Incentive compatible multi unit combinatorial auctions

ABSTRACT

This paper deals with multi-unit combinatorial auctions where there are n types of goods for sale, and for each good there is some fixed number of units. We focus on the case where each bidder desires a relatively small number of units of each good. In particular, this includes the case where each good has exactly k units, and each bidder desires no more than a single unit of each good. We provide incentive compatible mechanisms for combinatorial auctions for the general case where bidders are not limited to single minded valuations. The mechanisms we give have approximation ratios close to the best possible for both on-line and off-line scenarios. This is the first result where non-VCG mechanisms are derived for non-single minded bidders for a natural model of combinatorial auctions.

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: B. Awerbuch, Y. Azar, and A. Meyerson. Reducing Truth-telling Online Mechanisms to Online Optimization. Unpublished draft 2003.
• 3: B. Awerbuch, Y. Azar, and S. Plotkin. Throughput-Competitive On-Line Routing. Proceeding of 34th FOCS 1993, pp. 32--40.
• 4: Yossi Azar , Oded Regev, Strongly Polynomial Algorithms for the Unsplittable Flow Problem, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.15-29, June 13-15, 2001
• 5: E. H. Clarke Multipart Pricing of Public Goods. In journal Public Choice 1971, volume 2, pages 17--33.
• 6: Rica Gonen , Daniel Lehmann, Optimal solutions for multi-unit combinatorial auctions: branch and bound heuristics, Proceedings of the 2nd ACM conference on Electronic commerce, p.13-20, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352873]
• 7: R. Gonen, and D. Lehmann Linear Programming helps solving Large Multi-unit Combinatorial Auctions. In Proceeding of INFORMS 2001, November 4--7, 2001, Miami Beach, Florida.
• 8: Green, J. R., and J. J. Laffont Characterization of satisfactory mechanisms for the reveraltion of preferences in public goods. Econometrica 45, 1977.
• 9: T. Groves Incentives in teams. In journal Econometrica 1973, volume 41, pages 617--631.
• 10: J. Hastad Clique is Hard to Approximate to within n1--εJournal Acta Mathematica 1999, volume 182.
• 11: Hofmeister, and Lefmann. Approximating Maximum Independent Sets in Uniform Hypergraphs Erscheinungsjahr. 1998
• 12: Holzman, R., N. Kfir-Dahav, D. Monderer, and M. Tennenholtz On Bundling Equilibrium in Combinatorial Auctions mimeo, Technical report, Technion, http://iew3.technion.ac.il/~moshet/rndmll.ps
• 13: R. Lavi, A. Mu'alem and N. Nisan. Towards a Characterization of Truthful Combinatorial Auctions. Preliminary version 2003.
• 14: Ron Lavi , Noam Nisan, Competitive analysis of incentive compatible on-line auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.233-241, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352897]
• 15: Daniel Lehmann , Liaden Ita O'Callaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Proceedings of the 1st ACM conference on Electronic commerce, p.96-102, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337016]
• 16: 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]
• 17: Ahuva Mu'alem , Noam Nisan, Truthful approximation mechanisms for restricted combinatorial auctions: extended abstract, Eighteenth national conference on Artificial intelligence, p.379-384, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 18: N. Nisan Algorithms for Selfish Agents. In Proceedings of STACS, 1999
• 19: 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]
• 20: 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
• 21: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 22: 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]
• 23: N. Nisan, and I. Segal. The Communication Complexity of Efficient Allocation Problems. Working paper.
• 24: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 25: Roberts, K. The characterization of implementable choice rules. in aggregation and revelation of preferences, editor, J. J. Laffont, 1979.
• 26: Michael H. Rothkopf , Aleksandar Pekec , Ronald M. Harstad, Computationally Manageable Combinational Auctions, Management Science, v.44 n.8, p.1131-1147, August 1998 [doi>10.1287/mnsc.44.8.1131]
• 27: T. Sandholm Limitations of the Vickrey Auction in Computational Multiagent Systems. Proceedings of the Second International Conference on Multiagent Systems (ICMAS-96), pages 299--306, Kyoto, Japan, December 1996.
• 28: Tuomas Sandholm, An Algorithm for Optimal Winner Determination in Combinatorial Auctions, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.542-547, July 31-August 06, 1999
• 29: W. Vickrey Counterspeculation, Auctions and Competitive Sealed Tenders. In Journal of Finance 1961, volume 16, pages 8--37.
• 30: Vohra, R., and S. de Vries Combinatorial auctions: A survey. Available from http://www.kellogg.nwu.edu/faculty/vohra/htm/res.htm.
• 31: Edo Zurel , Noam Nisan, An efficient approximate allocation algorithm for combinatorial auctions, Proceedings of the 3rd ACM conference on Electronic Commerce, p.125-136, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501172]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Games

General Terms:
Algorithms, Design, Documentation