file.pdf (173.23 kB)
Download fileOnline Learning in Online Auctions
journal contribution
posted on 2006-09-01, 00:00 authored by Avrim Blum, Vijay Kumar, Atri Rudra, Felix WuWe consider the problem of revenue maximization in online auctions, that is, auctions in
which bids are received and dealt with one-by-one. In this note, we demonstrate that results
from online learning can be usefully applied in this context, and we derive a new auction for
digital goods that achieves a constant competitive ratio with respect to the best possible (offline)
fixed price revenue.
We are primarily concerned with auctions for a single good available in unlimited supply,
often described as a digital good, though our techniques may also be useful for the case of limited
supply. The problem of designing online auctions for digital goods was first described by Bar-
Yossef et al. [3], one of a number of recent papers interested in analyzing revenue-maximizing
auctions without making statistical assumptions about the participating bidders [2, 6, 8, 10].