2009 · 90 citations · 28 references
BusinessBusiness EconomicsEconomicsAlgorithmsAuction TheoryGame TheoryCombinatorial AuctionsDynamic AuctionsExploration-exploitation TradeoffInformation EconomicsNash EquilibriumPrivate-value AuctionsBandit AlgorithmsMulti-armed Bandit OptimizationPay-per-click AdvertisingRegret OptimizationSocial Welfare TheoremsTruthful BiddingTruthful Mechanism DesignTruthful Mechanisms
Multi‑round pay‑per‑click auctions lack prior knowledge of click probabilities, motivating the study of mechanisms that learn and allocate efficiently. The study aims to design a dominant‑strategy truthful mechanism that approximately maximizes social welfare. The mechanism selects an advertiser each round, displays the ad, observes whether it is clicked, and uses this feedback to guide future selections.
We consider a multi-round auction setting motivated by pay-per-click auctions for Internet advertising. In each round the auctioneer selects an advertiser and shows her ad, which is then either clicked or not. An advertiser derives value from clicks; the value of a click is her private information. Initially, neither the auctioneer nor the advertisers have any information about the likelihood of clicks on the advertisements. The auctioneer's goal is to design a (dominant strategies) truthful mechanism that (approximately) maximizes the social welfare.
28
Roger B. Myerson · Mathematics of Operations Research · 1981 · 6.1K citations
Asymptotically efficient adaptive allocation rules
Tze-Leung Lai, Herbert Robbins · Advances in Applied Mathematics · 1985 · 2.5K citations
The Nonstochastic Multiarmed Bandit Problem
Peter Auer, Nicolò Cesa‐Bianchi, Yoav Freund et al. · SIAM Journal on Computing · 2002 · 2.3K citations