Inapproximability results for combinatorial auctions with submodular utility functions (Q943868): Difference between revisions

The authors consider allocation problems on a combinatorial auction where a set of goods is to be allocated to a set of players. A utility function is associated with each player specifying the happiness of the player for each subset of the goods. The goal for the auctioneer is to maximize the economic efficiency of the auction, which is the sum of the utilities of all the players. The allocation problem consists of finding a partition of a set of m indivisible goods among n players that maximizes the overall utility of the system. The authors study the computational complexity of this problem when players' utility functions are submodular. The main result in the paper is that there is no polynomial time approximation algorithm for the allocation problem with monotone submodular utility functions achieving a ratio better than \(1 - 1/e\), unless \(P = NP\). This result is based on a reduction from a multi-prover proof system for MAX-3-COLORING.