📢

Every search you run sells advertising in a fraction of a second. Several slots down the page, several advertisers bidding, and the auction has to decide who goes where and what they pay. The rule Google actually uses is not the truthful one from the textbook.

Auctions III: position auctions

Selling one item is one thing; selling ranked slots that each deliver different traffic is another. Position auctions allocate ad slots to advertisers. VCG makes truthful bidding weakly dominant, but the classic generalized-second-price format does not. Under a lowest locally envy-free equilibrium in the standard model, GSP can nevertheless reproduce VCG’s efficient allocation and payments.

From earlier lessons

Two quick ones before we start.

Under VCG, a winner pays...

The single-item second-price auction is VCG with...

Predict, then play

Two slots, worth 100 and 80 clicks. Advertisers value clicks differently. Compare how VCG and the generalized second price (GSP) charge the winners.

Why did that happen?

Take a guess, then reveal the reason

VCG charges you the harm you do to others. Your bid can change the allocation and the payment, but truthful bidding makes VCG choose the allocation maximizing your true value plus others’ reported value, so honesty is weakly dominant. GSP charges you the bid just below yours, which depends on where everyone sits. Because that price takes no account of what the lower slots cost, the top advertiser can sometimes do better by shading under the second bid and buying a cheaper slot instead: fewer clicks, but a much lower price on each one. When that trade is worth taking, truthful bidding is not an equilibrium. In the standard separable-click model, a lowest locally envy-free GSP equilibrium reproduces VCG payments, but that is an equilibrium result, not a property of every GSP bid profile.

The math

Slots deliver $100$ and $80$ clicks; advertisers $A$ , $B$ , $C$ value a click at $10$ , $6$ , $4$ . The efficient assignment pairs the highest value with the most clicks: $A \to$ slot 1, $B \to$ slot 2, welfare $10(100) + 6(80) = 1480$ .

VCG payments charge each winner its externality. For $A$ : without $A$ , the others do best with $B \to 100$ , $C \to 80$ , welfare $920$ ; with $A$ present, the others get only $B \to 80 = 480$ . So $A$ pays $920 - 480 = 440$ (4.4 per click). For $B$ : without $B$ , others get $A \to 100$ , $C \to 80 = 1320$ ; with $B$ , others get $A \to 100 = 1000$ ; $B$ pays $320$ (4 per click).

Definition, GSP versus VCG

The generalized second-price auction ranks advertisers by bid and charges each the next advertiser’s bid per click. With one slot it is the ordinary second-price auction and is truthful. With several slots it is no longer truthful: a bidder can gain by shading into a cheaper lower slot. In the standard separable-click model, its lowest locally envy-free equilibrium yields the VCG payments. Other GSP bid profiles need not be efficient or have VCG prices.

Under truthful bids GSP charges $A$ the next bid $6$ over $100$ clicks, so $600$ , against VCG’s $440$ . Now check whether $A$ wants to stay. Holding slot 1 nets $100(10-6) = 400$ ; shading to just under $6$ hands slot 1 to $B$ and buys slot 2 at $C$ ‘s bid, netting $80(10-4) = 480$ . Since $480 > 400$ , truth-telling is not an equilibrium here.

The overcharge on its own does not settle it. Shrink slot 2 to $50$ clicks and GSP still charges $A$ above VCG, but dropping down then nets only $50(10-4) = 300 < 400$ , so $A$ stays. What breaks truthfulness is a lower slot cheap enough to be worth the lost traffic, so the click gap matters as much as the bid gap.

Work it out

VCG payments, then the GSP gap

Compute $A$ ‘s VCG payment as displaced welfare. Others’ best welfare without $A$ : give slot 1 to $B$ (600) and slot 2 to $C$ (320), total $920$ . Others’ welfare when $A$ takes slot 1: only $B$ in slot 2, $480$ . Payment $= 920 - 480 = 440$ . Likewise $B$ pays $1320 - 1000 = 320$ .

Now GSP under truthful bids: slot 1’s price is the next bid, $B = 6$ , times slot 1’s $100$ clicks, so $600$ , which exceeds $A$ ‘s VCG payment of $440$ . Test the deviation. Staying at slot 1 nets $A$ its value less that price, $1000 - 600 = 400$ . Shading to just under $6$ drops $A$ into slot 2, where it pays $C$ ‘s bid: $80(10-4) = 480$ . Since $480 > 400$ , $A$ deviates, so truthful bidding is not stable. A lowest locally envy-free GSP equilibrium, under the standard assumptions, has bids that make each advertiser content with its slot and price and reproduces the VCG numbers.

Key idea

Position auctions rank advertisers and charge by slot. VCG makes honesty weakly dominant by pricing externalities; generalized second price is not truthful. Under the standard model, its lowest locally envy-free equilibrium matches VCG, but arbitrary GSP bids need not.

Check yourself

Check yourselfapply

Under GSP with truthful bids (values 10, 6, 4), why does the top advertiser end up paying more than under VCG?

Check yourselfanalyse

Is bidding your true per-click value a dominant strategy under GSP with multiple slots?

Check yourselfbrings back: VCG

Given GSP is not truthful, what can be said about its lowest locally envy-free equilibrium in the standard model?

Sources

Edelman, B., Ostrovsky, M., and Schwarz, M. (2007). Internet advertising and the generalized second-price auction. American Economic Review, 97(1), 242-259.
Ausubel, L. M., and Milgrom, P. (2004). Ascending auctions with package bidding. Frontiers of Theoretical Economics, 1(1).