Externalities in Keyword Auctions: an Empirical andTheoretical Assessment∗Renato GomesNorthwestern UniversityDepartment of [email protected] ImmorlicaNorthwestern UniversityDepartment of [email protected] MarkakisAthens University ofEconomics and BusinessDepartment of [email protected] is widely believed that the value of acquiring a slot in a sponsoredsearch list (that comes along with the organic links in a search en-gine’s result page) highly depends on who else is shown in the othersponsored positions. To capture such externality effects, we con-sider a model of keyword advertising where bidders participate in aGeneralized Second Price (GSP) auction and users perform orderedsearch (they browse from the top to the bottom of the sponsored listand make their clicking decisions slot by slot). Our contribution istwofold: first, we use impression and click data from MicrosoftLive to estimate the ordered search model. With these estimates inhand, we are able to assess how the click-through rate of an ad is af-fected by the user’s click history and by the other competing links.Further, we compare the clicking predictions of our ordered searchmodel to those of the most widely used model of user behavior: theseparable click-through rate model. Second, we study complete in-formation Nash equilibria of the GSP under different scoring rules.First, we characterize the efficient and revenue-maximizing com-plete information Nash equilibrium (under any scoring rule) andshow that such an equilibrium can be implemented with any set ofadvertisers if and only if a particular weighting rule that combinesclick-through rates and continuation probabilities is used. Interest-ingly, this is the same ranking rule derived in [11] for solving theefficient allocation problem. On the negative side, we show thatthere is no scoring rule that implements an efficient equilibriumwith VCG payments (VCG equilibrium) for all profiles of valua-tions and search parameters. This result extends [8], who argue thatthe rank-by-revenue GSP does not possess a VCG equilibrium.1. INTRODUCTIONSponsored search advertising is a booming industry that accountsfor a significant part of the revenue made by search engines. Forqueries with most commercial interest, Google, Yahoo! and MSNLive make available to advertisers up to three links above the or-∗Most of this work was done while all authors were at the Centerfor Math and Computer Science (CWI), Amsterdam. The projectwas partially funded by the Microsoft external research program"Beyond Search: Semantic Computing and Internet Economics".Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.Copyright 200X ACM X-XXXXX-XX-X/XX/XX ...$10.00.ganic results (these are the mainline slots), up to eight links besidesthe organic results (sidebar slots) and, more recently, MSN Liveeven sells links below the organic results (bottom slots).As such, an advertiser that bids for a sponsored position is sel-dom alone; and is usually joined by his fiercest competitors. In-deed, it is widely believed that the value of acquiring a sponsoredslot highly depends on the identity and position of the other ad-vertisers. Putting it differently, advertisers impose externalities oneach other, which affect their click-through rates and might haveconsequences on their bidding behavior.The literature on sponsored search auctions mostly assumes click-through rates are separable, i.e., the click through rate of a bidderis a product of two quantities, the first expressing the quality of thebidder and the second the quality of the slot she occupies. Suchmodels cannot capture the externalities that one advertiser imposeson the others. To capture these externality effects, we depart fromthe separable model and study a model that integrates the users’search behavior and the advertiser’s bidding behavior in the Gen-eralized Second Price (GSP) auction run by search engines. Wewill assume that users perform ordered search, which means that(i) they browse the sponsored links from top to bottom and (ii) theytake clicking decisions slot by slot. After reading each ad, users de-cide whether to click on it or not and, subsequently, decide whetherto continue browsing the sponsored list or to simply skip it alto-gether (for a formal definition and motivation for this model, seeSection 2). With this formulation, we are able to estimate continu-ation probabilities for each ad (which are simply the probabilitiesof continuing searching the sponsored list after clicking or not onsome ad) and conditional click-though rates for each ad (which tellthe probability of a click conditional on the user’s previous clickinghistory). Continuation probabilities capture position externalities,that is, they capture the negative impact that top links impose onthe click-through rates of bottom links (as users stop browsing ei-ther because their search needs were already fulfilled or becausethey got tired of previous bad matches). In turn, conditional click-through rates capture information externalities, as we can assesshow the information collected by the user by clicking on one givenlink impacts the click-through rates of the other links he eventuallyreads.On the auction side of the model, advertisers submit their bidstaking click-through rates as implied by ordered search. As pre-scribed by the rules of the GSP, search engines then multiply eachbid by a weight defined by a scoring rule (which solely depends oneach advertiser’s characteristics), producing a score for each adver-tiser. Advertisers are then ranked by their score; slots are assignedin decreasing order of scores and each advertiser pays per click theminimum bid necessary to keep his position.We use the model described above to make both empirical andtheoretical contributions. On the empirical side, we used threemonths of impression and clicking data from Microsoft Live toestimate the ordered search model. In this version we report ourfindings from three selected search terms: ipod, diet pill and avgantivirus. We plan to substantiate further our findings in a longerversion