Robert Kleinberg,
Department of Mathematics,
MIT

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.