Generalized second-price auction

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 ${\displaystyle b_1\ge b_2\ge \cdots \ge b_n,}$ the bidder bidding ${\displaystyle b_i}$ gets slot ${\displaystyle i}$ for ${\displaystyle 1\le i\le k}$. Each bidder winning a slot pays the bid of the next highest bidder, so: ${\displaystyle p_i=b_{i+1}}$.

Non-truthfulness

There are cases where bidding the true valuation is not a Nash equilibrium. For example, consider two slots with ${\displaystyle {\alpha }_1=1}$ and ${\displaystyle {\alpha }_2=0.4}$ and three bidders with valuations ${\displaystyle v_1=7}$, ${\displaystyle v_2=6}$ and ${\displaystyle v_3=1}$ and bids ${\displaystyle b_1=7}$, ${\displaystyle b_2=6}$ and ${\displaystyle b_3=1}$ respectively. Thus, ${\displaystyle p_1=b_2=6}$, and ${\displaystyle p_2=b_3=1}$. The utility for bidder ${\displaystyle 1}$ is ${\displaystyle u_1={\alpha }_1(v_1-p_1)=1(7-6)=1.}$ 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 ${\displaystyle 0.4(5-1)=1.6}$.

Equilibria of GSP

Edelman, Ostrovsky and Schwarz, working under complete information, show that GSP (in the model presented above) always has an efficient locally-envy free equilibrium, i.e., an equilibrium maximizing social welfare, which is measured as ${\displaystyle SW=\sum _i{\alpha }_i{v}_i}$ where bidder ${\displaystyle i}$ is allocated slot ${\displaystyle i}$ according to the decreasing bid vector ${\displaystyle (b_1,\dots ,b_n)}$. Further, the expected total revenue in any locally-envy free equilibrium is at least as high as in the (truthful) VCG outcome.

Bounds on the welfare at Nash equilibrium are given by Caragiannis et al., proving a price of anarchy bound of ${\displaystyle 1.282}$. Dütting et al. and Lucier at al. prove that any Nash equilibrium extracts at least one half of the truthful VCG revenue from all slots but the first. Computational analysis of this game have been performed by Thompson and Leyton-Brown.

GSP and uncertainty

The classical results due to Edelman, Ostrovsky and Schwarz and Varian hold in the full information setting – when there is no uncertainty involved. Recent results as Gomes and Sweeney and Caragiannis et al. and also empirically by Athey and Nekipelov 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 prove that an efficient equilibrium might not exist in the partial information setting. Caragiannis et al. 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.

Budget constraints

The effect of budget constraints in the sponsored search or position auction model is discussed in Ashlagi et al. and in the more general assignment problem by Aggarwal et al. and Dütting et al.