Winner determination in combinatorial auctions with logic-based bidding languages

ABSTRACT

We propose the use of logic-based preference representation languages based on weighted propositional formulas for specifying bids in a combinatorial auction. We then develop several heuristics for a branch-and-bound search algorithm for determining the winning bids in this framework and report on their empirical performance. The logic-based approach is attractive due to its high degree of flexibility in designing a range of different bidding languages within a single conceptual framework.

REFERENCES

• 1: Craig Boutilier, Solving concisely expressed combinatorial auction problems, Eighteenth national conference on Artificial intelligence, p.359-366, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 2: C. Boutilier and H. H. Hoos. Bidding languages for combinatorial auctions. In Proc. 17th Intl. Joint Conference on Artif. Intell., 2001.
• 3: Y. Chevaleyre, U. Endriss, and J. Lang. Expressive power of weighted propositional formulas for cardinal preference modelling. In Proc. 10th Intl. Conference on Principles of Knowledge Representation and Reasoning, 2006.
• 4: Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
• 5: 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
• 6: 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
• 7: Jérôme Lang, Logical Preference Representation and Combinatorial Vote, Annals of Mathematics and Artificial Intelligence, v.42 n.1-3, p.37-71, September 2004 [doi>10.1023/B:AMAI.0000034522.25580.09]
• 8: 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]
• 9: N. Nisan. Bidding languages for combinatorial auctions. In P. Cramton et al., editors, Combinatorial Auctions. MIT Press, 2006.
• 10: G. Pinkas. Propositional nonmonotonic reasoning and inconsistency in symmetric neural networks. In Proc. 12th Intl. Joint Conference on Artif. Intell, 1991.
• 11: 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]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

General Terms:
Algorithms, Economics, Experimentation

Keywords:
combinatorial auctions, preference representation