TITLE: Competitive Auctions
SPEAKER: Andrew V. Goldberg (Microsoft Research)
DATE: 2:00-3:00 P.M., Tuesday, April 15, 2003
LOCATION: Half Dome, 3L (PA)
HOST: Vinay Deolalikar
ABSTRACT:
Recent trends, such as proliferation of digital goods and the
emergence of the Internet, have led to new dynamic pricing problems.
Traditionally studied by Economists and Game Theorists, these
problems have recently attracted attention of Computer Scientists.
Auctions are widely used dynamic pricing mechanisms. This
talks is a survey of recent work on competitive auctions.
Classical mechanism design works in Bayesian setting:
mechanisms assume that inputs come from a known distribution
and are designed to maximize expectation of a desired
parameter with respect to this distribution.
We take the worst-case analysis approach more common in
Computer Science and motivated by on-line algorithms.
Our competitive auctions combine two conflicting goals:
maximizing seller's revenue and encouraging buyers to bid their
true utility (i.e., these auctions are truthful).
In the competitive auction framework, one compares revenue of a
truthful auction to that of an optimal auction that need not be truthful.
We show that optimal single-price auctions are the right benchmark
for comparison.
We also show that, for a reasonable class of auctions, no
deterministic auction is competitive and randomized competitive
auctions exist.
We first consider auctions for digital goods. In this context,
we develop techniques for design and analysis of competitive auctions.
These techniques include random sampling and consensus revenue estimate.
Then we discuss extensions of these techniques to more problems.
Joint work with Jason Hartline.
|
printable version
