TITLE: The Value of Knowing a Demand Curve:
Bounds on Regret for Online Posted-Price Auctions
SPEAKER: Bobby Kleinberg, MIT
ABSTRACT:
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 some good interacts
sequentially with n buyers. In each transaction, the seller offers a
price between 0 and 1, and the buyer decides whether or not to buy one
copy 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.