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

Chapter 5 Impossibility: Hurwicz, Green–Laffont and Roberts

Four desirable properties

A mechanism is often asked to satisfy four properties at once: efficiency (the outcome maximises total welfare or, in an exchange economy, is Pareto efficient); incentive compatibility (truth-telling is optimal, in the dominant-strategy or the Bayesian sense); individual rationality (no one is worse off for taking part); and budget balance (payments sum to zero, so the designer neither subsidises nor keeps money). Several famous theorems of mechanism design say that in certain environments the four cannot all be had. They are often reduced to slogans such as “incentive compatibility is impossible”; this chapter states their conditions one by one and illustrates them by program in the smallest examples.

Hurwicz 1972: exchange economies

In his 1972 paper Hurwicz introduced the concept of “incentive compatibility” and proved the first result of this kind (Hurwicz 1972). Its content: in a pure exchange economy with two people and two goods and classical preferences (continuous, monotone, convex), there is no mechanism under which truthful reporting of preferences is an equilibrium at every preference profile and whose outcome is always Pareto efficient and individually rational. Hurwicz required that “if the others report truthfully, reporting truthfully is a best response” at every profile; with private values, since any report of the others equals the truthful report of some type, this is equivalent to dominant-strategy incentive compatibility.

The competitive-equilibrium (Walrasian) mechanism conveys the intuition: let the two report their preferences and compute the competitive equilibrium for the reports. With only two people each affects prices, like a monopolist seller: understating how much one is willing to sell raises the price of one’s own good. The program below takes endowments (0.7, 0.2) and (0.3, 0.8) and Cobb–Douglas utilities ui=ailn⁡x+(1−ai)ln⁡yu_i = a_i\ln x + (1-a_i)\ln y; it first examines the manipulation when both have a=0.5a = 0.5, then checks three properties of three mechanisms on 300 random preference profiles.

Calculation

# Chapter 5. Hurwicz (1972) in the smallest case: two agents, two goods, endowments
# e1 = (0.7, 0.2), e2 = (0.3, 0.8), Cobb-Douglas utilities u_i = a_i ln x + (1-a_i) ln y.
# Mechanism W ("Walrasian"): agents report a_i, the outcome is the competitive
# equilibrium for the reports. We test three properties on 300 random profiles:
#   SP: no agent gains by misreporting (grid of 99 reports);
#   PE: the allocation is Pareto efficient for the TRUE preferences (equal MRS);
#   IR: each agent weakly prefers the outcome to his endowment.
# and compare with two trivial mechanisms: no trade, and "agent 1 takes everything".
import math, random

E1, E2 = (0.7, 0.2), (0.3, 0.8)

def walras(r1, r2):
    p = (1 - r1 * E1[0] - r2 * E2[0]) / (r1 * E1[1] + r2 * E2[1])    # p = py / px
    m1, m2 = E1[0] + p * E1[1], E2[0] + p * E2[1]
    return (r1 * m1, (1 - r1) * m1 / p), (r2 * m2, (1 - r2) * m2 / p)

def no_trade(r1, r2):
    return E1, E2

def dictator(r1, r2):
    return (1.0, 1.0), (0.0, 0.0)

def u(a, b):
    if b[0] <= 0 or b[1] <= 0:
        return -math.inf
    return a * math.log(b[0]) + (1 - a) * math.log(b[1])

def mrs(a, b):
    return a * b[1] / ((1 - a) * b[0])

GRID = [k / 100 for k in range(1, 100)]

def check(mech, prof):
    sp = pe = ir = 0.0
    for a1, a2 in prof:
        b1, b2 = mech(a1, a2)
        g1 = max(u(a1, mech(r, a2)[0]) - u(a1, b1) for r in GRID)
        g2 = max(u(a2, mech(a1, r)[1]) - u(a2, b2) for r in GRID)
        sp = max(sp, g1 if g1 < math.inf else 0, g2 if g2 < math.inf else 0)
        if min(b1 + b2) > 0:
            pe = max(pe, abs(math.log(mrs(a1, b1) / mrs(a2, b2))))
        ir = max(ir, u(a1, E1) - u(a1, b1), u(a2, E2) - u(a2, b2))
    return sp, pe, ir

