Generalized second-price auction Information & Generalized second-price auction Links at HealthHaven.com

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.

[edit] Formal model

Consider there are $n$ bidders and $k < n$ slots. Each slot has a probability of being clicked of $α i$ . We can assume that top slots have a larger probability of being clicked, so:

$\alpha_1 \geq \alpha_2 \geq ... \geq \alpha_k$

We can think of $n - k$ additional virtual slots with click-through-rate zero, so, $α i = 0$ for $i > k$ . Now, each user submits a bid $b i$ indicating the maximum he is willing to pay for a slot. We order the bidders by the value of their bid, let's say:

$b_1 \geq b_2 \geq ... \geq b_n$

and charge each user a price $p i$ . Slots are sold in a pay-per-click model, so a user just pays for a slot if the user actually clicks in that slot. We say the utility of user $i$ when allocated to slot $j$ is $u i = α j (b i - p i)$ . The total social welfare is given by:

∑	α_jb_π(j)
j

where $π(j)$ is the user allocated to slot $j$ . The total revenue is given by:

∑	p_i
i

.

[edit] GSP Mechanism

To specify a mechanism we need to define the allocation rule (who gets which slot) and the prices payed by each bidder. In GSP we order the bidders by their bid value and give the top slot to the highest bidder, the second top slot to the second highest bidder and so on... So, bidder $i$ gets slot $i$ . Each bidder pays the bid of the next highest bidder, so: $p i = b i + 1$

[edit] Non-truthfulness

There are cases where bidding the true valuation is not a Nash equilibrium. For example, consider two slots with $α 1 = 1$ and $α 2 = 0.4$ and three bidders with valuations $v 1 = 7$ , $v 2 = 6$ and $v 3 = 1$ . 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.

[edit] See also

Auction theory

[edit] References

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

Lecture notes on Keyword-Based Advertisement

Contents

[edit] Formal model

[edit] GSP Mechanism

[edit] Non-truthfulness

[edit] See also

[edit] References