机制设计

一、核心定义

机制设计(Mechanism Design)是博弈论的一个分支,研究如何设计规则和制度(机制),使得理性个体在追求自身利益的过程中,实现社会期望的结果。机制设计也被称为"逆向博弈论"或"制度经济学的数学基础"。

核心思想:

给定社会目标,设计一个博弈规则,使得:

1. 参与者有激励说真话(激励相容)
2. 参与者愿意参与(个人理性)
3. 实现社会最优结果

基本要素:

1. 参与者:$N=\{1,2,...,n\}$
2. 类型空间:$\mathrm{\Theta }={\mathrm{\Theta }}_1\times ...\times {\mathrm{\Theta }}_n$,每个参与者有私人信息 ${\theta }_i$
3. 结果空间:$X$,所有可能的社会结果
4. 社会选择函数:$f:\mathrm{\Theta }\to X$,将类型映射到结果
5. 机制:$(M,g)$,其中 $M$ 是消息空间,$g:M\to X$ 是结果函数

数学表达:

机制 $(M,g)$ 实现社会选择函数 $f$,如果存在均衡策略 $s^{\ast }:\mathrm{\Theta }\to M$,使得:

$$g(s^{\ast }(\theta ))=f(\theta ),\mathrm{\forall }\theta \in \mathrm{\Theta }$$

二、理论推导 / 核心逻辑

显示原理(Revelation Principle):

任何通过某机制在均衡中实现的社会选择函数,都可以通过一个直接机制在激励相容的条件下实现。

直接机制:参与者直接报告类型 ${\hat{\theta }}_i$

激励相容(IC):说真话是最优策略

$$u_i(f({\theta }_i,{\theta }_{-i}),{\theta }_i)\ge u_i(f({\hat{\theta }}_i,{\theta }_{-i}),{\theta }_i),\mathrm{\forall }{\theta }_i,{\hat{\theta }}_i,{\theta }_{-i}$$

个人理性(IR):参与优于不参与

$$u_i(f(\theta ),{\theta }_i)\ge {\overline{u}}_i,\mathrm{\forall }{\theta }_i$$

Groves-Clarke机制(VCG机制):

对于准线性效用:

$$u_i(x,t_i,{\theta }_i)=v_i(x,{\theta }_i)+t_i$$

其中 $x$ 是公共决策,$t_i$ 是货币转移。

VCG支付规则:

$$t_i(\theta )=\sum _{j\ne i}{v}_j(x^{\ast }(\theta ),{\theta }_j)+h_i({\theta }_{-i})$$

其中:

• $x^{\ast }(\theta )=\arg \underset{x}{max}\sum _i{v}_i(x,{\theta }_i)$
• $h_i$ 是任意不依赖于 ${\theta }_i$ 的函数

Clarke税(Clarke Pivot Rule):

$$h_i({\theta }_{-i})=-\underset{x}{max}\sum _{j\ne i}{v}_j(x,{\theta }_j)$$

支付:

$$t_i=-[\underset{x}{max}\sum _{j\ne i}{v}_j(x,{\theta }_j)-\sum _{j\ne i}{v}_j(x^{\ast }(\theta ),{\theta }_j)]$$

参与者 $i$ 支付其对他人的外部性。

激励相容性证明:

参与者 $i$ 报告 ${\hat{\theta }}_i$ 时的效用:

$$U_i({\hat{\theta }}_i|{\theta }_i)=v_i(x^{\ast }({\hat{\theta }}_i,{\theta }_{-i}),{\theta }_i)+\sum _{j\ne i}{v}_j(x^{\ast }({\hat{\theta }}_i,{\theta }_{-i}),{\theta }_j)+h_i({\theta }_{-i})$$

由于 $x^{\ast }$ 最大化总价值,当 ${\hat{\theta }}_i={\theta }_i$ 时:

$$x^{\ast }({\theta }_i,{\theta }_{-i})=\arg \underset{x}{max}[v_i(x,{\theta }_i)+\sum _{j\ne i}{v}_j(x,{\theta }_j)]$$

因此说真话是最优策略。

三、关键结论

1. 显示原理简化了机制设计问题,只需考虑直接机制
2. VCG机制在准线性效用下实现激励相容和效率
3. Clarke税使参与者内部化其决策的外部性
4. 激励相容和个人理性是机制设计的核心约束
5. 不可能定理:某些情况下不存在同时满足所有理想性质的机制
6. 机制设计广泛应用于拍卖、投票、公共物品供给等领域

四、图形解释

机制设计框架图:

参与者私人信息(θ) → 报告消息(m) → 机制(M,g) → 结果(x) → 效用(u)
         ↑                                              ↓
         └──────────── 激励相容约束 ────────────────────┘

VCG机制示意:

1. 每个参与者报告估值 ${\theta }_i$
2. 选择最大化总价值的结果 $x^{\ast }$
3. 参与者 $i$ 支付其对他人的外部性
4. 说真话是占优策略

公共物品供给:

• 横轴:公共物品数量 $Q$
• 纵轴:边际收益/成本

曲线:

• 个人边际收益:$M{B}_i(Q)$
• 总边际收益:$\sum _{i}M{B}_i(Q)$
• 边际成本:$MC(Q)$

最优:$\sum _{i}M{B}_i(Q^{\ast })=MC(Q^{\ast })$

VCG机制诱导参与者真实报告 $M{B}_i$。

五、例子(现实或数值)

例子1:公共物品供给

3个人决定是否建公园,成本$300。

真实估值:

• 甲:$150
• 乙:$120
• 丙:$80
• 总:$350 > $300,应建

直接投票问题:

如果按估值分摊成本,丙有激励谎报$0,搭便车。

VCG机制:

每人报告估值 $v_i$,若 $\sum v_i\ge 300$ 则建,否则不建。

支付(Clarke税):

• 甲支付:$max(0,300-120-80)=100$
• 乙支付:$max(0,300-150-80)=70$
• 丙支付:$max(0,300-150-120)=0$

甲的支付解释:如果没有甲,总估值$200 < $300,不建。甲的加入使项目可行,甲支付其造成的外部性。

激励相容:

如果甲谎报$100:

• 总估值:$100+120+80=300$,刚好建
• 甲支付:$100$
• 甲净收益:$150-100=50$

如果甲说真话$150:

• 甲支付:$100$
• 甲净收益:$150-100=50$

说真话是最优策略!

例子2:拍卖(第二价格拍卖)

拍卖一件物品,3个竞标者:

• 甲估值:$100
• 乙估值:$80
• 丙估值:$60

第二价格拍卖规则:

• 出价最高者获得物品
• 支付第二高价格

均衡:

每人报真实估值是占优策略。

结果:

• 甲出价$100,获得物品
• 甲支付$80(第二高价)
• 甲净收益:$100 - $80 = $20

为什么说真话:

假设甲出价$90 < $100:

• 如果第二高价$85,甲仍获胜,支付$85
• 如果第二高价$95,甲输了,损失$100 - $95 = $5

假设甲出价$110 > $100:

• 如果第二高价$105,甲赢了但支付$105 > $100,亏损

说真话避免这些风险!

例子3:投票(Groves机制)

3人投票选择项目A或B:

• 甲:$v_A=100,v_B=0$
• 乙:$v_A=60,v_B=0$
• 丙:$v_A=0,v_B=120$

多数投票问题:

A获胜(2:1),但总价值:

• A:$160
• B:$120

A确实更优,但如果丙谎报强烈偏好,可能改变结果。

Groves机制:

每人报告估值,选择总价值最大的项目。

支付:

• 甲:$max(60+120,60+0)-(60+120)=0$
• 乙:$max(100+120,100+0)-(100+120)=0$
• 丙:$max(100+60,0+60)-(100+60)=0$

选择A,无人支付(因为每人都不是关键票)。

例子4:双边交易

卖家成本$50,买家估值$100。

问题:双方都有激励隐瞒真实信息。

Myerson-Satterthwaite定理:

不存在同时满足激励相容、个人理性和事后效率的机制。

次优机制:

设定保留价格:

• 买家最高支付$80
• 卖家最低接受$60

如果成交,价格$70。

效率损失:某些有效交易(如成本$55,估值$65)不会发生。

例子5:匹配市场(Gale-Shapley算法)

医学生与医院匹配:

学生偏好:

• 学生1:医院A > B > C
• 学生2:医院B > A > C

医院偏好:

• 医院A:学生2 > 学生1
• 医院B:学生1 > 学生2

延迟接受算法:

1. 学生向首选医院申请
2. 医院暂时接受最优学生,拒绝其他
3. 被拒学生向次选申请
4. 重复直到稳定

结果:

• 学生1 → 医院B
• 学生2 → 医院A

稳定匹配,学生说真话是最优策略。

六、相关知识

• 纳什均衡
• 信息不对称
• 逆向选择
• 道德风险
• 拍卖理论
• 公共物品

七、现实应用

1. 拍卖设计:

   • 频谱拍卖:FCC使用VCG机制
   • 在线广告拍卖:Google AdWords
   • 政府采购:逆向拍卖

2. 匹配市场:

   • 医学生匹配:NRMP
   • 学校选择:波士顿、纽约
   • 肾脏交换:器官匹配

3. 公共决策:

   • 预算分配:二次方投票
   • 环境政策:排放权拍卖
   • 公共物品供给:众筹机制

4. 电力市场:

   • 发电调度
   • 输电权拍卖
   • 需求响应

5. 互联网:

   • 域名拍卖
   • 云计算资源分配
   • 网络拥塞控制

八、小结

机制设计是研究如何设计规则使理性个体实现社会目标的理论。核心概念包括激励相容、个人理性和显示原理。VCG机制通过让参与者内部化外部性实现激励相容和效率。机制设计广泛应用于拍卖、投票、匹配市场和公共物品供给。理解机制设计对于政策制定、市场设计和制度改革至关重要。2007年诺贝尔经济学奖授予Hurwicz、Maskin和Myerson,表彰其在机制设计理论的贡献。