5D Library › Mechanism Design, Vickrey–Clarke–Groves Auctions and Incentive-Compatible Community Engineering · 中文

Chapter 3 Position Auctions: Equilibria of the Generalized Second-Price Auction and VCG

Position auctions

Beside a page of search results there are KK advertising slots; the higher the slot, the more clicks it gets. The standard model assumes that slot kk brings αk\alpha_k clicks per period (α1>α2>⋯>αK\alpha_1 > \alpha_2 > \cdots > \alpha_K), whoever’s advertisement it is; advertiser ii values each click at viv_i, his private information. Each advertiser wants at most one slot.

The generalized second-price (GSP) auction: each advertiser bids bib_i per click; bids are ranked from highest to lowest; the advertiser in position kk pays, per click, the bid of the advertiser in position k+1k+1. With one slot this is Vickrey’s second-price auction; with several it looks like the natural generalisation, which is why it is often mistakenly believed to make truth-telling dominant too. In practice ranks and prices are also multiplied by an ad-quality or predicted click-rate factor; assuming separable click rates (ad ii in slot kk gets αkei\alpha_k e_i clicks), this changes the notation, not the results below (Varian 2007).

VCG for positions: rank by bid (as in GSP), but the advertiser in position kk pays for the clicks he takes from everyone below: if he were absent, everyone from position k+1k+1 down would move up one slot. Numbering bidders by value from highest to lowest, the total payment for position kk is

TkVCG=∑j≥kvj+1(αj−αj+1),αK+1=0.T_k^{\text{VCG}} = \sum_{j \ge k} v_{j+1}\,(\alpha_j – \alpha_{j+1}), \qquad \alpha_{K+1} = 0 .

Truth-telling is not an equilibrium

The program below has two slots (100 and 60 clicks per period) and three bidders with values per click 10, 8 and 5. Under VCG the advertiser in slot 2 pays 5 per click (he displaces bidder 3’s 60 clicks), and the one in slot 1 pays (8×40+5×60)/100=6.2(8 \times 40 + 5 \times 60)/100 = 6.2 per click, for total revenue 920. In GSP, if everyone bids his value, bidder 1 pays 8 per click and earns 100×(10−8)=200100 \times (10 – 8) = 200; if he lowers his bid to between 5 and 8 (say 6), he drops to slot 2, pays only 5 per click and earns 60×(10−5)=30060 \times (10 – 5) = 300. So truth-telling is not a dominant strategy in GSP, and here it is not even a Nash equilibrium.

The program then enumerates every pure-strategy Nash equilibrium on a bid grid from 0 to 12 with step 0.25 (493=117,64949^3 = 117{,}649 bid profiles) and, following the definitions of Edelman, Ostrovsky and Schwarz (Edelman et al. 2007) and Varian (Varian 2007), selects the locally envy-free (in Varian’s terms, symmetric Nash) equilibria: no one wants to swap places with the advertiser one position above at the price that advertiser now pays. In this example this means

αk(vk−pk)≥αk−1(vk−pk−1),\alpha_k (v_k – p_k) \ge \alpha_{k-1}(v_k – p_{k-1}),

where pkp_k is the price per click in position kk; the losing bidder must likewise not want to move into slot 2 at its price.

Calculation

# Chapter 3. Position auction with 2 slots (clicks 100 and 60) and 3 bidders with
# values per click 10, 8, 5. GSP: rank by bid, the slot-k winner pays the (k+1)-th bid
# per click. VCG: each winner pays the click-externality he imposes. We enumerate all
# pure Nash equilibria of GSP on a bid grid 0..12 (step 0.25; ties go to the lower
# index), check truthful bidding, and compare revenues with the locally envy-free
# ("symmetric") equilibria of Edelman-Ostrovsky-Schwarz and Varian.
import itertools

ALPHA, V = (100.0, 60.0), (10.0, 8.0, 5.0)
GRID = [x / 4 for x in range(49)]

