CENTER Carnegie Mellon UniversityCarnegie Mellon Computer Science DepartmentSchool of Computer Science
Workshop on Auction Theory and Practice ABSTRACTS
Related Activities
Outreach Roadshow

Robert Kleinberg,
Department of Mathematics,


The Value of Knowing a Demand Curve: Bounds for Regret in Online Posted-Price Auctions

We address the question, "What is the value of knowing the demand curve for a good?" In other words, by how much can a seller with distributional information about buyers' valuations expect to outperform one who must learn this information through a series of transactions with buyers?

Specifically, we consider price-setting algorithms for a simple market in which a seller with an unlimited supply of identical copies of some good interacts sequentially with n buyers, each of whom wants at most one copy of the good. In each transaction, the seller offers a price between 0 and 1, and the buyer decides whether to buy or not by comparing the offered price with her privately-held valuation for the good. We consider three different assumptions on buyers' valuations -- identical, random, and worst-case -- deriving nearly-matching upper and lower bounds for the regret of the optimal pricing strategy in each case. The upper bounds are based on algorithms using ideas from machine-learning theory, while the lower bounds introduce a novel technique for quantifying exploration-versus-exploitation tradeoffs. This work has connections to the "multi-armed bandit" problem, as well as to optimization algorithms for congestion control, answering open questions in both areas.




This material is based upon work supported by National Science Foundation under Grant No. 0122581.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the
National Science Foundation