if __name__ == "__main__":
    a1 = a2 = 0.5
    b1, b2 = walras(a1, a2)
    best = max(GRID, key=lambda r: u(a1, walras(r, a2)[0]))
    c1, c2 = walras(best, a2)
    print(f"truthful: agent 1 gets ({b1[0]:.3f}, {b1[1]:.3f}), utility {u(a1, b1):+.4f};"
          f" MRS gap {abs(math.log(mrs(a1, b1) / mrs(a2, b2))):.3f}")
    print(f"agent 1 reports a = {best:.2f}: gets ({c1[0]:.3f}, {c1[1]:.3f}), utility"
          f" {u(a1, c1):+.4f} (gain {u(a1, c1) - u(a1, b1):+.4f})")
    print(f"  then true MRS: agent 1 {mrs(a1, c1):.3f}, agent 2 {mrs(a2, c2):.3f}"
          " -> not Pareto efficient")
    rng = random.Random(1972)
    prof = [(rng.uniform(0.1, 0.9), rng.uniform(0.1, 0.9)) for _ in range(300)]
    print("300 random profiles. Largest gain from lying (SP), largest MRS gap (PE),")
    print("largest utility loss against the endowment (IR); 0 means the property holds")
    for name, m in (("Walrasian", walras), ("no trade", no_trade),
                    ("agent 1 takes all", dictator)):
        sp, pe, ir = check(m, prof)
        ir_s = "inf" if ir == math.inf else f"{ir:.4f}"
        pe_s = "corner" if m is dictator else f"{pe:.4f}"
        print(f"  {name:18s} SP {sp:.4f}   PE {pe_s:>7s}   IR {ir_s:>7s}")
# truthful: agent 1 gets (0.450, 0.450), utility -0.7985; MRS gap 0.000
# agent 1 reports a = 0.66: gets (0.558, 0.394), utility -0.7567 (gain +0.0418)
#   then true MRS: agent 1 0.706, agent 2 1.371 -> not Pareto efficient
# 300 random profiles. Largest gain from lying (SP), largest MRS gap (PE),
# largest utility loss against the endowment (IR); 0 means the property holds
#   Walrasian          SP 0.1692   PE  0.0000   IR  0.0000
#   no trade           SP 0.0000   PE  6.0588   IR  0.0000
#   agent 1 takes all  SP 0.0000   PE  corner   IR     inf

Reporting truthfully, participant 1 gets (0.450, 0.450), and the two marginal rates of substitution are equal (Pareto efficiency). His endowment is mainly good x. If he reports a=0.66a = 0.66 (exaggerating his liking for x, that is, selling less of it), the relative price of x computed from the reports rises; he gets (0.558, 0.394) and his utility rises by 0.0418; but at the true preferences the two marginal rates of substitution are now 0.706 and 1.371, no longer equal, and the allocation is not Pareto efficient. Over 300 random profiles the Walrasian mechanism is efficient and individually rational, but the largest gain from lying is 0.1692; the “no trade” mechanism is strategy-proof and individually rational but not efficient (the log ratio of marginal rates of substitution differs by up to 6.06); “participant 1 takes everything” is strategy-proof and efficient (a corner allocation) but not individually rational for participant 2. Each of the three lacks one property, exactly the three that Hurwicz’s theorem says cannot all be had.

Zhou took the result one step further: in standard two-person exchange economies with any number of goods, every efficient and strategy-proof mechanism must be “inversely dictatorial”, that is, someone always gets nothing; no individual-rationality condition is needed (Zhou 1991). Hurwicz’s theorem is therefore not a general slogan about “incentives” but a precise statement about exchange economies with few people, each of whom affects prices; when there are many participants, each with little influence on prices, the gains from manipulation also shrink, which is a different kind of result.

Green and Laffont 1977: uniqueness of Groves mechanisms

Chapter 2 showed that Groves mechanisms (of which VCG is one) achieve efficiency and dominant-strategy incentive compatibility in quasi-linear environments. Green and Laffont proved the converse: if each person’s valuation can be any real-valued function on the set of alternatives (an unrestricted domain), then every efficient, dominant-strategy incentive-compatible mechanism is a Groves mechanism, that is, payments must have the form

ti(v̂)=hi(v̂−i)−∑j≠iv̂j(x*(v̂)).t_i(\hat v) = h_i(\hat v_{-i}) – \sum_{j \ne i} \hat v_j(x^*(\hat v)) .

Holmström extended this uniqueness to “smoothly connected” restricted domains (Holmström 1979). The consequence of uniqueness is that if no Groves mechanism balances the budget, efficiency and dominant-strategy incentive compatibility are incompatible with budget balance. Green and Laffont’s 1979 monograph and Walker’s 1980 paper proved this (Green and Laffont 1979; Walker 1980).

