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.