On maximizing welfare when utility functions are subadditive

ABSTRACT

We consider the problem of maximizing welfare when allocating m items to n players with subadditive utility functions. Our main result is a way of rounding any fractional solution to a linear programming relaxation to this problem so as to give a feasible solution of welfare at least half that of the value of the fractional solution. This approximation ratio of 1/2 improves over an Ω(1/log m) ratio of Dobzinski, Nisan and Schapira [STOC 2005]. We also show an approximation ratio of 1 - 1/e when utility functions are fractionally subadditive. A result similar to this last result was previously obtained by Dobzinski and Schapira [Soda 2006], but via a different rounding technique that requires the use of a so called "XOS oracle".The randomized rounding techniques that we use are oblivious in the sense that they only use the primal solution to the linear program relaxation, but have no access to the actual utility functions of the players. This allows us to suggest new incentive compatible mechanisms for combinatorial auctions, extending previous work of Lavi and Swamy [FOCS 2005].

REFERENCES

• 1: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 2: O. N. Bondareva. "Some applications of linear programming to cooperative games." Problemy Kibernetiki, 10:119--139, 1963.
• 3: E. Clarke. "Multipart pricing of public goods." Public Choice 8:17--33, 1971.
• 4: Shahar Dobzinski , Noam Nisan , Michael Schapira, Approximation algorithms for combinatorial auctions with complement-free bidders, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060681]
• 5: Shahar Dobzinski , Michael Schapira, An improved approximation algorithm for combinatorial auctions with submodular bidders, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1064-1073, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109675]
• 6: U. Feige, J. Vondrak. "The allocation problem with submodular utility functions." Manuscript, February 2006.
• 7: Lisa Fleischer , Michel X. Goemans , Vahab S. Mirrokni , Maxim Sviridenko, Tight approximation algorithms for maximum general assignment problems, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.611-620, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109624]
• 8: T. Groves. "Incentives in teams." Econometrica 41:617--631, 1973.
• 9: Ron Lavi , Chaitanya Swamy, Truthful and Near-Optimal Mechanism Design via Linear Programming, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.595-604, October 23-25, 2005 [doi>10.1109/SFCS.2005.76]
• 10: Benny Lehmann , Daniel Lehmann , Noam Nisan, Combinatorial auctions with decreasing marginal utilities, Proceedings of the 3rd ACM conference on Electronic Commerce, p.18-28, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501161]
• 11: L. S. Shapley. "On balanced sets and cores." Naval research logistics quarterly, 14:453--460, 1967.
• 12: W. Vickrey. "Counterspeculation, auctions and competitive sealed tenders." Journal of Finance, 1961.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Economics

Keywords:
combinatorial auctions, randomized rounding