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.
Contents |
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:
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 bi indicating the maximum he is willing to pay for a slot. We order the bidders by the value of their bid, let's say:
and charge each user a price pi. 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 ui = αj(bi − pi). 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:
| ∑ | pi |
| i |
.
To specify a mechanism 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 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: pi = bi + 1
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 v1 = 7, v2 = 6 and v3 = 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.
|
|
Wikis
Search
