Learning Valuation Distributions from Partial Observation


  • Avrim Blum Carnegie Mellon University
  • Yishay Mansour Tel Aviv University
  • Jame Morgenstern Carnegie Mellon University




Auction theory traditionally assumes that bidders’ val- uation distributions are known to the auctioneer, such as in the celebrated, revenue-optimal Myerson auc- tion (Myerson 1981). However, this theory does not de- scribe how the auctioneer comes to possess this infor- mation. Recently work (Cole and Roughgarden 2014) showed that an approximation based on a finite sample of independent draws from each bidder’s distribution is sufficient to produce a near-optimal auction. In this work, we consider the problem of learning bidders’ val- uation distributions from much weaker forms of obser- vations. Specifically, we consider a setting where there is a repeated, sealed-bid auction with n bidders, but all we observe for each round is who won, but not how much they bid or paid. We can also participate (i.e., submit a bid) ourselves, and observe when we win. From this information, our goal is to (approximately) recover the inherently recoverable part of the underlying bid distributions. We also consider extensions where different subsets of bidders participate in each round, and where bidders’ valuations have a common-value component added to their independent private values.




How to Cite

Blum, A., Mansour, Y., & Morgenstern, J. (2015). Learning Valuation Distributions from Partial Observation. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9301



AAAI Technical Track: Game Theory and Economic Paradigms