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.