def rank(b):
    return sorted(range(3), key=lambda i: (-b[i], i))

def gsp(b):
    r = rank(b); u = [0.0] * 3; rev = 0.0
    for k in range(2):
        i, price = r[k], b[r[k + 1]]
        u[i] = ALPHA[k] * (V[i] - price); rev += ALPHA[k] * price
    return u, rev, r

def best_response_value(i, b):
    others = sorted(((b[j], j) for j in range(3) if j != i), key=lambda t: (-t[0], t[1]))
    best = 0.0                                           # option: lose (bid 0 loses
    for k in range(2):                                   # unless all bid 0; ignore)
        above = others[k - 1] if k > 0 else None         # need to beat others[k]
        target = others[k]
        bids = [g for g in GRID if (g > target[0] or (g == target[0] and i < target[1]))
                and (above is None or g < above[0] or (g == above[0] and i > above[1]))]
        if bids:
            best = max(best, ALPHA[k] * (V[i] - target[0]))
    return best

def vcg():
    p2 = V[2]                                            # slot 2 displaces bidder 3
    p1 = (V[1] * (ALPHA[0] - ALPHA[1]) + p2 * ALPHA[1]) / ALPHA[0]
    return p1, p2

if __name__ == "__main__":
    p1, p2 = vcg()
    print(f"VCG prices per click: slot 1 {p1:.2f}, slot 2 {p2:.2f};"
          f" revenue {ALPHA[0] * p1 + ALPHA[1] * p2:.0f}")
    u, rev, _ = gsp(V)
    print(f"GSP, all bid their values: revenue {rev:.0f}; bidder 1 earns {u[0]:.0f},"
          f" bidding 6 (slot 2) {ALPHA[1] * (V[0] - V[2]):.0f}")
    ne = []
    for b in itertools.product(GRID, repeat=3):
        u, rev, r = gsp(b)
        if all(u[i] >= best_response_value(i, b) - 1e-9 for i in range(3)):
            ne.append((b, rev, r))
    eff = [x for x in ne if x[2][:2] == [0, 1]]
    noover = [x for x in eff if all(x[0][i] <= V[i] for i in range(3))]
    def envy_free(b, r):
        price = [b[r[1]], b[r[2]]]                     # no one envies the slot above
        return (ALPHA[1] * (V[r[1]] - price[1]) >= ALPHA[0] * (V[r[1]] - price[0]) - 1e-9
                and 0.0 >= ALPHA[1] * (V[r[2]] - price[1]) - 1e-9)
    sne = [x for x in noover if envy_free(x[0], x[2])]
    print(f"pure Nash equilibria on the grid: {len(ne):,}; truthful profile among them:"
          f" {any(x[0] == V for x in ne)}")
    for lab, s in (("all equilibria", ne), ("efficient ranking", eff),
                   ("efficient, no overbidding", noover),
                   ("locally envy-free (SNE), no overbidding", sne)):
        rv = [x[1] for x in s]
        print(f"  {lab:40s} {len(s):6,d}   revenue {min(rv):6.0f} .. {max(rv):6.0f}")
    lo = min(sne, key=lambda x: x[1])
    print(f"  lowest grid SNE: bids {lo[0]}, revenue {lo[1]:.0f}"
          f" (VCG price {p1:.2f} is off the grid)")
    lo1 = (V[1] * (ALPHA[0] - ALPHA[1]) + V[2] * ALPHA[1]) / ALPHA[0]
    hi1 = (V[0] * (ALPHA[0] - ALPHA[1]) + V[2] * ALPHA[1]) / ALPHA[0]
    print(f"  SNE bounds (Varian), slot-2 price {V[2]:.0f}: slot-1 price {lo1:.2f} .."
          f" {hi1:.2f}, revenue {ALPHA[0] * lo1 + ALPHA[1] * V[2]:.0f} .."
          f" {ALPHA[0] * hi1 + ALPHA[1] * V[2]:.0f}")
