[Colloquium] Kleinberg talk today 12:15 at TTI (new abstract)

[Meridel Trimble]

The title and abstract of this talk have been modified since the last announcement:

TOYOTA TECHNOLOGICAL INSTITUTE TALK

Speaker: Robert Kleinberg
MIT

Title: The Value of Knowing a Demand Curve: Bounds on Regret for Online
Posted-Price Auctions 
Time: Thursday, June 17th, 12:15 p.m.

Place: TTI-C (1427 E. 60th St. – 2nd Floor)
LUNCH PROVIDED

Speaker 's Homepage: http://www-math.mit.edu/~rdk/

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. 

If you have questions, or would like to meet the speaker, please contact
Meridel at 4-9873 or mtrimble at tti-c.org