Consider two people deciding whether to build a public project; θi\theta_i is participant ii’s net value (after his cost share), and the project is built when θ1+θ2≥0\theta_1 + \theta_2 \ge 0 (write d*=𝟏{θ1+θ2≥0}d^* = \mathbf 1\{\theta_1 + \theta_2 \ge 0\}). To match program p08, this section switches to transfer notation, the money the mechanism gives each participant (the negative of the payment tit_i above, still writing hih_i for −hi-h_i): τi=∑j≠iθjd*+hi(θ−i)\tau_i = \sum_{j \ne i}\theta_j d^* + h_i(\theta_{-i}). Budget balance requires τ1+τ2=0\tau_1 + \tau_2 = 0, that is,

h1(θ2)+h2(θ1)=−(θ1+θ2)𝟏{θ1+θ2≥0}.h_1(\theta_2) + h_2(\theta_1) = -(\theta_1 + \theta_2)\,\mathbf 1\{\theta_1 + \theta_2 \ge 0\}.

The left side is a sum of two functions of one variable each, so its “mixed difference” g(a,a′)−g(a,b′)−g(b,a′)+g(b,b′)g(a,a') – g(a,b') – g(b,a') + g(b,b') over any four profiles (a,a′),(a,b′),(b,a′),(b,b′)(a, a'), (a, b'), (b, a'), (b, b') must vanish; the right side’s mixed difference over (±1,±1)(\pm1, \pm1) equals 2. So no Groves mechanism balances the budget.

Calculation

# 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}")
# (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

Part (A) of the program confirms the mixed difference of 2 and finds, on the grid {−2,…,2}2\{-2,\dots,2\}^2, the Groves mechanism closest to budget balance: the smallest root-mean-square imbalance is 0.551, and the worst profile is off by 1.200. Part (B) computes the Clarke pivot taxes (each “pivotal” participant pays the loss he imposes on the others, and this money must be “burnt” or handed to an outsider). It is often said that “with more people, Clarke taxes become small”; this needs qualifying. When valuations have mean zero (the project is marginal), the average tax per person falls from 0.1171 to 0.0141, but taxes as a share of total welfare do not fall and stay at about 42–50 % (with two people the closed-form value is 41.4 %, the simulated 41.8 %); only when valuations have a positive mean (μ=0.2\mu = 0.2), so that the project is clearly worth doing, does the share fall from 28.63 % to 0.11 % with 200 people. Part (C) shows why the taxes cannot simply be returned equally (Book 27 already explained that Clarke taxes cannot be returned and the budget cannot balance; this is a numerical counterexample): if three people share the taxes equally, participant 1’s report affects his own share, and by reporting +0.10 instead of +0.20 he gains 0.033; incentive compatibility is broken.

Evidence

Relaxing to Bayesian incentive compatibility changes the conclusion: d’Aspremont and Gérard-Varet constructed efficient, Bayesian incentive-compatible mechanisms with a balanced budget (often called the AGV mechanism) (d’Aspremont and Gérard-Varet 1979), although they do not guarantee that everyone is willing to participate. Adding individual rationality gives the bilateral-trade impossibility of the Myerson–Satterthwaite theorem (Myerson and Satterthwaite 1983) (Book 27). Which of “efficiency, incentive compatibility, individual rationality and budget balance” can be given up therefore depends on whether incentive compatibility is meant in the dominant-strategy or the Bayesian sense.

Roberts 1979: only affine maximisers can be implemented

The results so far take efficiency as the goal. If the goal is some other social choice function (for instance a “max-min” rule that protects the worst-off), can payments be found to implement it in dominant strategies? Roberts proved that if there are at least three alternatives, the domain of valuations is unrestricted and the rule’s range is all alternatives, then every social choice function implementable in dominant strategies is an affine maximiser,

f(v)∈arg⁡maxa[∑iwivi(a)+ca],wi≥0,f(v) \in \arg\max_a \Big[\sum_i w_i v_i(a) + c_a\Big], \qquad w_i \ge 0,

with the wiw_i not all zero, weighting participants, adding a constant to each alternative, and maximising the sum (Roberts 1979). Utilitarianism (all wi=1w_i = 1, ca=0c_a = 0) is a special case. A powerful tool for deciding whether a rule can be implemented is Rochet’s cycle monotonicity: payments making a rule incentive compatible exist if and only if, for each participant and every cycle of types, the sum of value differences is non-negative (Rochet 1987). The simplest, two-cycle case is weak monotonicity: if type vv gets alternative aa and type v′v' gets alternative bb, then v(a)−v(b)≥v′(a)−v′(b)v(a) – v(b) \ge v'(a) – v'(b).

The program below takes three alternatives, three participants and integer values from 0 to 4 for each alternative (125 types per person), and checks three rules: utilitarianism with Clarke payments; an affine maximiser (weights (1, 2, 1), 1.5 added to the second alternative) with weighted Clarke payments; and the max-min rule.

