Winner determination in combinatorial auction generalizations

ABSTRACT

Combinatorial markets where bids can be submitted on bundles of items can be economically desirable coordination mechanisms in multiagent systems where the items exhibit complementarity and substitutability. There has been a surge of research on winner determination in combinatorial auctions. In this paper we study a wider range of combinatorial market designs: auctions, reverse auctions, and exchanges, with one or multiple units of each item, with and without free disposal. We first theoretically characterize the complexity of finding a feasible, approximate, or optimal solution. Reverse auctions with free disposal can be approximated (even in the multi-unit case), although auctions cannot. When XOR-constraints between bids are allowed (to express substitutability), the hardness turns the other way around: even finding a feasible solution for a reverse auction or exchanges is &Ngr;&Pgr;-complete, while in auctions that is trivial. Finally, in all of the cases without free disposal, even finding a feasible solution is &Ngr;&Pgr;-complete.We then ran experiments on known benchmarks as well as ones which we introduced, to study the complexity of the market variants in practice. Cases with free disposal tended to be easier than ones without. On many distributions, reverse auctions with free disposal were easier than auctions with free disposal---as the approximability would suggest---but interestingly, on one of the most realistic distributions they were harder. Single-unit exchanges were easy, but multi-unit exchanges were extremely hard.

REFERENCES

• 1: A. Andersson, M. Tenhunen, and F. Ygge. Integer programming for combinatorial auction winner determination. ICMAS, p. 39--46, 2000.
• 2: S. de Vries and R. Vohra. Combinatorial auctions: A survey. Draft, August 28th, 2000.
• 3: Yuzo Fujishima , Kevin Leyton-Brown , Yoav Shoham, Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.548-553, July 31-August 06, 1999
• 4: M. R. Garey and D. S. Johnson. Computers and Intractability. W. H. Freeman and Company, 1979.
• 5: 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]
• 6: J. Håstad. Clique is hard to approximate within n1-ε. Acta Mathematica, 182:105--142, 1999.
• 7: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 8: Holger H. Hoos , Craig Boutilier, Solving Combinatorial Auctions Using Stochastic Local Search, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.22-29, July 30-August 03, 2000
• 9: A. Kothari, T. Sandholm, and S. Suri. Solving combinatorial exchanges: Optimality via few partial bids. AAAI workshop on AI for Business, 2002.
• 10: 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]
• 11: Kevin Leyton-Brown , Mark Pearson , Yoav Shoham, Towards a universal test suite for combinatorial auction algorithms, Proceedings of the 2nd ACM conference on Electronic commerce, p.66-76, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352879]
• 12: Kevin Leyton-Brown , Yoav Shoham , Moshe Tennenholtz, An Algorithm for Multi-Unit Combinatorial Auctions, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.56-61, July 30-August 03, 2000
• 13: 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]
• 14: 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]
• 15: Tuomas Sandholm, eMediator: a next generation electronic commerce server, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.923-924, July 18-22, 1999, Orlando, Florida, United States
• 16: 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
• 17: Tuomas Sandholm , Subhash Suri, Improved Algorithms for Optimal Winner Determination in Combinatorial Auctions and Generalizations, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.90-97, July 30-August 03, 2000
• 18: T. Sandholm and S. Suri. Side constraints and non-price attributes in markets. IJCAI Workshop on Distributed Constraint Reasoning, p. 55--61, 2001.
• 19: T. Sandholm, S. Suri, A. Gilpin, and D. Levine. CABOB: A fast optimal algorithm for combinatorial auctions. IJCAI, p. 1102--1108, 2001.
• 20: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination; Multiagent systems
      I.2.8 Problem Solving, Control Methods, and Search

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics