Proceedings

More on the Power of Demand Queries in Combinatorial Auctions: Learning Atomic Languages and Handling Incentives

Download BibTeX Cite

Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 959-963.

© 2005 International Joint Conferences on Artificial Intelligence

Abstract

Query learning models from computational learning theory (CLT) can be adopted to perform elicitation in combinatorial auctions. Indeed, a recent elicitation framework demonstrated that the equivalence queries of CLT can be usefully simulated with price-based demand queries. In this paper, we validate the flexibility of this framework by defining a learning algorithm for atomic bidding languages, a class that includes XOR and OR. We also handle incentives, characterizing the communication requirements of the Vickrey-ClarkeGroves outcome rule. This motivates an extension to the earlier learning framework that brings truthful responses to queries into an equilibrium.

  1. [Bertsimas and Tsitsiklis, 1997] D Bersimas and J Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, 1997.
  2. [Blum et al., 2004] A Blum, J Jackson, T Sandholm, and M Zinkevich. Preference elicitation and query learning. Journal of Machine Learning Research (JMLR), 5:649-667, 2004.
  3. [Conen and Sandholm, 2001] W Conen and T Sandholm. Preference elicitation in combinatorial auctions. In Proc. 3rd ACM Conf. on Electronic Commerce (EC-01), pages 256-259. ACM Press, New York, 2001.
  4. [Conen and Sandholm, 2002] W Conen and T Sandholm. Partial-revelation VCG mechanism for combinatorial auctions. In Proc. 18th Nat. Conf. on Artificial In- telligence (AAAI'02), 2002.
  5. [Jackson, 2000] M Jackson. Mechanism theory. In The Encyclopedia of Life Support Systems. EOLSS Publishers, 2000.
  6. [Krishna and Perry, 2000] V Krishna and M Perry. Efficient mechanism de- sign. Technical report, Pennsylvania State University, 2000. Available at: http://econ.la.psu.edu/∼vkrishna/vcg18.ps. Link
  7. [Lahaie and Parkes, 2004] S Lahaie and D C Parkes. Applying learning algorithms to preference elicitation. In Proc. ACM Conf. on Electronic Commerce, pages 180- 188, 2004.
  8. [Mishra and Parkes, 2004] D Mishra and D C Parkes. Ascending price Vickrey auc- tions using primal-dual algorithms. Technical report, Harvard Univeristy, 2004.
  9. [Nisan and Segal, 2004] N Nisan and I Segal. The communication requirements of efficient allocations and supporting prices. To appear in the Journal of Economic Theory, 2004.
  10. [Nisan and Segal, 2004] N Nisan and I Segal. Exponential communication inefficiency of demand queries. Technical report, Hebrew University, 2004.
  11. [Nisan, 2000] N Nisan. Bidding and allocation in combinatorial auctions. In Proc. 2nd ACM Conf. on Electronic Commerce (EC-00), pages 1-12, 2000.
  12. [Parkes, 2002] D C Parkes. Price-based information certificates for minimal-revelation combinatorial auctions. In Agent Mediated Electronic Commerce IV: Designing Mechanisms and Systems, volume 2531 of Lecture Notes in Artificial Intelligence, pages 103-122. 2002.
  13. [Parkes, 2004] D C Parkes. Iterative combinatorial auctions. In Peter Cramton, Yoav Shoham, and Richard Steinberg, editors, Combinatorial Auctions, chapter 2. MIT Press, 2004.
  14. [Sandholm, 1993] T Sandholm. An implementation of the Contract Net Protocol based on marginal-cost calculations. In Proc. 11th National Conference on Artificial In- telligence (AAAI-93), pages 256-262, July 1993.
  15. [Santi et al., 2004] P Santi, V Conitzer, and T Sandholm. Towards a characterization of polynomial preference elicitation with value queries in combinatorial auctions. In Proc. Conf. on Computational Learning Theory (COLT), 2004.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards