Online Learning in Online Auctions
journal contributionposted on 01.09.2006, 00:00 authored by Avrim Blum, Vijay Kumar, Atri Rudra, Felix Wu
We 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. , 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].