Calculation

# Chapter 5. Roberts (1979): with at least three alternatives and unrestricted
# quasi-linear valuations, the choice rules implementable in dominant strategies are
# affine maximisers, argmax_a sum_i w_i v_i(a) + c_a. Here: 3 alternatives, 3 agents,
# valuations v_i(a) in {0,...,4} (125 types per agent).
#  U  utilitarian (w = 1, c = 0) with Clarke payments
#  F  affine maximiser, w = (1, 2, 1), c = (0, 1.5, 0), weighted Clarke payments
#  E  egalitarian max-min rule, argmax_a min_i v_i(a)
# For U and F we search for profitable misreports; for E we search for violations of
# weak monotonicity, v(a) - v(b) >= v'(a) - v'(b) whenever f(v) = a, f(v') = b; a
# violation means NO payment rule makes E truthful (Rochet 1987, two-cycle case).
import itertools, random

TYPES = list(itertools.product(range(5), repeat=3))

def affine(prof, w, c):
    score = lambda a: sum(wi * v[a] for wi, v in zip(w, prof)) + c[a]
    return max(range(3), key=lambda a: (score(a), -a))

def pay(prof, i, w, c):                            # weighted Clarke payment of agent i
    a = affine(prof, w, c)
    oth = lambda b: sum(w[j] * prof[j][b] for j in range(3) if j != i) + c[b]
    return (max(oth(b) for b in range(3)) - oth(a)) / w[i]

def maxmin(prof):
    return max(range(3), key=lambda a: (min(v[a] for v in prof),
                                        sum(v[a] for v in prof), -a))

if __name__ == "__main__":
    rng = random.Random(1979)
    for name, w, c in (("U utilitarian + Clarke", (1, 1, 1), (0, 0, 0)),
                       ("F affine maximiser", (1, 2, 1), (0, 1.5, 0))):
        worst = 0.0
        for _ in range(1500):
            prof = [rng.choice(TYPES) for _ in range(3)]; i = rng.randrange(3)
            a = affine(prof, w, c); u0 = prof[i][a] - pay(prof, i, w, c)
            for t in TYPES:
                fake = list(prof); fake[i] = t
                worst = max(worst, prof[i][affine(fake, w, c)] - pay(fake, i, w, c) - u0)
        print(f"{name:24s}: 1,500 profiles x 125 misreports, largest gain {worst:+.3f}")
    viol = 0; trials = 0; ex = None
    for _ in range(3000):
        oth = [rng.choice(TYPES) for _ in range(2)]
        v, v2 = rng.choice(TYPES), rng.choice(TYPES)
        a, b = maxmin([v] + oth), maxmin([v2] + oth); trials += 1
        if a != b and v[a] - v[b] < v2[a] - v2[b]:
            viol += 1; ex = ex or (oth, v, v2, a, b)
    print(f"E max-min: weak-monotonicity violations in {viol} of {trials:,} random pairs")
    oth, v, v2, a, b = ex
    print(f"  e.g. others {oth}: type {v} gets {'xyz'[a]}, type {v2} gets {'xyz'[b]};")
    print(f"  v(a) - v(b) = {v[a] - v[b]}, v'(a) - v'(b) = {v2[a] - v2[b]}: a price gap"
          f" p(a) - p(b)\n  would have to be <= {v[a] - v[b]} and >= {v2[a] - v2[b]}")
    u_viol = 0
    for _ in range(3000):
        oth = [rng.choice(TYPES) for _ in range(2)]
        v, v2 = rng.choice(TYPES), rng.choice(TYPES)
        a, b = affine([v] + oth, (1, 1, 1), (0, 0, 0)), affine([v2] + oth, (1, 1, 1),
                                                                (0, 0, 0))
        u_viol += a != b and v[a] - v[b] < v2[a] - v2[b]
    print(f"U utilitarian: weak-monotonicity violations in {u_viol} of 3,000 pairs")
# U utilitarian + Clarke  : 1,500 profiles x 125 misreports, largest gain +0.000
# F affine maximiser      : 1,500 profiles x 125 misreports, largest gain +0.000
# E max-min: weak-monotonicity violations in 16 of 3,000 random pairs
#   e.g. others [(1, 4, 2), (3, 4, 2)]: type (4, 2, 2) gets y, type (1, 0, 1) gets x;
#   v(a) - v(b) = -2, v'(a) - v'(b) = -1: a price gap p(a) - p(b)
#   would have to be <= -2 and >= -1
# U utilitarian: weak-monotonicity violations in 0 of 3,000 pairs