# VCG prices per click: slot 1 6.20, slot 2 5.00; revenue 920
# GSP, all bid their values: revenue 1100; bidder 1 earns 200, bidding 6 (slot 2) 300
# pure Nash equilibria on the grid: 4,307; truthful profile among them: False
#   all equilibria                            4,307   revenue    605 ..   1355
#   efficient ranking                         3,106   revenue    605 ..   1355
#   efficient, no overbidding                 1,162   revenue    605 ..   1000
#   locally envy-free (SNE), no overbidding      58   revenue    925 ..   1000
#   lowest grid SNE: bids (6.25, 6.25, 5.0), revenue 925 (VCG price 6.20 is off the grid)
#   SNE bounds (Varian), slot-2 price 5: slot-1 price 6.20 .. 7.00, revenue 920 .. 1000

There are 4,307 pure-strategy Nash equilibria on the grid; in 1,201 of them the ranking is not efficient (a higher-value bidder sits below a lower-value one), and equilibrium revenue runs from 605 to 1,355. Excluding bids above one’s own value, efficient equilibria earn from 605 to 1,000. Adding the locally envy-free condition leaves 58, earning from 925 to 1,000. In theory, in locally envy-free equilibria the slot-2 price is 5 and the slot-1 price lies between 6.20 and 7.00, so revenue lies between 920 and 1,000: the lower bound is exactly the VCG revenue; 6.20 is not on the grid, so the lowest grid equilibrium earns 925.

Evidence

Edelman, Ostrovsky and Schwarz proved (Edelman et al. 2007) that truth-telling is generally not an equilibrium of GSP; that there is a locally envy-free equilibrium whose allocation and payments are exactly the VCG outcome; and that in every locally envy-free equilibrium the auctioneer’s revenue is at least the VCG revenue. They also proved that the corresponding “generalized English auction” (prices rise and bidders choose when to drop out) has (within the class of strategies they consider) a unique perfect Bayesian equilibrium, with the same outcome as VCG. Varian independently characterised symmetric Nash equilibria by inequalities and derived bounds on revenue (Varian 2007). Fukuda and co-authors compared GSP and VCG in the laboratory and found similar revenue and efficiency under the two rules, in line with theory (Fukuda et al. 2013).

Random instances: comparing revenue

That was one example. The next program generates 20,000 random instances (6 bidders, 4 slots, click rates falling as dk−1d^{k-1}, values uniform on [0,1]) and computes the VCG revenue (that is, the lowest locally envy-free equilibrium), the highest locally envy-free revenue (with the first loser bidding his value; Varian’s recursion pkαk=vk(αk−αk+1)+pk+1αk+1p_k\alpha_k = v_k(\alpha_k – \alpha_{k+1}) + p_{k+1}\alpha_{k+1}) and the GSP revenue when everyone bids truthfully, and checks whether truth-telling is an equilibrium. It also checks the recursion independently against the VCG formula above.

Calculation

# Chapter 3. Random position auctions: n = 6 bidders, K = 4 slots, click rates
# alpha_k = d^(k-1), values per click i.i.d. U[0,1]. Per instance we compute
#   VCG revenue  (= revenue of the lowest locally envy-free equilibrium of GSP, EOS 2007)
#   upper SNE    (Varian 2007: p_k a_k = v_k (a_k - a_k+1) + p_k+1 a_k+1, p_K = v_K+1)
#   GSP with everyone bidding his value, and whether that profile is a Nash equilibrium.
import math, random, statistics

