Advertisement
Published in:
2005 | OriginalPaper | Chapter
Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions
Authors : Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
Published in: Internet and Network Economics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider the following allocation problem arising in the setting of combinatorial auctions: a set of goods is to be allocated to a set of players so as to maximize the sum of the utilities of the players (i.e., the social welfare). In the case when the utility of each player is a monotone submodular function, we prove that there is no polynomial time approximation algorithm which approximates the maximum social welfare by a factor better than 1–1/
e
≃ 0.632, unless
P
=
NP
. Our result is based on a reduction from a multi-prover proof system for MAX-3-COLORING.