关于「不可能性:赫维茨、格林—拉丰与罗伯茨」,《VCG 拍卖与社群激励》给出的定量结论是什么?

结论:赫维茨 1972 年的不可能性是关于两人交换经济的精确结论:说真话、有效与个体理性不能兼得;程序中瓦尔拉斯机制、不交易与独裁各缺一项。格林—拉丰证明在不受限制的估值域上只有格罗夫斯机制有效且占优策略激励相容,而格罗夫斯机制不能预算平衡;克拉克税在边缘项目中约占总福利的 42%—50%,平均退还则破坏激励。罗伯茨证明在至少三个方案、估值不受限制时,可实施的规则只有仿射最大化;最大最小规则违反弱单调性,无论怎样定价都不能如实实施。

数据口径:书中以标注框区分已发表的证据、可运行的 Python 计算(16 段程序)、原典与作者的模型和假说;书中所有数据都是虚构或模拟的。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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

核心公式

\[t_i(\hat v) = h_i(\hat v_{-i}) - \sum_{j \ne i} \hat v_j(x^*(\hat v)) .\]
查看完整验算程序
# 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}")

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《机制设计、维克里—克拉克—格罗夫斯(VCG)拍卖与数字社群激励相容工程》第 5 章「不可能性:赫维茨、格林—拉丰与罗伯茨」(版本 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23836274

DOI: 10.5281/zenodo.23836274 · 阅读本章所在专著 · 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}
}

本书其他章节结论