“Internet Advertising and the Generalized Second-Price Auction,” B. Edelman, M. Ostrovsky & M. Schwarz (2007)

Consider the Google Adwords Auction. When you search on Google (or Microsoft, or facebook, or Bing, among others), a series of ads is displayed in your browser. Assume that, when you search for “cookies,” the top ad slot is clicked 3 times per hour, the second slot 2 times per hour and the bottom slot once per hour. How should you sell these?

You could just set a fixed price for every X displays of each ad: this was how internet advertising was done in the 1990s. But we know that a posted price is rarely the optimal mechanism. Instead, why not auction each slot? Since we also have a famous result that adding bidders to the auction is a very good thing indeed, why not sell all three ad slots simultaneously? Have each advertiser offer a bid per click, then give the slot with the most clicks to the bidder who bid highest, the second most clicks to the bidder who bid second highest, and so on. The designers of this auction, Overture (now owned by Yahoo), were likely familiar with some economics literature and knew that second-price auctions had some nice properties: they are dominant-strategy truthful, they are efficient, and with a proper reserve price, they are optimal. Overture took that intuition and started charging the top bidder the second highest bid per click, the second highest bidder the third highest per click and so on. They called this “generalized second price”, or GSP. As of the mid-2000s, Google claimed in ad materials that this auction was very similar in its properties to a classic second-price auction.

Edelman and his coauthors, as well as Varian in a separate 2007 paper, noted that this is, in fact, not so. GSP is not necessarily efficient (let private values be [16,15,14], clickthrough rate be [3,2,1] and bids be [7,9,11]; you can check and see that this bidding is Nash in the one-shot simultaneous bid game, but has the highest value bidder getting the least number of clicks) nor truthful (let private values be [4,3,2] and clickthrough rate be [10,9,0] – truthful bids give bidder with value 4 a payoff of (4-3)*10=10, but bidding 2.5 would give her (4-2.5)*9=13.5). What, then, are the properties of the GSP mechanism? And why does anyone use it?

For any given parameter values, there are tons of Nash equilibria when GSP is modeled as a one-shot simultaneous bid game. The real auction is dynamic: bidders may change their bids as often as they want. Edelman et al, as well as Varian, refine the Nash set to equilibria that are a stable matching (in the sense of Roth and Sotomayor) between ad slots and bidders. It turns out that all of these “stable” or “locally envy-free” or “symmetric” equilibria give the auctioneer higher revenue than the Vickrey-Clarke-Groves mechanism; even though VCG is much simpler for bidders, auctioneers may be using GSP in order to extract higher revenue.

There have been many extensions of this model, only a few of which I point out. Susan Athey has a paper with Glenn Ellison incorporating consumer search across ad platforms – that is, the value of an ad slot is endogenous – and another paper with Denis Nekipelov adding bidder uncertainty about how the search engine will “quality-score” their bid. My classmates Kane Sweeney and Renato Gomes let bidders be uncertain about other bidders’ values per click, and show that even in the static game an efficient Bayes Nash equilibrium to GSP often fails to exist. I suppose this post mainly serves as notes to myself on this topic – I’m putting final touches on a new paper about GSP in a dynamic context with the takeaway that GSP is actually particularly bad for the auctioneer when bidders bid sequentially, and that the stable matching/local envy free refinement to stage game Nash is in an important sense giving exactly the opposite results of the dynamic subgame perfect equilibria set. More on this in a couple weeks.

http://www.benedelman.org/publications/gsp-060801.pdf (Final AER version – three cheers to Ben Edelman for posting final versions of his papers on his website!)

Advertisement