One of the defining characteristic of ad auctions is that they are repeated a large number of times. Every time some user makes a search query or visits a web page with an “ad slot” on it a new auction takes place among all advertisers that target their ads at this impression. The targeting criteria may be quite sophisticated, taking into account not only the characteristics of the ad-slot (web page or search keyword) but also various characteristics of the user such as his geographic location (and sometimes much more). While much of the early work on ad auctions focused on the single auction, much of the current work of ad auctions focuses explicitly on the repetitions, on the stream. If the different auctions in the stream are totally unrelated then one of them shouldn’t effect the others, and indeed they should be analyzed in isolation. In many real world scenarios, however, there are significant constraints between the different auctions in the stream that need to be taken into account. Looking at the papers soon to be presented in EC’09 we can see several such issues:
- Budgets: It is very common for an advertiser to have a budget limit for the total expenditure over all auctions in a certain period. This raises many questions, both game-theoretic and algorithmic, from the bidder’s point of view as well as from the auctioneer’s point of view. The basic paper addressing the algorithmic problem of the auctioneer due to Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani presents an online algorithm with a worst case competitive ratio of 1-1/e. Many variants of the model have been considered in the literature, but the 1-1/e ratio has been hard to beat. The EC’09 paper “The Adwords Problem: Online Keyword Matching with Budgeted Bidders under Random Permutations” by Nikhil Devanur and Thomas Hayes does so getting a approximation by adding a distributional assumption to model.
- Reservations: Advertisers often wish to “reserve” a certain number of impressions of some target type in advance. If this has been done, then once the stream of impressions arrives, then the reserved number of impressions should be delivered sometime during the agreed-upon period (with some penalty if the reservation cannot be fulfilled.) There are challenges during reservation time (can the auctioneer commit to a requested reservation? how to price it?) as well as during delivery time (which reservation should the current impression fulfill?). The EC’09 paper “Selling Ad Campaigns: Online Algorithms with Cancellations” by Moshe Babaioff, Jason Hartline, and Robert Kleinberg studies the added flexibility that the auctioneer gets if he is allowed to renege on past reservations, for a cancellation fee.
- Learning: Most ad auctions have a pay-per-click rule: the bidders pay for the impression that they won only if the ad was “clicked” by the user. This means that the “real bid” to be considered depends on the “click through rate” — the probability that the ad will be clicked — a random variable that depends on the impression and on the advertiser. These click through rates can be learned throughout the stream of auctions, and then taken into account in future auctions. Non-strategic analysis of similar situations often falls under the name of multi-arm bandit problems, and two closely related papers in EC’09 take into account the strategic behavior of the bidders: “Characterizing Truthful Multi-Armed Bandit Mechanisms” by Moshe Babaioff, Yogeshwer Sharma, and Aleksandrs Slivkins and “The Price of Truthfulness for Pay-Per-Click Auctions” by Nikhil Devanur and Sham Kakade.