Learning Market Parameters Using Aggregate Demand Queries

Authors

  • Xiaohui Bei Nanyang Technological University
  • Wei Chen Microsoft Research
  • Jugal Garg Max-Planck-Institut für Informatik
  • Martin Hoefer Max-Planck-Institut für Informatik
  • Xiaoming Sun China Academy of Science

DOI:

https://doi.org/10.1609/aaai.v30i1.10027

Keywords:

Fisher market, exchange market, revealed preference, query complexity

Abstract

We study efficient algorithms for a natural learning problem in markets. There is one seller with m divisible goods and n buyers with unknown individual utility functions and budgets of money. The seller can repeatedly announce prices and observe aggregate demand bundles requested by the buyers. The goal of the seller is to learn the utility functions and budgets of the buyers. Our scenario falls into the classic domain of ''revealed preference'' analysis. Problems with revealed preference have recently started to attract increased interest in computer science due to their fundamental nature in understanding customer behavior in electronic markets. The goal of revealed preference analysis is to observe rational agent behavior, to explain it using a suitable model for the utility functions, and to predict future agent behavior. Our results are the first polynomial-time algorithms to learn utility and budget parameters via revealed preference queries in classic Fisher markets with multiple buyers. Our analysis concentrates on linear, CES, and Leontief markets, which are the most prominent classes studied in the literature. Some of our results extend to general Arrow-Debreu exchange markets.

Downloads

Published

2016-02-21

How to Cite

Bei, X., Chen, W., Garg, J., Hoefer, M., & Sun, X. (2016). Learning Market Parameters Using Aggregate Demand Queries. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10027

Issue

Section

Technical Papers: Game Theory and Economic Paradigms