What does VCG Auctions and Community Incentives conclude, in numbers, about “Position Auctions: Equilibria of the Generalized Second-Price Auction and VCG”?
Answer: 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.
Scope of the numbers: Marked boxes separate published evidence, runnable Python calculations (16 programs), classical sources and the author's models and hypotheses; all data in the book are fictional or simulated.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 1000, 1355, 200, 300, 605, 920
| 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 |
Key formula
Show the full program
# 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}")Single source and citation
Fan, Y. (2026). Mechanism Design, Vickrey–Clarke–Groves Auctions and Incentive-Compatible Community Engineering (Version 1.0.0), Chapter 3: Position Auctions: Equilibria of the Generalized Second-Price Auction and VCG. 5D Library. https://doi.org/10.5281/zenodo.23836274
DOI: 10.5281/zenodo.23836274 · Read the monograph · 5DL-B-050 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026050,
author = {Fan, Yafu},
title = {Mechanism Design, Vickrey–Clarke–Groves Auctions and Incentive-Compatible Community Engineering},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
doi = {10.5281/zenodo.23836274},
url = {https://doi.org/10.5281/zenodo.23836274}
}Other chapter answers in this book
- Chapter 1 · The Revelation Principle, Incentive Compatibility and Commitment
- Chapter 2 · Multi-Item VCG: Pricing Externalities, the Core and False-Name Bids
- Chapter 4 · Myerson's Optimal Auction: Virtual Values, Reserve Prices and Ironing
- Chapter 5 · Impossibility: Hurwicz, Green–Laffont and Roberts
- Chapter 6 · Community Incentives: Points Inflation, Badges and Sybil Attacks
- Chapter 7 · Reading the Classics: One Reward, Settled Shares and "Rewards Reliable, Punishments Certain"
- Chapter 8 · Practice and Pre-Registered Testing