Applying learning algorithms to preference elicitation

ABSTRACT

We consider the parallels between the preference elicitation problem in combinatorial auctions and the problem of learning an unknown function from learning theory. We show that learning algorithms can be used as a basis for preference elicitation algorithms. The resulting elicitation algorithms perform a polynomial number of queries. We also give conditions under which the resulting algorithms have polynomial communication. Our conversion procedure allows us to generate combinatorial auction protocols from learning algorithms for polynomials, monotone DNF, and linear-threshold functions. In particular, we obtain an algorithm that elicits XOR bids with polynomial communication.

REFERENCES

• 1: Integer Programming for Combinatorial Auction Winner Determination, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.39, July 10-12, 2000
• 2: Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
• 3: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 4: S. Bikhchandani and J. Ostroy. The Package Assignment Model. Journal of Economic Theory, 107(2), December 2002.
• 5: A. Blum, J. Jackson, T. Sandholm, and M. Zinkevich. Preference elicitation and query learning. In Proc. 16th Annual Conference on Computational Learning Theory (COLT), Washington DC, 2003.
• 6: Wolfram Conen , Tuomas Sandholm, Partial-revelation VCG mechanism for combinatorial auctions, Eighteenth national conference on Artificial intelligence, p.367-372, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 7: 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
• 8: Benoît Hudson , Tuomas Sandholm, Using value queries in combinatorial auctions, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779971]
• 9: Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
• 10: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• 11: 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]
• 12: N. Nisan and I. Segal. The communication requirements of efficient allocations and supporting Lindahl prices. Working Paper, Hebrew University, 2003.
• 13: David C. Parkes, Price-Based Information Certificates for Minimal-Revelation Combinatorial Auctions, Revised Papers from the Workshop on Agent Mediated Electronic Commerce on Agent-Mediated Electronic Commerce IV, Designing Mechanisms and Systems, p.103-122, July 16, 2002
• 14: David C. Parkes, Auction design with costly preference elicitation, Annals of Mathematics and Artificial Intelligence, v.44 n.3, p.269-302, July 2005 [doi>10.1007/s10472-005-4692-y]
• 15: David C. Parkes , Lyle H. Ungar, Iterative Combinatorial Auctions: Theory and Practice, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.74-81, July 30-August 03, 2000
• 16: T. Sandholm, S. Suri, A. Gilpin, and D. Levine. CABOB: A fast optimal algorithm for combinatorial auctions. In Proc. the 17th International Joint Conference on Artificial Intelligence (IJCAI), pages 1102--1108, 2001.
• 17: Robert E. Schapire , Linda M. Sellie, Learning sparse multivariate polynomials over a field with queries and counterexamples, Proceedings of the sixth annual conference on Computational learning theory, p.17-26, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168307]
• 18: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 19: 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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

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

General Terms:
Algorithms, Economics, Theory

Keywords:
combinatorial auctions, learning, preference elicitation