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 | mu0: 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, n2, mu = 0: tax/agent 0.1168, welfare 0.5642, taxes/welfare 41.4%
(C) taxes rebated equally, n3, others report (0.9, -1.0), my value 0.2:
reporting +0.10 instead of +0.20 gains 0.033

Key formula

\[t_i(\hat v) = h_i(\hat v_{-i}) - \sum_{j \ne i} \hat v_j(x^*(\hat v)) .\]
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