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 employed by Google's AdWords technology.
Contents
Formal model
Suppose that there are
We can think of
and charge each bidder a price
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. So, bidder
Non-truthfulness
There are cases where bidding the true valuation is not a Nash equilibrium. For example, consider two slots with
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
Bounds on the welfare at Nash equilibrium are given by Caragiannis et al., proving a Price of Anarchy bound of
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 impact of budget constraints in the sponsored search/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.