Robert
Kleinberg,
Department
of Mathematics,
MIT

The Value of Knowing a Demand Curve: Bounds
for Regret in Online PostedPrice 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 pricesetting 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 privatelyheld valuation
for the good. We consider three different assumptions on
buyers' valuations  identical, random, and worstcase
 deriving nearlymatching 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 machinelearning
theory, while the lower bounds introduce a novel technique
for quantifying explorationversusexploitation tradeoffs.
This work has connections to the "multiarmed bandit"
problem, as well as to optimization algorithms for congestion
control, answering open questions in both areas.