def instance(rng, n=6, K=4, d=0.7):
    a = [d ** k for k in range(K)] + [0.0]
    v = sorted((rng.random() for _ in range(n)), reverse=True)
    lo = [0.0] * (K + 1); hi = [0.0] * (K + 1)
    lo[K - 1] = hi[K - 1] = v[K]                       # price per click of slot K
    for k in range(K - 2, -1, -1):
        lo[k] = (v[k + 1] * (a[k] - a[k + 1]) + lo[k + 1] * a[k + 1]) / a[k]
        hi[k] = (v[k] * (a[k] - a[k + 1]) + hi[k + 1] * a[k + 1]) / a[k]
    vcg = math.fsum(a[k] * lo[k] for k in range(K))
    up = math.fsum(a[k] * hi[k] for k in range(K))
    truth = math.fsum(a[k] * v[k + 1] for k in range(K))
    # truthful GSP: can bidder k (slot k) gain by moving to a lower slot j > k?
    dev = 0
    for k in range(K):
        u = a[k] * (v[k] - v[k + 1])
        if any(a[j] * (v[k] - v[j + 1]) > u + 1e-12 for j in range(k + 1, K)):
            dev += 1
    # direct VCG formula as a check: slot k pays sum_j>=k v_j+1 (a_j - a_j+1)
    chk = math.fsum(math.fsum(v[j + 1] * (a[j] - a[j + 1]) for j in range(k, K))
                    for k in range(K))
    return vcg, up, truth, dev, chk

if __name__ == "__main__":
    rng = random.Random(2007)
    for d in (0.9, 0.7, 0.5):
        R = [instance(rng, d=d) for _ in range(20000)]
        assert all(abs(r[0] - r[4]) < 1e-9 for r in R)
        print(f"click decay d = {d}: 20,000 instances")
        print(f"  mean revenue: VCG {statistics.fmean(r[0] for r in R):.4f},"
              f" upper SNE {statistics.fmean(r[1] for r in R):.4f},"
              f" GSP truthful {statistics.fmean(r[2] for r in R):.4f}")
        print(f"  upper SNE / VCG {statistics.fmean(r[1] / r[0] for r in R):.3f};"
              f" truthful GSP / VCG {statistics.fmean(r[2] / r[0] for r in R):.3f};"
              f" min truthful/VCG {min(r[2] / r[0] for r in R):.3f}")
        print(f"  truthful bidding is a GSP equilibrium in"
              f" {sum(r[3] == 0 for r in R) / len(R):.1%} of instances;"
              f" mean deviators {statistics.fmean(r[3] for r in R):.2f}")
# click decay d = 0.9: 20,000 instances
#   mean revenue: VCG 1.1116, upper SNE 1.1866, GSP truthful 1.7848
#   upper SNE / VCG 1.100; truthful GSP / VCG 1.857; min truthful/VCG 1.012
#   truthful bidding is a GSP equilibrium in 0.0% of instances; mean deviators 2.86
# click decay d = 0.7: 20,000 instances
#   mean revenue: VCG 1.0331, upper SNE 1.1993, GSP truthful 1.4195
#   upper SNE / VCG 1.201; truthful GSP / VCG 1.436; min truthful/VCG 1.007
#   truthful bidding is a GSP equilibrium in 0.2% of instances; mean deviators 2.33
# click decay d = 0.5: 20,000 instances
#   mean revenue: VCG 0.9478, upper SNE 1.1445, GSP truthful 1.1444
#   upper SNE / VCG 1.244; truthful GSP / VCG 1.225; min truthful/VCG 1.003
#   truthful bidding is a GSP equilibrium in 4.2% of instances; mean deviators 1.63

Three conclusions. First, truth-telling is almost never an equilibrium of GSP: when click rates fall slowly (d=0.9d = 0.9), in none of 20,000 instances; even with d=0.5d = 0.5, in only 4.2 %; on average 1.63–2.86 bidders want to move down. Second, the range of locally envy-free revenue is wide: the highest is on average 10.0–24.4 % above VCG. Third, “GSP with everyone bidding truthfully” always earns more than VCG (at least 0.3 % more), on average 85.7 % more with d=0.9d = 0.9; but this is a non-equilibrium reference point, and using it to show that “GSP earns more than VCG” is an invalid comparison.

