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 ^[1] and by Varian. ^[2] It is used by Google's AdWords technology and Facebook.

Formal model

Suppose that there are ${\displaystyle n}$ bidders and ${\displaystyle k<n}$ slots. Each slot has a probability of being clicked of ${\displaystyle \alpha _{i}}$. We can assume that top slots have a larger probability of being clicked, so:

${\displaystyle \alpha _{1}\geq \alpha _{2}\geq \cdots \geq \alpha _{k}.\,}$

We can think of ${\displaystyle n-k}$ additional virtual slots with click-through-rate zero, so, ${\displaystyle \alpha _{m}=0}$ for ${\displaystyle k<m\leq n}$. Now, each bidder submits a bid ${\displaystyle b_{i}}$ indicating the maximum they are willing to pay for a slot. Each bidder also has an intrinsic value for buying a slot ${\displaystyle v_{i}}$. Notice that a player's bid${\displaystyle b_{i}}$ doesn't need to be the same as their true valuation${\displaystyle v_{i}}$. We order the bidders by their bid, let's say:

${\displaystyle b_{1}\geq b_{2}\geq \cdots \geq b_{n},\,}$

and charge each bidder a price ${\displaystyle p_{i}}$. 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 ${\displaystyle i}$ who is allocated to slot ${\displaystyle i}$ is ${\displaystyle u_{i}=\alpha _{i}(v_{i}-p_{i})}$. The total social welfare from owning or selling all slots is given by: ${\displaystyle SW=\sum _{i}\alpha _{i}v_{i}.}$ The expected total revenue is given by: ${\displaystyle TR=\sum _{i}\alpha _{i}p_{i}.}$

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}\geq b_{2}\geq \cdots \geq b_{n},\,}$ the bidder bidding ${\displaystyle b_{i}}$ gets slot ${\displaystyle i}$ for ${\displaystyle 1\leq i\leq 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(7-1)=2.4}$.

Equilibria of GSP

Edelman, Ostrovsky and Schwarz, ^[1] 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., ^[3] proving a price of anarchy bound of ${\displaystyle 1.282}$. Dütting et al. ^[4] and Lucier at al. prove ^[5] 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. ^[6]

GSP and uncertainty

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

Budget constraints

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

See also

• Vickrey–Clarke–Groves auction
• Generalized first-price auction
• Google Ads
• Auction theory
• Japanese auction

References

1. Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz: "Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords". American Economic Review 97(1), 2007 pp 242-259
2. H. R. Varian: "Position auctions. International Journal of Industrial Organization, 2006".
3. Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis; Kyropoulou, Maria; Lucier, Brendan; Paes Leme, Renato; Tardos, Eva (2015). "Bounding the inefficiency of outcomes in generalized second price auctions". Journal of Economic Theory. 156: 343–388. arXiv: 1201.6429 . doi:10.1016/j.jet.2014.04.010. S2CID   37395632.
4. Dütting, Paul; Fischer, Felix; Parkes, David C. (2011). "Simplicity-Expressiveness Tradeoffs in Mechanism Design". Proceedings of the 12th ACM Conference on Electronic Commerce (EC'11): 341–350. doi:10.1145/1993574.1993632. ISBN   9781450302616. S2CID   607322.
5. Lucier, Brendan; Renato, Paes Leme; Eva, Tardos (2012). "On Revenue in the Generalized Second Price Auction". Proceedings of the 21st International World Wide Web Conference (WWW'12): 361–370. doi:10.1145/2187836.2187886. ISBN   9781450312295. S2CID   6518222.
6. D. R. M. Thompson and K. Leyton-Brown. Computational analysis of perfect-information position auctions. In EC ’09: Proceedings of the tenth ACM conference on Electronic commerce, pages 51–60, New York, NY, USA, 2009. ACM.
7. R. D. Gomes and K. S. Sweeney. "Bayes–Nash equilibria of the generalized second price auction". In EC ’09: Proceedings of the tenth ACM conference on Electronic commerce, pages 107–108, New York, NY, USA, 2009. ACM
8. Susan Athey and Denis Nekipelov. A Structural Model of Sponsored Search Advertising Auctions Archived 2012-04-25 at the Wayback Machine , Ad Auctions Workshop, 2010
9. Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis; Kyropoulou, Maria (2014). "Revenue Guarantees in the Generalized Second Price Auction" (PDF). ACM Transactions on Internet Technology. 14 (2–3): 1–19. doi:10.1145/2663497. S2CID   9233522.
10. Ashlagi, Itai; Braverman, Mark; Hassidim, Avinatam; Lavi, Ron; Tennenholtz, Moshe (2010). "Position Auctions with Budgets: Existence and Uniqueness". The B.E. Journal of Theoretical Economics. 10 (1): Article 20. doi:10.2202/1935-1704.1648. hdl: 1721.1/64459 . S2CID   8624078.
11. Aggarwal, Gagan; Muthukrishnan, Muthu; Pal, David; Pal, Martin (2009). "General Auction Mechanism for Search Advertising". Proceedings of the 18th International World Wide Web Conference (WWW'09): 241–250. arXiv: 0807.1297 . doi:10.1145/1526709.1526742. ISBN   9781605584874. S2CID   2800123.
12. Dütting, Paul; Henzinger, Monika; Weber, Ingmar (2011). "An Expressive Mechanism for Auctions on the Web". Proceedings of the 20th World Wide Web Conference (WWW'11): 127–136. doi:10.1145/1963405.1963427. ISBN   9781450306324. S2CID   2138064.

• S. Lahaie, D. Pennock, A. Saberi, and R. Vohra. Algorithmic Game Theory, chapter "Sponsored search auctions", pages 699–716. Cambridge University Press, 2007
• Lecture notes on Keyword-Based Advertisement