Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions

ABSTRACT

We provide tight information-theoretic lower bounds for the welfare maximization problem in combinatorial auctions. In this problem, the goal is to partition m items among k bidders in a way that maximizes the sum of bidders' values for their allocated items. Bidders have complex preferences over items expressed by valuation functions that assign values to all subsets of items.

We study the "black box" setting in which the auctioneer has oracle access to the valuation functions of the bidders. In particular, we explore the well-known value query model in which the permitted query to a valuation function is in the form of a subset of items, and the reply is the value assigned to that subset of items by the valuation function.

We consider different classes of valuation functions: submodular,subadditive, and superadditive. For these classes, it has been shown that one can achieve approximation ratios of 1 -- 1/e, 1/√m, and √ m/m, respectively, via a polynomial (in k and m) number of value queries. We prove that these approximation factors are essentially the best possible: For any fixed ε > 0, a (1--1/e + ε)-approximation for submodular valuations or an 1/_m1/2-ε-approximation for subadditive valuations would require exponentially many value queries, and a log^1+ε m/ m-approximation for superadditive valuations would require a superpolynomial number of value queries.

REFERENCES

• 1: Liad Blumrosen , Noam Nisan, On the computational power of iterative auctions, Proceedings of the 6th ACM conference on Electronic commerce, p.29-43, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064013]
• 2: Liad Blumrosen , Noam Nisan, On the computational power of iterative auctions, Proceedings of the 6th ACM conference on Electronic commerce, p.29-43, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064013]
• 3: S. Dobzinski. Private communication, 2006.
• 4: 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]
• 5: 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]
• 6: Uriel Feige, On maximizing welfare when utility functions are subadditive, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132523]
• 7: Uriel Feige , Jan Vondrak, Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.667-676, October 21-24, 2006 [doi>10.1109/FOCS.2006.14]
• 8: Uriel Feige , Vahab S. Mirrokni , Jan Vondrak, Maximizing Non-Monotone Submodular Functions, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.461-471, October 21-23, 2007 [doi>10.1109/FOCS.2007.40]
• 9: R. Holzman, N. Kfir-Dahav, D. Monderer and M. Tennenholtz. Bundling equilibrium in combinatorial auctions. Games and Economic Behavior 47, 2004, 104--123.
• 10: S. Khot, R. Lipton, E. Markakis and A. Mehta.Inapproximability results for combinatorialauctions with submodular utility functions. In Proc. of WINE 2005.
• 11: 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]
• 12: Noam Nisan, Bidding and allocation in combinatorial auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.1-12, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352872]
• 13: N. Nisan and I. Segal. The communication requirements of efficient allocations and supportingprices. Journal of Economic Theory, 129:1, 2006, 192--224.
• 14: G. Nemhauser and M. Fisher, and L. Wolsey. An analysis of approximations for maximizing submodular set functions II. Math. Programming Study 8, 1978, 73--87.
• 15: Jan Vondrak, Optimal approximation for the submodular welfare problem in the value oracle model, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374389]

INDEX TERMS

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

General Terms:
Algorithms, Economics, Theory

Keywords:
approximation algorithms, combinatorial auctions