Generalized second-price auction
Generalized second-price auction
The generalized second-price auction (GSP) is a non-truthful auction mechanism for multiple items. Each bidder places a bid. The highest bidder gets the first slot, the second-highest, the second slot and so on, but the highest bidder pays the price bid by the second-highest bidder, the second-highest pays the price bid by the third-highest, and so on. First conceived as a natural extension of the vickrey-auction, it conserves some of the desirable properties of the Vickrey auction. It is used mainly in the context of keyword auctions, where sponsored search slots are sold on an auction basis. The first analyses of GSP are in the economics literature by Edelman, Ostrovsky, and Schwarz and by Varian. It is used by Google's AdWords technology and Facebook.
Formal model Suppose that there are <math>n</math> bidders and <math>k < n</math> slots. Each slot has a probability of being clicked of <math>\alpha_i</math>. We can assume that top slots have a larger probability of being clicked, so:
: <math>\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_k. \, </math>
We can think of <math>n-k</math> additional virtual slots with click-through-rate zero, so, <math>\alpha_m = 0</math> for <math>k<m \leq n</math>. Now, each bidder submits a bid <math>b_i</math> indicating the maximum they are willing to pay for a slot. Each bidder also has an intrinsic value for buying a slot <math>v_i</math>. Notice that a player's bid <math>b_i</math> doesn't need to be the same as their true valuation <math>v_i</math>. We order the bidders by their bid, let's say:
: <math>b_1 \geq b_2 \geq \cdots \geq b_n, \, </math>
and charge each bidder a price <math>p_i</math>. The price will be 0 if they didn't win a slot. Slots are sold in a pay-per-click model, so a bidder just pays for a slot if the user actually clicks in that slot. We say the utility of bidder <math>i</math> who is allocated to slot <math>i</math> is <math>u_i = \alpha_i (v_i - p_i)</math>. The total social welfare from owning or selling all slots is given by: <math>SW=\sum_i \alpha_i v_i.</math> The expected total revenue is given by: <math>TR=\sum_i \alpha_i p_i.</math>
GSP mechanism To specify a mechanism we need to define the allocation rule (who gets which slot) and the prices paid by each bidder. In a generalized second-price auction we order the bidders by their bid and give the top slot to the highest bidder, the second top slot to the second highest bidder and so on. Then, assuming the bids are listed in decreasing order <math>b_1 \geq b_2 \geq \cdots \geq b_n, \, </math> the bidder bidding <math>b_i</math> gets slot <math>i</math> for <math>1 \leq i \leq k</math>. Each bidder winning a slot pays the bid of the next highest bidder, so: <math>p_i = b_{i+1}</math>.
Non-truthfulness There are cases where bidding the true valuation is not a nash-equilibrium. For example, consider two slots with <math>\alpha_1 = 1</math> and <math>\alpha_2 = 0.4</math> and three bidders with valuations <math>v_1 = 7</math>, <math>v_2 = 6</math> and <math>v_3 = 1</math> and bids <math>b_1 = 7</math>, <math>b_2 = 6</math> and <math>b_3 = 1</math> respectively. Thus, <math>p_1=b_2=6</math>, and <math>p_2=b_3=1</math>. The utility for bidder <math>1</math> is <math>u_1 = \alpha_1 (v_1 - p_1)= 1(7-6)=1. </math> This set of bids is not a Nash equilibrium, since the first bidder could lower their bid to 5 and get the second slot for the price of 1, increasing their utility to <math>0.4(7-1)=2.4</math>.
Equilibria of GSP Edelman, Ostrovsky and Schwarz, and Lucier at al. prove
GSP and uncertainty The classical results due to Edelman, Ostrovsky and Schwarz and Caragiannis et al. discuss the Bayesian version of the game - where players have beliefs about the other players but do not necessarily know the other players' valuations.
Gomes and Sweeney consider the welfare loss at Bayes–Nash equilibrium and prove a price-of-anarchy bound of 2.927. Bounds on the revenue in Bayes–Nash equilibrium are given by Lucier et al. and Caragiannis et al.