Generalized second-price auction

Suppose that there are $n$ bidders and slots. Each slot has a probability of being clicked of $\backslash alpha\_i$. We can assume that top slots have a larger probability of being clicked, so:

: $\backslash alpha\_1\; \backslash geq\; \backslash alpha\_2\; \backslash geq\; \backslash cdots\; \backslash geq\; \backslash alpha\_k.\; \backslash ,$

We can think of $n-k$ additional virtual slots with click-through-rate zero, so, $\backslash alpha\_m\; =\; 0$ for bid $b\_i$ doesn't need to be the same as their true valuation $v\_i$.

We order the bidders by their bid, let's say:

: $b\_1\; \backslash geq\; b\_2\; \backslash geq\; \backslash cdots\; \backslash geq\; b\_n,\; \backslash ,$

and charge each bidder a price $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 $i$ who is allocated to slot $i$ is $u\_i\; =\; \backslash alpha\_i\; (v\_i\; -\; p\_i)$. The total social welfare from owning or selling all slots is given by: $SW=\backslash sum\_i\; \backslash alpha\_i\; v\_i.$ The expected total revenue is given by: $TR=\backslash sum\_i\; \backslash alpha\_i\; p\_i.$

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 $b\_1\; \backslash geq\; b\_2\; \backslash geq\; \backslash cdots\; \backslash geq\; b\_n,\; \backslash ,$ the bidder bidding $b\_i$ gets slot $i$ for $1\; \backslash leq\; i\; \backslash leq\; k$. Each bidder winning a slot pays the bid of the next highest bidder, so: $p\_i\; =\; b\_\{i+1\}$.

There are cases where bidding the true valuation is not a Nash equilibrium. For example, consider two slots with $\backslash alpha\_1\; =\; 1$ and $\backslash alpha\_2\; =\; 0.4$ and three bidders with valuations $v\_1\; =\; 7$, $v\_2\; =\; 6$ and $v\_3\; =\; 1$ and bids

$b\_1\; =\; 7$, $b\_2\; =\; 6$ and $b\_3\; =\; 1$ respectively. Thus, $p\_1=b\_2=6$, and $p\_2=b\_3=1$. The utility for bidder $1$ is $u\_1\; =\; \backslash 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 $0.4(7-1)=2.4$.

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 $SW\; =\; \backslash sum\_i\; \backslash alpha\_i\; v\_i$ where bidder $i$ is allocated slot $i$ according to the decreasing bid vector $(b\_1,\; \backslash 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 $1.282$. Dütting et al.{{cite book|last1=Dütting|first1=Paul|last2=Fischer|first2=Felix|last3=Parkes|first3=David C.|title=Proceedings of the 12th ACM conference on Electronic commerce |chapter=Simplicity-expressiveness tradeoffs in mechanism design |date=2011|pages=341–350|doi=10.1145/1993574.1993632 |isbn=9781450302616 |s2cid=607322 |chapter-url=http://nrs.harvard.edu/urn-3:HUL.InstRepos:4892934 }} 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.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.

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 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 and Caragiannis et al. and also empirically by Athey and Nekipelov Susan Athey and Denis Nekipelov. [http://keystonestrategy.com/publications/pdf/athey%20structural%20model%20sponsored%20search%20ad.pdf A Structural Model of Sponsored Search Advertising Auctions] {{Webarchive|url=https://web.archive.org/web/20120425113102/http://www.keystonestrategy.com/publications/pdf/athey%20structural%20model%20sponsored%20search%20ad.pdf |date=2012-04-25 }}, Ad Auctions Workshop, 2010 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.{{cite journal|last1=Caragiannis|first1=Ioannis|last2=Kaklamanis|first2=Christos|last3=Kanellopoulos|first3=Panagiotis|last4=Kyropoulou|first4=Maria|last5=Lucier|first5=Brendan|last6=Paes Leme|first6=Renato|last7=Tardos|first7=Eva|title=Bounding the inefficiency of outcomes in generalized second price auctions|journal=Journal of Economic Theory|volume=156|pages=343–388|doi=10.1016/j.jet.2014.04.010|arxiv=1201.6429|year=2015|s2cid=37395632 }} 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.{{cite book|last1=Lucier|first1=Brendan|last2=Renato|first2=Paes Leme|last3=Eva|first3=Tardos|title=Proceedings of the 21st international conference on World Wide Web |chapter=On revenue in the generalized second price auction |date=2012|pages=361–370|doi=10.1145/2187836.2187886 |isbn=9781450312295 |s2cid=6518222 }} and Caragiannis et al.{{cite journal | doi=10.1145/2663497 | title=Revenue Guarantees in the Generalized Second Price Auction | year=2014 | last1=Caragiannis | first1=Ioannis | last2=Kaklamanis | first2=Christos | last3=Kanellopoulos | first3=Panagiotis | last4=Kyropoulou | first4=Maria | journal=ACM Transactions on Internet Technology | volume=14 | issue=2–3 | pages=1–19 | s2cid=9233522 | url=http://repository.essex.ac.uk/28645/1/Revenue%2BGuarantees%2Bin%2BGeneralized%2BSecond%2BPrice%2BAuctions.pdf }}

The effect of budget constraints in the sponsored search or position auction model is discussed in Ashlagi et al.{{cite journal|last1=Ashlagi|first1=Itai|last2=Braverman|first2=Mark|author-link2=Mark Braverman|last3=Hassidim|first3=Avinatam|last4=Lavi|first4=Ron|last5=Tennenholtz|first5=Moshe|author-link5=Moshe Tennenholtz|title=Position Auctions with Budgets: Existence and Uniqueness|journal=The B.E. Journal of Theoretical Economics|volume=10|issue=1|article-number=20|doi=10.2202/1935-1704.1648|year=2010|hdl=1721.1/64459|s2cid=8624078 |hdl-access=free}} and in the more general assignment problem by Aggarwal et al.{{cite book|last1=Aggarwal|first1=Gagan|last2=Muthukrishnan|first2=Muthu|author2-link=S. Muthukrishnan (computer scientist)|last3=Pal|first3=David|last4=Pal|first4=Martin|title=Proceedings of the 18th international conference on World wide web |chapter=General auction mechanism for search advertising |date=2009|pages=241–250|doi=10.1145/1526709.1526742 |arxiv=0807.1297 |isbn=9781605584874 |s2cid=2800123 }} and Dütting et al.{{cite book|last1=Dütting|first1=Paul|last2=Henzinger|first2=Monika|author-link2=Monika Henzinger|last3=Weber|first3=Ingmar|title=Proceedings of the 20th international conference on World wide web |chapter=An expressive mechanism for auctions on the web |author-link3=Ingmar Weber|date=2011|pages=127–136|doi=10.1145/1963405.1963427 |isbn=9781450306324 |s2cid=2138064 |chapter-url=http://infoscience.epfl.ch/record/153929 }}

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

{{Reflist}}

• 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 [http://www.infosci.cornell.edu/courses/info204/2007sp/kba.pdf Keyword-Based Advertisement]

Category:Types of auction