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.
Keywords Combinatorial auctions - Submodular - Social welfare - Hardness of approximation
This work was performed when all authors were at the Georgia Institute of Technology. A preliminary version of this work appears
in Khot et al. (Workshop on internet and network economics, pp. 92–101, 2005)
R.J. Lipton’s research supported by NSF grant CCF-0431023.