Avrim Blum, Vijay Kumar,
Atri Rudra and Felix Wu
Online Learning in Online Auctions
Abstract :
The advent of online stores on the Internet has led to the
proliferation
of digital goods. These are goods, which
unlike the ``traditional" goods generally studied in the economics literature,
can be replicated without any additional cost to the seller (for example
MP3 songs). In addition the
buyers are selfish, that is, the buyers can lie about what they are
willing to pay in order to get a better deal for themselves. To complicate
matters further buyers arrive in an online fashion, that is, the seller
has no information about the buyers in advance. Given all these constraints,
the seller wants to make as much money as possible.
In such scenarios, the seller generally cannot hope to make as much
money as if either the buyers are honest or if the seller has the information
of all the buyers in advance.
In this work,
we considered the problem of designing auctions for a single
digital good, which could provably generate an almost optimal revenue even in
the presence of selfish buyers who arrive in an online fashion. This work was
one of the first to apply techniques from online learning theory
to problems in algorithmic game theory. Techniques from learning theory
have since found much success in such settings.
Versions