Approximation algorithms for combinatorial auctions with complement-free bidders

ABSTRACT

We exhibit three approximation algorithms for the allocation problem in combinatorial auctions with complement free bidders. The running time of these algorithms is polynomial in the number of items $m$ and in the number of bidders n, even though the "input size" is exponential in m. The first algorithm provides an O(log m) approximation. The second algorithm provides an O(√ m) approximation in the weaker model of value oracles. This algorithm is also incentive compatible. The third algorithm provides an improved 2-approximation for the more restricted case of "XOS bidders", a class which strictly contains submodular bidders. We also prove lower bounds on the possible approximations achievable for these classes of bidders. These bounds are not tight and we leave the gaps as open problems.

REFERENCES

• 1: Aaron Archer , Christos Papadimitriou , Kunal Talwar , Éva Tardos, An approximate truthful mechanism for combinatorial auctions with single parameter agents, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 2: Yair Bartal , Rica Gonen , Noam Nisan, Incentive compatible multi unit combinatorial auctions, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana [doi>10.1145/846241.846250]
• 3: Alejandro Bertelsen and Daniel Lehmann. Substitutes valuations: M#-concavity. Working Paper.
• 4: Liad Blumrosen and Noam Nisan. On the computational power of iterative auctions I: Demand queries, 2005. Working paper.
• 5: Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
• 6: Shahar Dobzinski and Michael Schapira. Optimal upper and lower approximation bounds for k-duplicates combinatorial auctions, 2005. Working paper.
• 7: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 8: Martin Grötschel, Lászlo Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. IIASA Collab. Proceedings Ser. CP-81-S1, pages 511--546, 1981.
• 9: T. Groves. Incentives in teams. Econometrica, pages 617--631, 1973.
• 10: Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
• 11: Ron Holzman, Noa Kfir-Dahav, Dov Monderer, and Moshe Tennenholtz. Bundling equilibrium in combinatrial auctions. Games and Economic Behavior, 47:104--123, 2004.
• 12: Subhash Khot, Richard Lipton, Evangelos Markakis, and Aranyak Mehta. Inapproximability results for combinatorial auctions with submodular utility functions, 2005. Working paper.
• 13: Samir Khuller , Anna Moss , Joseph (Seffi) Naor, The budgeted maximum coverage problem, Information Processing Letters, v.70 n.1, p.39-45, April 01, 1999 [doi>10.1016/S0020-0190(99)00031-9 ]
• 14: 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]
• 15: Daniel Lehmann , Liadan Ita Oćallaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Journal of the ACM (JACM), v.49 n.5, p.577-602, September 2002 [doi>10.1145/585265.585266]
• 16: Noam Nisan, The Communication Complexity of Approximate Set Packing and Covering, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.868-875, July 08-13, 2002
• 17: Noam Nisan, RL⊆SC, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.619-623, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129772]
• 18: Noam Nisan. Chapter 9: Bidding Languages. In P. Cramton and Y. Shoham and R. Steinberg (Editors), Combinatorial Auctions. MIT Press. Forthcoming, 2005. Available from http://www.cs.huji.ac.il/~noam/mkts.html.
• 19: Noam Nisan , Amir Ronen, Computationally feasible VCG mechanisms, Proceedings of the 2nd ACM conference on Electronic commerce, p.242-252, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352898]
• 20: Noam Nisan and Ilya Segal. The communication requirements of efficient allocations and supporting prices, 2003. Working paper. Available from http://www.cs.huji.ac.il/~noam/mkts.html.
• 21: Tuomas Sandholm, Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence, v.135 n.1-2, p.1-54, 02/01/2002 [doi>10.1016/S0004-3702(01)00159-X ]
• 22: Alexander Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory Series B, v.80 n.2, p.346-355, Nov. 2000 [doi>10.1006/jctb.2000.1989 ]
• 23: D. Sivakumar, Algorithmic derandomization via complexity theory, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509996]
• 24: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
combinatorial auctions