Online Learning in Online Auctions

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. [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].