An efficient approximate allocation algorithm for combinatorial auctions

ABSTRACT

We propose a heuristic for allocation in combinatorial auctions. We first run an approximation algorithm on the linear programming relaxation of the combinatorial auction. We then run a sequence of greedy algorithms, starting with the order on the bids determined by the approximate linear program and continuing in a hill-climbing fashion using local improvements in the order of bids. We have implemented the algorithm and have tested it on the complete corpus of instances provided by Vohra and de Vries as well as on instances drawn from the distributions of Leyton-Brown, Pearson, and Shoham. Our algorithm typically runs two to three orders of magnitude faster than the reported running times of Vohra and de Vries, while achieving an average approximation error of less than 1%. This algorithm can provide, in less than a minute of CPU time, excellent solutions for problems with over 1000 items and 10,000 bids. We thus believe that combinatorial auctions for most purposes face no practical computational hurdles.

REFERENCES

• 1: A. Andersson, M. Tenhunen, and F. Ygge. Integer programming for combinatorial auction winner determination. In ICMAS, 2000.
• 2: Yair Bartal , John W. Byers , Danny Raz, Global Optimization Using Local Information with Applications to Flow Control, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.303, October 19-22, 1997
• 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: 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]
• 5: 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]
• 6: Michael Luby , Noam Nisan, A parallel approximation algorithm for positive linear programming, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.448-457, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167211]
• 7: 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]
• 8: N. Nisan. The Communication Complexity of Combinatorial Auctions. Available from http://www.cs.huji.ac.il/~noam/ccaucecon.pdf, 2001.
• 9: Serge A. Plotkin , David B. Shmoys , Eva Tardos, Fast approximation algorithms for fractional packing and covering problems, Stanford University, Stanford, CA, 1993
• 10: 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]
• 11: 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
• 12: T. W. Sandholm. Limitations of the vickrey auction in computational multiagent systems. In Proceedings of the Second International Conference on Multiagent Systems (ICMAS-96), pages 299-306, Keihanna Plaza, Kyoto, Japan, December 1996.
• 13: Moshe Tennenholtz, Some Tractable Combinatorial Auctions, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.98-103, July 30-August 03, 2000
• 14: R. Vohra and S. de Vries. Combinatorial auctions: A survey, 2000.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Experimentation, Performance