What does VCG Auctions and Community Incentives conclude, in numbers, about “Impossibility: Hurwicz, Green–Laffont and Roberts”?
Answer: Hurwicz's 1972 impossibility is a precise statement about two-person exchange economies: truth-telling, efficiency and individual rationality cannot all hold; in the program the Walrasian mechanism, no trade and dictatorship each lack one property. Green and Laffont proved that on an unrestricted domain only Groves mechanisms are efficient and dominant-strategy incentive compatible, and Groves mechanisms cannot balance the budget; Clarke taxes on a marginal project take about 42–50 % of total welfare, and returning them equally breaks incentives. Roberts proved that with at least three alternatives and unrestricted valuations, the only implementable rules are affine maximisers; the max-min rule violates weak monotonicity and no pricing can implement it truthfully.
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: 50
| (A) mixed difference of the required sum over (+-1, +-1): +2 | |
| (it is 0 for every function of the form h_1(theta_2) + h_2(theta_1)) | |
| best additive fit on a 5 x 5 grid: RMS imbalance 0.551, largest 1.200 | |
| (B) Clarke pivot taxes, theta_i ~ N(mu, 1), 20,000 profiles each | |
| n | mu | 0: P(pivot) tax/agent taxes/welfare | mu = 0.2: tax/welfare |
| 2 | | 0.501 0.1171 41.8% | 28.63% |
| 3 | | 0.497 0.1034 44.9% | 28.87% |
| 5 | | 0.466 0.0848 47.8% | 26.39% |
| 10 | | 0.407 0.0608 48.6% | 19.90% |
| 50 | | 0.252 0.0272 47.8% | 5.09% |
| 200 | | 0.158 0.0141 50.2% | 0.11% |
| closed form, n | 2, mu = 0: tax/agent 0.1168, welfare 0.5642, taxes/welfare 41.4% |
| (C) taxes rebated equally, n | 3, others report (0.9, -1.0), my value 0.2: |
| reporting +0.10 instead of +0.20 gains 0.033 |
Key formula
Show the full program
# Chapter 5. Groves mechanisms cannot balance the budget (Green-Laffont line of work).
# Binary public project; agent i's net value theta_i (cost share included), build iff
# sum theta >= 0. Groves transfers to i: t_i = sum_{j != i} theta_j d* + h_i(theta_-i).
# (A) n = 2: budget balance needs h_1(theta_2) + h_2(theta_1) = -(theta_1 + theta_2) d*,
# an additive function of the two types; its mixed difference over four profiles
# must vanish, but the right-hand side's does not. Least squares on a type grid gives
# the smallest possible imbalance.
# (B) Clarke pivot rule: h_i makes each payment the agent's externality; the taxes are
# collected and cannot be returned to the agents without breaking incentives.
import math, random, statistics
def d_star(s):
return 1 if s >= 0 else 0
def g(a, b): # required h_1(b) + h_2(a)
return -(a + b) * d_star(a + b)
def lstsq(rows, y): # normal equations, small ridge
n = len(rows[0])
A = [[sum(r[i] * r[j] for r in rows) + (1e-9 if i == j else 0) for j in range(n)]
+ [sum(r[i] * t for r, t in zip(rows, y))] for i in range(n)]
for c in range(n):
p = max(range(c, n), key=lambda r: abs(A[r][c])); A[c], A[p] = A[p], A[c]
for r in range(n):
if r != c:
f = A[r][c] / A[c][c]; A[r] = [x - f * z for x, z in zip(A[r], A[c])]
return [A[i][n] / A[i][i] for i in range(n)]
if __name__ == "__main__":
md = g(1, -1) - g(1, 1) - g(-1, -1) + g(-1, 1)
print(f"(A) mixed difference of the required sum over (+-1, +-1): {md:+.0f}")
print(" (it is 0 for every function of the form h_1(theta_2) + h_2(theta_1))")
T = [-2, -1, 0, 1, 2]; rows, y = [], []
for a in T:
for b in T:
r = [0.0] * 10; r[T.index(b)] = 1.0; r[5 + T.index(a)] = 1.0
rows.append(r); y.append(g(a, b))
h = lstsq(rows, y)
res = [sum(x * c for x, c in zip(r, h)) - t for r, t in zip(rows, y)]
print(f" best additive fit on a 5 x 5 grid: RMS imbalance"
f" {statistics.fmean(e * e for e in res) ** 0.5:.3f}, largest"
f" {max(abs(e) for e in res):.3f}")
print("(B) Clarke pivot taxes, theta_i ~ N(mu, 1), 20,000 profiles each")
print(" n | mu = 0: P(pivot) tax/agent taxes/welfare | mu = 0.2: tax/welfare")
rng = random.Random(1977)
for n in (2, 3, 5, 10, 50, 200):
row = []
for mu in (0.0, 0.2):
piv = tax = wel = 0.0
for _ in range(20000):
th = [rng.gauss(mu, 1) for _ in range(n)]; s = sum(th); d = d_star(s)
tx = [abs(s - t) if d_star(s - t) != d else 0.0 for t in th]
piv += any(x > 0 for x in tx); tax += sum(tx); wel += s * d
row.append((piv / 20000, tax / 20000 / n, tax / wel))
print(f" {n:4d} | {row[0][0]:16.3f} {row[0][1]:9.4f} {row[0][2]:13.1%} |"
f" {row[1][2]:23.2%}")
nd = statistics.NormalDist(); m = 4000; h = 8.0 / m # closed form check, n = 2
tx = math.fsum((4 if k % 2 else 2) * k * h * nd.pdf(k * h) * nd.cdf(-k * h)
for k in range(1, m)) * h / 3 * 2 # 2 int_0^inf t phi Phi(-t)
wel = math.sqrt(2) * nd.pdf(0.0)
print(f" closed form, n = 2, mu = 0: tax/agent {tx:.4f}, welfare {wel:.4f},"
f" taxes/welfare {2 * tx / wel:.1%}")
# (C) give the taxes back equally: agent 1 now gains from misreporting
others = (0.9, -1.0); best = (0.0, 0.0)
def u1(true, rep):
th = (rep,) + others; s = sum(th); d = d_star(s)
tx = [abs(s - t) if d_star(s - t) != d else 0.0 for t in th]
return true * d - tx[0] + sum(tx) / 3
for k in range(-300, 301):
rep = k / 100; gain = u1(0.2, rep) - u1(0.2, 0.2)
if gain > best[0] + 1e-12:
best = (gain, rep)
print(f"(C) taxes rebated equally, n = 3, others report {others}, my value 0.2:"
f"\n reporting {best[1]:+.2f} instead of +0.20 gains {best[0]:.3f}")Single source and citation
Fan, Y. (2026). Mechanism Design, Vickrey–Clarke–Groves Auctions and Incentive-Compatible Community Engineering (Version 1.0.0), Chapter 5: Impossibility: Hurwicz, Green–Laffont and Roberts. 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 3 · Position Auctions: Equilibria of the Generalized Second-Price Auction and VCG
- Chapter 4 · Myerson's Optimal Auction: Virtual Values, Reserve Prices and Ironing
- 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