CS 789 THEORY SEMINAR [home]

Speaker:   Bobby Kleinberg 
Affiliation: MIT
Date:   April 19, 2004      
Title:   The Value of Knowing a Demand Curve:  Bounds on Regret for Online Posted-Price Auctions     

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.

This is based on joint work with Tom Leighton.