5D Library › 机制设计、维克里—克拉克—格罗夫斯(VCG)拍卖与数字社群激励相容工程 · English
第一章 显示原理、激励相容与承诺
机制是什么
机制设计把一个规则看成一台机器:每个参与者 有只有自己知道的类型 (对物品的估值、做一件事的成本、对公共项目的偏好),向机器提交一条消息 ,机器按照事先公布的结果函数 给出结果(谁得到什么、谁付多少钱)。设计者心中有一个社会选择函数 ,即「如果我知道每个人的类型,我希望得到的结果」。问题是:能否设计 ,使参与者按自身利益选择消息时,均衡结果恰好是 ?如果能,就说机制实施了 。
本书所说的拍卖都假设私人价值(每个人的估值只取决于自己的类型)与拟线性效用:参与者得到结果 、支付 时的效用为 。这两个假设决定了下面大多数结论的适用范围;第 27 本已经用「我切你选」、拍卖与公共品三个例子介绍过「逆向博弈论」的思路,这里直接进入定理。系统的教科书讲解可参看博格斯的机制设计导论、克里希纳与米尔格罗姆的拍卖理论专著,以及《算法博弈论》文集 (Börgers 2015; Krishna 2010; Milgrom 2004; Nisan et al. 2007)。
显示原理的两种版本
直接机制是消息空间就等于类型空间的机制:每个人报告一个类型,机器按报告计算结果。若如实报告在其中是均衡,就说这个直接机制激励相容。
定理(占优策略版本)。 若机制 有占优策略均衡 ,且 对所有 成立,则直接机制 本身是占优策略激励相容的:如实报告是每个人的占优策略。
证明。 设参与者 的真实类型为 ,他报告 ,其他人报告任意的 。在直接机制中他得到 。由于 在原机制中对其他人的任意消息都是最优的,特别是对消息 也是最优的,所以
左边就是如实报告的效用,右边是报告 的效用。证毕。
定理(贝叶斯版本)。 若类型按共同先验分布抽取,机制 有贝叶斯纳什均衡 使 ,则直接机制 是贝叶斯激励相容的:在其他人如实报告时,每个人如实报告的期望效用最高。
证明。 与上面相同,只是把「对其他人的任意消息」换成「对其他人类型的条件分布取期望」: 在给定 时最大化期望效用,所以任何别的消息 都不会更好。证毕。
两种版本的证明都是「让机器替你执行均衡策略」:直接机制只是把原机制和参与者的均衡策略组合在一起。占优策略版本由吉巴德 1973 年在投票问题中给出 (Gibbard 1973);贝叶斯版本由迈尔森 1979、达斯古普塔—哈蒙德—马斯金 1979、哈里斯—汤森 1981 等独立提出 (Myerson 1979; Dasgupta et al. 1979; Harris and Townsend 1981)。迈尔森在诺贝尔奖演讲中把它的意义概括为:在寻找最优规则时,可以不失一般性地只考虑说真话的直接机制 (Myerson 2008)。
注
两种「激励相容」的差别。 占优策略激励相容不需要参与者知道别人的类型分布,也不需要相信别人说真话;贝叶斯激励相容只要求在「别人说真话、自己只知道分布」时如实报告平均而言最好。后者弱得多:在具体的一局中,知道别人报告的人往往有利可图。下面的程序用第 27 本的一价拍卖说明这一点。
下面的程序取两名出价者、估值独立服从 均匀分布的一价拍卖。第 27 本已推导其均衡出价 。把它与拍卖组合,得到一个直接机制:报告 ,报告最高者获胜并支付 。类型 报告 的期望效用为 ,在 处取最大,所以它是贝叶斯激励相容的;但若知道对手报告 0.3,估值 0.8 的人只需报告略高于 0.3 即可。程序的第二部分讨论承诺,见下一节。
推导
# Chapter 1. (A) The Bayesian revelation principle, checked on a grid: take the
# first-price auction with two bidders, values i.i.d. U[0,1], whose Bayes-Nash
# equilibrium is b(v) = v/2 (Book 27). The "direct" mechanism composes the strategy with
# the auction: report r, highest report wins and pays r/2. Truth is optimal in
# expectation (Bayesian IC) but NOT a dominant strategy: against a known rival report,
# shading pays. (B) Commitment: one buyer, v ~ U[0,1], T selling periods, discount d.
# With commitment the seller posts p = 1/2 once (revenue 1/4, Myerson / Riley-Zeckhauser).
# Without commitment she re-prices after each refusal and the buyer anticipates it (the
# Coase problem). Backward induction: with remaining types [0, k], continuation revenue
# is c_t k^2 and the price a_t k; type kappa is indifferent between buying now and next
# period: kappa - p = d (kappa - a_{t+1} kappa).
G = [i / 1000 for i in range(1001)]
def bayes_utility(v, r): # P(win) = P(rival value < r) = r; pay r/2 if win
return r * (v - r / 2)
def expost_utility(v, r, rival_report):
return (v - r / 2) if r > rival_report else 0.0
def no_commitment(d, T):
a, c = 0.5, 0.25 # last period: price k/2, revenue k^2/4
for _ in range(T - 1):
m = 1 - d + d * a # p = m * kappa keeps type kappa indifferent
s = m / (2 * m - 2 * d * c) # optimal new cutoff kappa = s k
a, c = m * s, m * s * (1 - s) + d * c * s * s
return c, a # revenue from k = 1, first-period price
if __name__ == "__main__":
worst = max(abs(max(G, key=lambda r: bayes_utility(v, r)) - v) for v in G[::10])
print(f"(A) Bayesian IC: largest gap, best report vs true value = {worst:.3f}")
v, rival = 0.80, 0.30
best = max(G, key=lambda r: expost_utility(v, r, rival))
print(f" ex post, value {v}, rival report {rival}: truth earns"
f" {expost_utility(v, v, rival):.3f}; report {best:.3f} earns"
f" {expost_utility(v, best, rival):.3f}")
k2 = max(G, key=lambda k: k * (1 - 0.9 / 2) * (1 - k) + 0.9 * (k / 2) ** 2)
print(f"(B) two periods, d = 0.9: grid cutoff {k2:.3f}; closed form (2-d)/(4-3d)"
f" = {(2 - 0.9) / (4 - 3 * 0.9):.4f}")
print(" revenue without commitment (commitment: 0.2500 for every d and T)")
print(" periods T: 1 2 5 20 100 1000")
for d in (0.5, 0.9, 0.99):
row = [no_commitment(d, T) for T in (1, 2, 5, 20, 100, 1000)]
print(f" d = {d:<5}" + "".join(f"{c:8.4f}" for c, _ in row))
c, a = no_commitment(0.99, 1000)
print(f" d = 0.99, T = 1000: first price {a:.4f}, revenue {c / 0.25:.1%}"
" of the commitment value")
# (A) Bayesian IC: largest gap, best report vs true value = 0.000
# ex post, value 0.8, rival report 0.3: truth earns 0.400; report 0.301 earns 0.650
# (B) two periods, d = 0.9: grid cutoff 0.846; closed form (2-d)/(4-3d) = 0.8462
# revenue without commitment (commitment: 0.2500 for every d and T)
# periods T: 1 2 5 20 100 1000
# d = 0.5 0.2500 0.2250 0.2084 0.2071 0.2071 0.2071
# d = 0.9 0.2500 0.2327 0.1926 0.1269 0.1201 0.1201
# d = 0.99 0.2500 0.2476 0.2405 0.2084 0.1028 0.0455
# d = 0.99, T = 1000: first price 0.0909, revenue 18.2% of the commitment value第一行确认:在 0 到 1、步长 0.001 的网格上,每个类型的最优报告都等于真实类型(差距 0.000)。第二行显示它不是占优策略激励相容:已知对手报告 0.3 时,如实报告得 0.400,报告 0.301 得 0.650。贝叶斯版本的显示原理把一价拍卖变成了一个「平均而言说真话最好」的机制,但不能把它变成「无论如何说真话最好」的机制;后者需要支付规则本身改变,即第二价格规则。
显示原理不说什么
显示原理是一条等价性结论,它的力量来自假设。至少有五件事它不保证。
第一,均衡的唯一性。 它只保证「说真话是一个均衡」,不保证没有其他对设计者不利的均衡。要求所有均衡都实现 的问题称为完全实施;马斯金证明,在完全信息下,可以纳什完全实施的社会选择规则必须满足一种单调性(后称马斯金单调性)(Maskin 1999)。第 27 本讨论过 VCG 中落败者合谋的例子,这正是多重均衡的一种形式。
第二,承诺能力。 证明中「机器替你执行策略」默认设计者事后不会改变规则。若设计者在看到报告后可以重新谈判或修改规则,参与者会预见到这一点,显示原理就要改写:贝斯特与施特劳斯证明,在单个代理人、承诺不完全的情形下,仍可以只考虑消息空间等于类型空间的直接机制,但不能再假定代理人如实报告 (Bester and Strausz 2001)。最清楚的例子是科斯问题 (Coase 1972):一位卖家面对一个估值 的买家。若她能承诺,最好的做法是一次性标价 1/2,期望收入 1/4,以后永不降价(承诺下最优售卖机制就是一口价,见赖利与泽克豪泽 (Riley and Zeckhauser 1983))。但若买家拒绝之后她可以降价,买家就会等待;她只能在一系列逐期下降的价格中卖出。
程序的第二部分用逆向归纳求解 期、贴现因子 的线性均衡:剩下的类型为 时,续值为 、价格为 ,边际类型 在「现在买」与「等一期」之间无差异:。两期、 时,网格搜索的分界点 0.846 与闭式解 一致。表中可见: 时收入从一期的 0.2500 降到两期的 0.2327、五期的 0.1926,多期时趋于 0.1201; 时 1,000 期的收入只有 0.0455,是承诺收入的 18.2%,第一期标价只有 0.0909。这就是古尔、索南夏因与威尔逊证明的科斯猜想:期数越多、等待越便宜,不能承诺的垄断者越接近按边际成本定价 (Gul et al. 1986)。一个规则的设计者若不能约束自己将来的行为,他的规则就不会被人认真对待。
第三,通信与隐私。 直接机制要求每个人报告全部类型。在 件物品的组合拍卖中,一个类型是 个组合的估值;报告它既不现实,也泄露商业秘密:罗特科普夫列举 VCG 不实用的十三条理由时,就包括出价者不愿向拍卖方透露真实估值、担心拍卖方或日后的谈判对手利用这些信息 (Rothkopf 2007; Rothkopf et al. 1990)。实践中使用的往往是间接机制(例如逐轮加价的时钟拍卖),它们只在理论上「等价」于某个直接机制。
第四,参与与预算。 激励相容只是约束之一。参与者是否愿意参加(个体理性)、设计者是否需要贴钱(预算平衡),会与激励相容和效率发生冲突,第五章专门讨论。
第五,参与者是否看得出占优策略。 占优策略存在不等于人们会用。卡格尔、哈斯塔德与莱文的实验室研究发现,在第二价格密封拍卖中出价者系统性地高于估值出价 (Kagel et al. 1987);李胜武提出「显然防操纵」的概念,并用实验显示,同样以说真话为占优策略,逐轮加价的时钟拍卖比第二价格密封拍卖引出更多的占优策略行为 (Li 2017)。第八章的实验正是以此为背景。
证据
吉巴德—萨特思韦特定理 (Gibbard 1973; Satterthwaite 1975) 是显示原理在「没有货币」时的否定版本:备选方案至少三个、偏好不受限制、社会选择函数取遍所有方案时,占优策略激励相容的规则只有独裁。拟线性效用允许用支付来平衡激励,这是 VCG 能够存在的原因;第五章的罗伯茨定理说明,即使有了支付,在不受限制的估值域上能实施的规则也相当有限。
假说 · 尚未验证 · 可承诺的积分规则
作者的假说(尚未确立): 在线社群中,事先公开、并以技术手段承诺不追溯修改的积分规则(例如规则版本上链或第三方存证),比由管理者事后裁量的规则引出更多如实的贡献申报与更少的「等待规则变化」行为。什么样的结果能证明它是错的: 在事先登记的随机化比较中(以社群为单位,独立于作者的社群),两种规则下经核实的如实申报比例之差的置信区间包含零或偏向裁量规则。本书不做这项检验。
本章小结
显示原理说:任何机制的均衡结果,都可以由一个让人如实报告的直接机制得到;占优策略版本与贝叶斯版本的证明都是把均衡策略「装进」机器。它让机制设计可以只研究激励相容的直接机制,但它不保证均衡唯一,依赖设计者的承诺能力,要求报告全部类型,也不保证参与者看得出占优策略。程序显示,由一价拍卖组合成的直接机制只是贝叶斯激励相容;不能承诺不降价的卖家,在多期、低等待成本时只能得到承诺收入的一小部分(、1,000 期时为 18.2%)。
参考文献
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).