Source: Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords by Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz

Pay-Per-Click advertising is the primary source of revenue for internet search companies such as Yahoo and Google. When a user enters a search query, advertisements to sites that match the query are returned along with the search results. In class, Prof. Kleinberg mentioned that Google uses a second-price auction to sell the rights to have their ads displayed beside certain search keywords. Generally in second-price auctions, the buyer should bid their true value. In reality, multiple advertisements can appear for a given keyword, so advertising providers such as Google and Yahoo! use a form of second-price auctions to place advertisements on the page. The key difference is that there is a limited number of ads that can appear for each keyword, and some placements (at the top of the page) are better than others (at the bottom of the page). In this modified second-price auction, which the authors refer to as GSP, short for generalized second-price, advertisers bid on a keyword, and when the user searches for that keyword, the advertisements are shown in order of bid price, the bidder who bid the most gets to have the most desirable placement. When a user clicks on an advertisement, the owner of that ad is charged the second-price amount for that bid, that is the bid price of the ad below the one the user clicked.

The article reveals that GSP guarantees the seller’s payoff will be least that of the second-price auctions we did in class, given the same bid prices. Perhaps even more interesting is that the added twist of ad positioning makes the dominant strategy for GSP no longer each bidder bidding their true value. The authors give the following counterexample of why bidding truthfully is no longer the dominant strategy:

• 3 bidders with values $10, $4, $2 vying for 2 positions.
• Position 1 has 200 clicks per hour, Position 2 has 199 clicks per hour.
• If bidder 1 bids his true value, his payoff will be (10-4)*200 = $1200
• If instead bidder 1 bids $3, his payoff in Position 2 will be (10-2)*199 = $1592
• $1592 > $1200, therefore all agents bidding truthfully is not a dominant strategy.

Like we did in class, the article also shows how GSP is the same as a generalized English Auction, where bidding starts with everyone in and price $0. As the price increases, bidders drop out until there is just one bidder left, who is given the first ad position at the price where the second to last bidder dropped out, etc. In this auction, a bidder will drop out before the price gets to the point where moving to the next position will no longer increase his payoff. This strategy is an equilibrium and will yield the same payoffs as the English and second-price auctions we learned in class, but only if all the other bidders follow the same strategy. The generalized English Auction is different from the English Auction in that there still is no dominant strategy.

Source: Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords by Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz