5D Library › 机制设计、维克里—克拉克—格罗夫斯(VCG)拍卖与数字社群激励相容工程 · English

第五章 不可能性:赫维茨、格林—拉丰与罗伯茨

四个想要的性质

一个机制常被要求同时满足四个性质:效率(结果最大化总福利,或在交换经济中帕累托有效);激励相容(占优策略或贝叶斯意义上说真话最优);个体理性(每个人参与不比不参与差);预算平衡(支付之和为零,设计者既不贴钱也不留钱)。机制设计的几条著名定理说的都是:在某些环境中,这四项不能全部做到。这些定理常被简化为「激励相容不可能」之类的口号;本章逐一写出它们的条件,并用程序在最小的例子中演示。

赫维茨 1972:交换经济

赫维茨在 1972 年的论文中提出了「激励相容」这一概念,并证明了第一个这类不可能性结论 (Hurwicz 1972)。其内容是:在两个人、两种物品的纯交换经济中,偏好为经典型(连续、单调、凸),不存在这样一个机制:如实报告偏好在每一个偏好组合下都构成均衡,同时结果总是帕累托有效且个体理性。赫维茨当时要求的是「在别人如实报告时,自己如实报告是最优反应」对每个偏好组合都成立;在私人价值环境中,由于别人的任意报告都等于某个类型的如实报告,这一要求等价于占优策略激励相容。

这一结论的直觉可以用竞争均衡(瓦尔拉斯)机制说明:让两人报告偏好,按报告计算竞争均衡。只有两个人时,每个人都影响价格,就像一个垄断卖方:少报自己愿意卖出的数量,可以抬高自己物品的价格。下面的程序取禀赋 (0.7, 0.2) 与 (0.3, 0.8)、柯布—道格拉斯效用 ui=ailn⁡x+(1−ai)ln⁡yu_i = a_i\ln x + (1-a_i)\ln y,先看两人都取 a=0.5a = 0.5 时的操纵,再在 300 个随机偏好组合上检查三个机制的三项性质。

推导

# 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

如实报告时,参与者 1 得到 (0.450, 0.450),两人的边际替代率相等(帕累托有效)。他的禀赋主要是物品 x。若他报告 a=0.66a = 0.66(夸大自己对 x 的偏好,也就是少卖出 x),按报告算出的 x 的相对价格上升,他得到 (0.558, 0.394),效用提高 0.0418;但此时按真实偏好,两人的边际替代率分别为 0.706 与 1.371,不再相等,配置不是帕累托有效的。在 300 个随机组合中,瓦尔拉斯机制有效且个体理性,但最大的说谎收益为 0.1692;「不交易」机制防操纵、个体理性,但不有效(边际替代率之比的对数最多相差 6.06);「参与者 1 拿走全部」防操纵且有效(角点配置),但对参与者 2 不是个体理性的。三个机制各缺一项,恰好是赫维茨定理所说的三项不能兼得。

周林把这一结论推进了一步:在两人、多种物品的标准交换经济中,任何有效且防操纵的机制都必定是「逆独裁」的,即总有一个人什么也得不到;这一结论不需要个体理性条件 (Zhou 1991)。赫维茨的定理因此不是关于「激励」的一般口号,而是关于少数人、各自影响价格的交换经济的精确结论;参与者很多、每人对价格影响很小时,操纵的收益也变小,那是另一类结果。

格林—拉丰 1977:格罗夫斯机制的唯一性

第二章说明,格罗夫斯机制(VCG 是其中一个)在拟线性环境中实现效率与占优策略激励相容。格林与拉丰证明了反方向:若每个人的估值可以是备选方案集上的任意实值函数(估值域不受限制),则任何有效且占优策略激励相容的机制都必须是格罗夫斯机制,即支付必须形如

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 1979)。唯一性的后果是:只要格罗夫斯机制都不能预算平衡,有效与占优策略激励相容就与预算平衡不相容。格林与拉丰在 1979 年的专著、沃克在 1980 年的论文中证明了这一点 (Green and Laffont 1979; Walker 1980)。

考虑两人是否兴建一个公共项目,θi\theta_i 是参与者 ii 的净价值(已扣除成本分摊),θ1+θ2≥0\theta_1 + \theta_2 \ge 0 时兴建(记 d*=𝟏{θ1+θ2≥0}d^* = \mathbf 1\{\theta_1 + \theta_2 \ge 0\})。为与程序 p08 对照,这一节改用转移支付记号,即机制给参与者的钱(上式支付 tit_i 的相反数,并把 −hi-h_i 仍记为 hih_i):τi=∑j≠iθjd*+hi(θ−i)\tau_i = \sum_{j \ne i}\theta_j d^* + h_i(\theta_{-i})。预算平衡要求 τ1+τ2=0\tau_1 + \tau_2 = 0,即

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\}.

左边是两个单变量函数之和,它在任意四个组合 (a,a′),(a,b′),(b,a′),(b,b′)(a, a'), (a, b'), (b, a'), (b, b') 上的「混合差分」g(a,a′)−g(a,b′)−g(b,a′)+g(b,b′)g(a,a') – g(a,b') – g(b,a') + g(b,b') 必为零;右边的混合差分在 (±1,±1)(\pm1, \pm1) 上等于 2。所以不存在预算平衡的格罗夫斯机制。

推导

# 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