Left: distribution of revenue across pure Nash equilibria of GSP in the example (grey), the locally envy-free revenue range (shaded, 920–1,000), the VCG revenue (solid) and revenue when everyone bids truthfully (dashed). Right: in random instances, mean revenue of the highest locally envy-free equilibrium and of “truthful GSP” (VCG = 1) as the click-rate decay varies.

Why platforms used GSP

If, in locally envy-free equilibria, GSP earns at most “VCG or somewhat more”, why did platforms use it for so long? Common explanations are that it is easy to explain to advertisers (“you pay the next bid”); that it was adopted before VCG and switching is costly; and that if equilibrium selection favours higher revenue it may earn more than VCG (Edelman et al. 2007; Varian and Harris 2014). These explanations are mostly about history and organisation, not theorems. In September 2019 Google announced that programmatic display advertising in Ad Manager would move to a unified first-price auction (Bigler 2019); the change concerned display advertising, and the announcement says nothing about search advertising, so the book records it as a note and draws no inference for search.

Note

Equilibrium selection. Local envy-freeness is an equilibrium refinement, not a state that participants must reach. The example has 4,307 Nash equilibria, of which only 58 are locally envy-free. Book 32 discussed dynamics in learning and recommendation; its conclusions are a reminder that where a learning process in repeated bidding comes to rest depends on the learning rule. When saying “GSP revenue is at least VCG revenue”, one should add “in locally envy-free equilibria”.

Hypothesis · not established · Ranking auctions in creator placement

The author’s hypothesis (not established): in creator-ranking recommendations priced at “the next bid”, bids converge with experience to the lower bound of locally envy-free equilibria (the VCG outcome), not to truthful bids. What would show it wrong: in pre-registered repeated bidding on an independent platform or in the laboratory, the mean distance of bids from the VCG lower bound in the second half of rounds is no smaller than in the first half, or the share of truthful bids rises over rounds. Chapter 8’s experiment can test the latter case.

Chapter summary

In position auctions GSP charges the next bid and looks like a second-price auction, but truth-telling is generally not an equilibrium: in the example, the top bidder raises his payoff from 200 to 300 by dropping to slot 2, and in random instances truth-telling is an equilibrium in only 0.0–4.2 % of cases. Locally envy-free equilibria earn between the VCG revenue and an upper bound (920 to 1,000 in the example), the lowest reproducing the VCG outcome exactly; “GSP earns at least as much as VCG” is guaranteed only for this class of equilibria; other Nash equilibria can earn as little as 605, or more than VCG (up to 1,355). Laboratory evidence shows similar revenue and efficiency under the two rules.

References

Bigler, Jason. 2019. Rolling out First Price Auctions to Google Ad Manager Partners. Google, The Keyword (company blog), 5 September 2019.
Edelman, Benjamin, Michael Ostrovsky, and Michael Schwarz. 2007. “Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords.” American Economic Review 97 (1): 242–59.
Fukuda, Emiko, Yoshio Kamijo, Ai Takeuchi, Michiharu Masui, and Yukihiko Funaki. 2013. “Theoretical and Experimental Investigations of the Performance of Keyword Auction Mechanisms.” RAND Journal of Economics 44 (3): 438–61. https://doi.org/10.1111/1756-2171.12026.
Varian, Hal R. 2007. “Position Auctions.” International Journal of Industrial Organization 25 (6): 1163–78.
Varian, Hal R., and Christopher Harris. 2014. “The VCG Auction in Theory and Practice.” American Economic Review 104 (5): 442–45.

Fan, Y. (2026). Mechanism Design, Vickrey–Clarke–Groves Auctions and Incentive-Compatible Community Engineering: From Myerson's Optimal Auction and the Hurwicz Impossibility Theorem to Sybil-Resistant Reputation Games, Read Beside Classical Legalist Treatises on Rewards and Incentives [机制设计、维克里—克拉克—格罗夫斯(VCG)拍卖与数字社群激励相容工程] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23836274 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).