Generalized second-price auction
Encyclopedia
The generalized second-price auction (GSP) is a non-truthful auction mechanism for multiple items. First thought of as a natural extension of the Vickrey auction
, it actually doesn't conserve some good properties of the Vickrey auction (as truthfulness, for example). It is used mainly in the context of keyword auctions, where sponsored search slots are sold on an auction-base. The first analysis of GSP are in the economics
literature by Edelman, Ostrovsky and Schwarz and by Varian
. It is employed by Google's AdWords
technology.
bidders and 
slots. Each slot has a probability of being clicked of 
. We can assume that top slots have a larger probability of being clicked, so:
We can think of
additional virtual slots with click-through-rate zero, so, 
for 
. Now, each bidder has an intrinsic value for one slot 
submits a bid 
indicating the maximum he is willing to pay for a slot (which is his bid reported valuation - notice it doesn't need to be the same as his true valuation 
). We order the bidders by the value of their value, let's say:
and charge each bidder a price
(this 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
when allocated to slot 
is 
. The total social welfare from owning or selling slots is given by: 
where 
is the bidder allocated to slot 
. The total revenue is given by: 
we need to define the allocation rule (who gets which slot) and the prices paid by each bidder. In GSP 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
gets slot 
. Each bidder pays the bid of the next highest bidder, so: 
..
. For example, consider two slots with
and 
and three bidders with valuations 
, 
and 
. Bidding 7, 6 and 1 respectively is not a Nash equilibrium, since the first bidder could lower his bid to 5 and get the second slot for the price of 1 and increase his utility therefore.
where 
is the slot in which player 
is allocated according to his bid (the permutation 
is defined by the bid vector 
). This equilibrium has the property that the outcome (allocation and payments) is the similar of VCG. The same papers study properties of a natural but restricted class of equilibria called envy-free equilibria. They prove that envy-free equilibria always exist and it always maximizes the social welfare - they also compare the revenue on different envy-free equilibria. Lahaie studies the GSP from a Theoretical Computer Science point of view. Paes Leme and Tardos
study the structure of the general equilibria in GSP and prove Price of Anarchy
. They prove that the Price of Anarchy under a set of natural conditions is bounded by
(golden ratio
). Computational analysis of this game have been performed by Thompson and Leyton-Brown.
- when there is no uncertainty involved. Recent results as Gomes and Sweeney and Paes Leme and Tardos and also empirically by Athey and Nikipelov discuss the Bayesian version of the game - where players have beliefs about the other players, but not necessarily know the other players valuations. Gomes and Sweeney prove that an efficient equilibrium might not exist in the partial information setting. Paes Leme and Tardos prove a bound of 8 for the Bayes-Nash Price of Anarchy
.
Vickrey auction
A Vickrey auction is a type of sealed-bid auction, where bidders submit written bids without knowing the bid of the other people in the auction, and in which the highest bidder wins, but the price paid is the second-highest bid. The auction was created by William Vickrey...
, it actually doesn't conserve some good properties of the Vickrey auction (as truthfulness, for example). It is used mainly in the context of keyword auctions, where sponsored search slots are sold on an auction-base. The first analysis of GSP are in the economics
Economics
Economics is the social science that analyzes the production, distribution, and consumption of goods and services. The term economics comes from the Ancient Greek from + , hence "rules of the house"...
literature by Edelman, Ostrovsky and Schwarz and by Varian
Hal Varian
Hal Ronald Varian is an economist specializing in microeconomics and information economics. He is the Chief Economist at Google and he holds the title of emeritus professor at the University of California, Berkeley where he was founding dean of the School of Information...
. It is employed by Google's AdWords
AdWords
Google AdWords is Google's main advertising product and main source of revenue. Google's total advertising revenues were USD$28 billion in 2010. AdWords offers pay-per-click advertising, cost-per-thousand advertising, and site-targeted advertising for text, banner, and rich-media ads. The AdWords...
technology.
Formal model
Consider there are bidders and slots. Each slot has a probability of being clicked of . We can assume that top slots have a larger probability of being clicked, so:
We can think of
additional virtual slots with click-through-rate zero, so, for . Now, each bidder has an intrinsic value for one slot submits a bid indicating the maximum he is willing to pay for a slot (which is his bid reported valuation - notice it doesn't need to be the same as his true valuation ). We order the bidders by the value of their value, let's say:
and charge each bidder a price
(this will be 0 if they didn't win a slot). Slots are sold in a pay-per-clickPay per click
Pay per click is an Internet advertising model used to direct traffic to websites, where advertisers pay the publisher when the ad is clicked. With search engines, advertisers typically bid on keyword phrases relevant to their target market...
model, so a bidder just pays for a slot if the user actually clicks in that slot. We say the utility of bidder
when allocated to slot is . The total social welfare from owning or selling slots is given by: where is the bidder allocated to slot . The total revenue is given by: GSP mechanism
To specify a mechanismMechanism design
Mechanism design is a field in game theory studying solution concepts for a class of private information games...
we need to define the allocation rule (who gets which slot) and the prices paid by each bidder. In GSP 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
gets slot . Each bidder pays the bid of the next highest bidder, so: ..Non-truthfulness
There are cases where bidding the true valuation is not a Nash equilibriumNash equilibrium
In game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally...
. For example, consider two slots with
and and three bidders with valuations , and . Bidding 7, 6 and 1 respectively is not a Nash equilibrium, since the first bidder could lower his bid to 5 and get the second slot for the price of 1 and increase his utility therefore.Equilibria of GSP
Edelman, Ostrovsky and Schwarz show that GSP (in the model presented above) has always an efficient equilibrium, i.e., an equilibrium maximizing social welfare, which is measured as where is the slot in which player is allocated according to his bid (the permutation is defined by the bid vector ). This equilibrium has the property that the outcome (allocation and payments) is the similar of VCG. The same papers study properties of a natural but restricted class of equilibria called envy-free equilibria. They prove that envy-free equilibria always exist and it always maximizes the social welfare - they also compare the revenue on different envy-free equilibria. Lahaie studies the GSP from a Theoretical Computer Science point of view. Paes Leme and TardosÉva Tardos
Éva Tardos is a Hungarian mathematician, winner of the Fulkerson Prize , and professor of Computer Science at Cornell University.Research Interests:...
study the structure of the general equilibria in GSP and prove Price of Anarchy
Price of anarchy
The Price of Anarchy is a concept in game theory that measures how the efficiency of a system degrades due to selfish behavior of its agents. It is a general notion that can be extended to diverse systems and notions of efficiency. For example, consider the system of transportation of a city and...
. They prove that the Price of Anarchy under a set of natural conditions is bounded by
(golden ratioGolden ratio
In mathematics and the arts, two quantities are in the golden ratio if the ratio of the sum of the quantities to the larger quantity is equal to the ratio of the larger quantity to the smaller one. The golden ratio is an irrational mathematical constant, approximately 1.61803398874989...
). 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 settingComplete information
Complete information is a term used in economics and game theory to describe an economic situation or game in which knowledge about other market participants or players is available to all participants. Every player knows the payoffs and strategies available to other players.Complete information...
- when there is no uncertainty involved. Recent results as Gomes and Sweeney and Paes Leme and Tardos and also empirically by Athey and Nikipelov discuss the Bayesian version of the game - where players have beliefs about the other players, but not necessarily know the other players valuations. Gomes and Sweeney prove that an efficient equilibrium might not exist in the partial information setting. Paes Leme and Tardos prove a bound of 8 for the Bayes-Nash Price of Anarchy
Price of anarchy
The Price of Anarchy is a concept in game theory that measures how the efficiency of a system degrades due to selfish behavior of its agents. It is a general notion that can be extended to diverse systems and notions of efficiency. For example, consider the system of transportation of a city and...
.