Using value queries in combinatorial auctions

ABSTRACT

Combinatorial auctions, where bidders can bid on bundles of items, are known to be desirable auction mechanisms for selling items that are complementary and/or substitutable. However, there are 2^k --1 bundles, and each agent may need to bid on all of them to fully express its preferences. We address this by showing how them auctioneer can recommend to the agents incrementally which bundles to bid on so that they need to only place a small fraction of all possible bids. These algorithms impose a great computational burden on the auctioneer; we show how to speed them up dramatically. We also present an optimal elicitor, which is intractable but may be the basis for future algorithms. Finally, we introduce the notion of a universal revelation reducer, demonstrate a randomized one, and prove that no deterministic one exists.The full paper is available in draft form at http://www.cs.cmu.edu/ sandholm/using_value_queries.pdf.

REFERENCES

• 1: Wolfram Conen , Tuomas Sandholm, Preference elicitation in combinatorial auctions, Proceedings of the 3rd ACM conference on Electronic Commerce, p.256-259, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501191]
• 2: Wolfram Conen , Tuomas Sandholm, Differential -Revelation VCG Mechanisms for Combinatorial Auctions, Revised Papers from the Workshop on Agent Mediated Electronic Commerce on Agent-Mediated Electronic Commerce IV, Designing Mechanisms and Systems, p.34-51, July 16, 2002
• 3: Benoît Hudson , Tuomas Sandholm, Effectiveness of Preference Elicitation in Combinatorial Auctions, Revised Papers from the Workshop on Agent Mediated Electronic Commerce on Agent-Mediated Electronic Commerce IV, Designing Mechanisms and Systems, p.69-86, July 16, 2002
• 4: Noam Nisan and Ilya Segal. The communication complexity of efficient allocation problems Draft. March, 2002.
• 5: David C. Parkes, iBundle: an efficient ascending price bundle auction, Proceedings of the 1st ACM conference on Electronic commerce, p.148-157, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337032]
• 6: Trey Smith, Tuomas Sandholm, and Reid Simmons. Constructing and clearing combinatorial exchanges using preference elicitation. In AAAI-02 workshop on Preferences in AI and CP: Symbolic Approaches, 2002.
• 7: Martin A. Zinkevich , Avrim Blum , Tuomas Sandholm, On polynomial-time preference elicitation with value queries, Proceedings of the 4th ACM conference on Electronic commerce, p.176-185, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779949]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms, Experimentation, Performance

Keywords:
combinatorial auctions, electronic auctions, preference elicitation