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.
Turing's Invisible Hand 
Interesting set of papers. I would like to suggest my paper that describes the measurement problem a number of AdSense suppliers encounter due the difficulties introduced in sensing due to the “channel issue” (where Google reports revenue in aggregate not per-click): http://www.win-vector.com/dfiles/ComparingApplesAndOrangesProblemsWithAdsense.pdf .
Noam, do you have any reference or data to support your statement that the “it is common to have budget restrictions…” in the AdWords auctions? Of course, putting a billion dollar as a maximum budget is a budget, but not something which is realistic. What a budget realistically means, is a budget which realisticaly could be hit by an auction.
What I think most advertisers describe is that their budgets are elastic, that is, as long as they are hitting the RoI goals, they are happy to spend money, because in that case it is not spend but it is invest.
In “it is common” I didn’t mean “in Google’s adwords auctions there is X% fraction…”, but rather the much less specific “there could be applications in which….”. I definitely wouldn’t want to disclose Google confidential numbers…..
In any case, in almost all of the advertising industry the main constraint used to buy ads is budget. It is definitely true that in search budgets are not as prominent, but this does not nullify the role of budgets everywhere online.
Noam, the paper you have referenced uses online auctions or spot market and budgets. Yes, budgets are important elsewhere in the online advertising, but then spot market is not usually used there. Instead contracts are manually negotiated for a period of inventory.
The thing is that in spot markets, a spot is bought only if it is profitable. Well, if it is profitable, then why upper bound the profit?
While I agree with the basic logic of your argument, reality seems to be fuzzier. The paper that I referred to is from Microsoft, and I don’t know the specific motivation there. From my side, let me just reprint a footnote from my own paper on budgets with Lavi and Dobzinski:
“The nature of what this budget limit means for the bidders themselves is somewhat of a mystery since it often does not seem to simply reflect the true liquidity constraints of the bidding firm. There seems to be some risk control element to it, some purely administrative element to it, some bounded-rationality element to it, and more. What can not be disputed is that these budget constraints are very real to the bidders, in fact, usually more concrete and real than the rather abstract notion of the valuation.”
Regarding the quote from your paper, my question what is the basis of that quote? A paper implies a certain level of investigation. Do you have publically verifiable data to make this claim that budgets are real? If not, then the users may be willing to trust your word, if you say that you made the quote based on the data you observed at your place of employment?
Otherwise making this footnote is questionable, and should not be made in a scientific paper, where the readers beleive a certain amount of publically verifiable evidence or at least a confirmed investigation by the author. Since you did not cite any reference to this claim, you get the credit and accountable to produce the evidence, in case another scientist asks.
The footnote was our interpretation of known facts rather than reporting new data. I am not sure what exactly do you dispute here: that advertisers set budgets to their online campaigns? That sometimes these budgets are the main constraint? That advertisers often take these budget limits very seriously and that the various auctioneers must also do so? That the economic “meaning” of these budget limits is sometimes not clear?
[…] Online Stochastic Matching: Beating 1-1/e by Jon Feldman, Aranyak Mehta, Vahab Mirrokni and S. Muthukrishnan. (A link to the paper hides in this related blog post.) […]
i dont know alot about algoritmic game teory, but this can give me konowledge abot that, thank you
[…] researchers, much of this work seems to focus on issues that are of basic theoretical interest in settings of repeated auctions, often departing from the basic models of dominant-strategy worst-case analysis, vying for more […]