For the first two rules, no misreport pays in 1,500 random profiles with 125 misreports each. The max-min rule violates weak monotonicity in 16 of 3,000 random type pairs. The program’s example: with the other two types fixed, type (4, 2, 2) gets alternative y and type (1, 0, 1) gets alternative x; the former values x 2 more than y, the latter only 1 more, so the type with the stronger preference for x does not get it. For both types to report truthfully, the price difference p(y)−p(x)p(y) – p(x) would have to be at most −2 and at least −1, which is impossible; so no payment scheme whatever can implement the max-min rule truthfully. The utilitarian rule has no violation in the same 3,000 pairs.

Note

The conditions of Roberts’ theorem matter. Both “an unrestricted domain of valuations” and “at least three alternatives” are needed. With only two alternatives any monotone rule can be implemented; in single-parameter environments such as auctions (each person has one number, his value for the object), there are implementable rules that are not affine maximisers, for example Myerson’s optimal auction when bidders are differently distributed with non-linear virtual values (Chapter 4). Note that with identical regular distributions Myerson’s auction, “the highest value gets the object if it is at least the reserve rr”, is itself an affine maximiser (weights 1, and constant rr for the alternative “do not sell”). So Roberts’ theorem does not say “only VCG-like mechanisms are feasible”, but “when valuations are rich enough, the only feasible goals are weighted welfare plus constants for alternatives (affine maximisers)”.

Summary table

Result Environment Properties that cannot all hold What to relax to escape
Hurwicz 1972, Zhou 1991 Two-person exchange economy, classical preferences Dominant-strategy truth-telling, Pareto efficiency, individual rationality (Zhou: efficient + strategy-proof ⇒ inversely dictatorial) Many participants; give up efficiency
Green–Laffont 1977 and sequels Quasi-linear, unrestricted valuations Efficiency, dominant-strategy incentive compatibility, budget balance Bayesian incentive compatibility (AGV)
Myerson–Satterthwaite 1983 (Book 27) Bilateral trade, overlapping value ranges Efficiency, Bayesian incentive compatibility, individual rationality, budget balance Outside subsidy; give up efficiency
Roberts 1979 At least three alternatives, unrestricted valuations Dominant-strategy implementable ⇒ affine maximiser Restricted (e.g. single-parameter) domains
Gibbard–Satterthwaite (Chapter 1) No money, at least three alternatives Strategy-proof ⇒ dictatorial Introduce money; single-peaked preferences

Hypothesis · not established · Budget balance in a community fund

The author’s hypothesis (not established): when a community decides on joint activities by having members report their values, running VCG and collecting Clarke taxes, returning the taxes equally to members makes the gap between members’ reports and independently measured true values significantly larger than when they are not returned. What would show it wrong: in a pre-registered laboratory comparison, a confidence interval for the difference in reporting gaps between the “returned” and “not returned” arms that includes zero. Part (C) is only a counterexample and says nothing about the size of such a gap in a population.

Chapter summary

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.

References

d’Aspremont, Claude, and Louis-André Gérard-Varet. 1979. “Incentives and Incomplete Information.” Journal of Public Economics 11 (1): 25–45.
Green, Jerry R., and Jean-Jacques Laffont. 1979. Incentives in Public Decision-Making. North-Holland.
Holmström, Bengt. 1979. “Groves’ Scheme on Restricted Domains.” Econometrica 47 (5): 1137–44.
Hurwicz, Leonid. 1972. “On Informationally Decentralized Systems.” In Decision and Organization: A Volume in Honor of Jacob Marschak, edited by C. B. McGuire and Roy Radner. North-Holland.
Myerson, Roger B., and Mark A. Satterthwaite. 1983. “Efficient Mechanisms for Bilateral Trading.” Journal of Economic Theory 29 (2): 265–81.
Roberts, Kevin. 1979. “The Characterization of Implementable Choice Rules.” In Aggregation and Revelation of Preferences, edited by Jean-Jacques Laffont. North-Holland.
Rochet, Jean-Charles. 1987. “A Necessary and Sufficient Condition for Rationalizability in a Quasi-Linear Context.” Journal of Mathematical Economics 16 (2): 191–200.
Walker, Mark. 1980. “On the Nonexistence of a Dominant Strategy Mechanism for Making Optimal Public Decisions.” Econometrica 48 (6): 1521–40.
Zhou, Lin. 1991. “Inefficiency of Strategy-Proof Allocation Mechanisms in Pure Exchange Economies.” Social Choice and Welfare 8 (3): 247–54.

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).