程序的 (A) 部分验证了混合差分为 2,并在 {−2,…,2}2\{-2,\dots,2\}^2 的网格上求最接近预算平衡的格罗夫斯机制:最小的均方根不平衡为 0.551,最坏的一个组合差 1.200。(B) 部分计算克拉克枢纽税(每个「关键」参与者支付他对其他人造成的损失,这笔钱必须被「烧掉」或交给局外人)。常有人说「人越多,克拉克税越小」,这需要限定:在估值均值为零(项目处于边缘)时,每人平均缴税从 0.1171 降到 0.0141,但税款占总福利的比例并不下降,始终约为 42%—50%(两人时的闭式值为 41.4%,程序的模拟值为 41.8%);只有当估值均值为正(μ=0.2\mu = 0.2)、项目明显值得做时,这一比例才从 28.63% 降到 200 人时的 0.11%。(C) 部分说明为什么税款不能简单地平均退还(第 27 本已说明克拉克税不能退还、预算无法平衡,这里给出一个数值反例):若三人平分税款,参与者 1 的报告会影响自己分到的那一份,他把 +0.20 报成 +0.10 可多得 0.033,激励相容就被破坏了。

证据

放宽到贝叶斯激励相容时,结论改变:达斯普勒蒙与热拉尔—瓦雷构造了有效、贝叶斯激励相容且预算平衡的机制(常称 AGV 机制)(d’Aspremont and Gérard-Varet 1979),但它不保证每个人都愿意参加。再加上个体理性,就得到迈尔森—萨特思韦特定理所说的双边交易不可能性 (Myerson and Satterthwaite 1983)(第 27 本)。所以「效率、激励相容、个体理性、预算平衡」中能放弃哪一项,取决于激励相容是占优策略意义还是贝叶斯意义。

罗伯茨 1979:能实施的规则只有仿射最大化

前面的结论都以「效率」为目标。如果目标不是总福利最大,而是别的社会选择函数(例如照顾最弱者的「最大最小」规则),能否找到支付使它在占优策略中可实施?罗伯茨证明:若备选方案至少有三个、估值域不受限制,并且规则能取到所有方案,那么在占优策略中可实施的社会选择函数都是仿射最大化的形式

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,

其中 wiw_i 不全为零,即对参与者加权、对方案加常数,然后求和最大化 (Roberts 1979)。功利主义(所有 wi=1w_i = 1、ca=0c_a = 0)是它的特例。判断一个规则能否实施的有力工具是罗歇的循环单调性:存在支付使规则激励相容,当且仅当对每个参与者、每一圈类型序列,估值差之和非负 (Rochet 1987);最简单的两圈情形叫弱单调性:若类型 vv 得到方案 aa、类型 v′v' 得到方案 bb,则必须有 v(a)−v(b)≥v′(a)−v′(b)v(a) – v(b) \ge v'(a) – v'(b)。

下面的程序取三个方案、三名参与者、每人对每个方案的估值为 0 到 4 的整数(每人 125 种类型),检查三条规则:功利主义加克拉克支付、一个仿射最大化(权重 (1, 2, 1)、对第二个方案加 1.5)加加权的克拉克支付,以及最大最小规则。

推导

# 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

前两条规则在 1,500 个随机组合、每个组合 125 种误报下都没有获利的误报。最大最小规则在 3,000 对随机类型中有 16 对违反弱单调性。程序给出的例子:其他两人的类型固定时,类型 (4, 2, 2) 得到方案 y,类型 (1, 0, 1) 得到方案 x;前者对 x 的估值比 y 高 2,后者只高 1,偏好 x 更强的类型反而没有得到 x。要让两个类型都如实报告,价格差 p(y)−p(x)p(y) – p(x) 必须同时不超过 −2、不低于 −1,这是不可能的,所以无论怎样设计支付,最大最小规则都不能如实实施。功利主义规则在同样的 3,000 对中没有违反。

注

罗伯茨定理的条件很重要。 「不受限制的估值域」与「至少三个方案」缺一不可。只有两个方案时,任何单调的规则都可实施;在拍卖这样的单参数环境中(每人只有一个数:对物品的估值),存在不是仿射最大化却可以实施的规则,例如出价者分布不同、虚拟估值非线性时的迈尔森最优拍卖(第四章)。要注意,同分布、正则时的迈尔森拍卖——「估值最高者若不低于保留价 rr 就得到物品」——本身仍是仿射最大化(各人权重为 1,「不卖」这一方案的常数为 rr)。所以罗伯茨定理说的不是「只有 VCG 类机制可行」,而是「在估值足够丰富时,可行的目标只能是加权福利加上方案常数(仿射最大化)」。

小结表

结论 环境 不能兼得的性质 放宽什么可以绕开
赫维茨 1972、周林 1991 两人交换经济,经典偏好 占优策略说真话、帕累托有效、个体理性(周林:有效 + 防操纵 ⇒ 逆独裁) 人数很多;放弃有效
格林—拉丰 1977 及后续 拟线性,估值不受限制 有效、占优策略激励相容、预算平衡 改用贝叶斯激励相容(AGV)
迈尔森—萨特思韦特 1983(第 27 本) 双边交易,估值区间重叠 有效、贝叶斯激励相容、个体理性、预算平衡 外部补贴;放弃有效
罗伯茨 1979 至少三个方案,估值不受限制 占优策略可实施 ⇒ 仿射最大化 受限域(单参数等)
吉巴德—萨特思韦特(第一章) 无货币,至少三个方案 防操纵 ⇒ 独裁 引入货币;单峰偏好

假说 · 尚未验证 · 社群奖池的预算平衡

作者的假说(尚未确立): 社群用「成员报告对活动的估值、按 VCG 决定是否举办并收取克拉克税」决定公共活动时,若把税款平均退还给成员,成员报告与经独立测量的真实估值之间的偏差会显著大于不退还时。什么样的结果能证明它是错的: 在实验室中事先登记的比较里,退还组与不退还组的报告偏差之差的置信区间包含零。第 (C) 部分只是一个反例,不说明这种偏差在人群中有多大。

本章小结

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

参考文献

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