形式陈述
设有有限个参与者 N = { 1 , … , n } 、非空有限结果集 X ,以及每人的非空类型集 T i 。类型 t i ∈ T i 是参与者自己知道的偏好信息,其估值为 v i ( x ; t i ) ∈ R 。这里采用私人价值 假设:同一结果给参与者 i 带来的价值只由 t i 决定,不依赖别人的真实类型。X 有限不意味着 T i 有限;例如一件物品的去向只有有限种,每人的估值却可以是任意非负实数。
直接显示机制要求每人报告一个 r i ∈ T i ,再由两个公开的函数 公理库 函数 Function · Map · Mapping 由定义域、陪域和单值图共同组成,并把每个输入送到唯一输出的映射。 决定结果和支付:
x : ∏ i T i ⟶ X , p : ∏ i T i ⟶ R n . 本页采用确定性规则。若规则包含最大化,则用固定、公开的结果顺序处理并列。p i ( r ) > 0 表示参与者向设计者付款,负数表示收款。参与者的准线性效用 为
u i ( r ; t i ) = v i ( x ( r ) ; t i ) − p i ( r ) . 报告决定机制做什么,真实类型决定参与者如何评价这个结果。准线性模型允许直接减去钱款;它没有加入硬预算、非线性的金钱效用或参与者秘密控制的可行集。
两种激励约束
机制是占优策略激励相容的 (DSIC),若对每位 i 、每个真实类型 t i 、每个虚假报告 r i 和任意其他人的报告 r − i ,都有
v i ( x ( t i , r − i ) ; t i ) − p i ( t i , r − i ) ≥ v i ( x ( r i , r − i ) ; t i ) − p i ( r i , r − i ) . 因此诚实报告是弱占优策略:别人可以诚实、撒谎或随意报告,自己都不能靠单方改报获得严格更高的效用。这里允许其他报告同样好,并不声称诚实是唯一最优选择。
为陈述贝叶斯激励相容性 (BIC),本页另外限制各 T i 有限,并给定共同先验 μ ,每个允许类型的边缘概率均为正。使用条件期望 公理库 条件期望 Conditional expectation 以信息分组的加权平均建立条件期望直觉,再连接测度定义、最小均方预测、塔式性质和可计算反例。 ,BIC 要求对所有 i , t i , r i ,
E t − i ∼ μ ( ⋅ ∣ t i ) [ v i ( x ( t i , t − i ) ; t i ) − p i ( t i , t − i ) ] ≥ E t − i ∼ μ ( ⋅ ∣ t i ) [ v i ( x ( r i , t − i ) ; t i ) − p i ( r i , t − i ) ] . 这次假设其他人诚实,只在给定自己真实信息后的平均意义上比较。若类型相关,两边都必须使用 μ ( t − i ∣ t i ) ;虚假报告 r i 不会把自己掌握的信息改成 r i 。将 DSIC 的逐点不等式按此分布求和立即得到 BIC,反向推导一般不成立。
参与和收支是另外的约束
规定不参与的效用为零。事后个体理性 要求每个真实类型剖面 t 上都有 u i ( t ; t i ) ≥ 0 ;中期个体理性 仅要求给定 t i 、其他人诚实时的条件期望效用非负。两者都在比较参与和退出,而激励相容比较参与之后的诚实和改报,不能互相替代。
按本页符号,预算平衡 是每个报告剖面都满足 ∑ i p i ( r ) = 0 ;无赤字 只要求这个和非负。这些条件约束设计者的收支,既不同于参与者的收益非负,也不同于社会估值总和最大。
直觉
普通博弈把收益函数交给分析者,让分析者研究玩家会选什么。机制设计则先确定想实现的结果,再设计一套“收到什么报告,就分配什么、收多少钱”的规则,使玩家根据自己的偏好行动时能实现该目标。设计者通常不能检查“我值十元”是否真实,因此诚实必须由偏离比较支持,不能写进参与者的行为假设。
固定真实类型后,报告就是策略,效用规则给出了一个报告博弈。当类型集也有限时,它恰是有限策略式博弈 公理库 有限策略式博弈 Strategic-form game · Normal-form game · 标准式博弈 用玩家、有限策略集和收益函数描述相互影响的选择,并以固定他人策略后的单方偏离定义最佳回应。 ;类型集无限时仍可写出同样的单方偏离不等式,但不能直接借用有限策略空间的存在性结论。DSIC 在每个对手报告上成立,BIC 则允许某些状态下的损失被其他状态下的收益抵消。
例子与边界
固定价格:逐个真实类型检查
一位买家的类型为非负估值 t ,结果为“得到物品”或“没有物品”,对应估值为 t 或 0 。给定价格 q ≥ 0 ,报告 r ≥ q 就获得物品并支付 q ,否则不获得也不支付。
若 t ≥ q ,诚实报告产生 t − q ≥ 0 ;改报到价格以下变为 0 ,留在价格以上收益不变。若 t < q ,诚实收益为 0 ;改报到价格以上得到 t − q < 0 ,留在价格以下仍为 0 。边界 t = q 时两种结果都给零效用。因此该机制 DSIC,且对零外部选项满足事后个体理性。证明比较了每个可改变分配的报告区域,而非只试一个谎言。
BIC 可以容许某个状态下撒谎更好
现在有两位参与者,类型都为 L , H 。第一人在获得物品时的价值分别为 0 , 2 ,未获得时为零;第二人在所有结果下的估值、支付均为零。两人的类型独立,各自以 3 / 4 的概率为 H 。规则规定:第一人报告 H 就支付 1 ,而只有两人都报告 H 时,第一人才获得物品;第一人报告 L 时既不获物也不付款。
第一人的真实类型为 H 时,诚实的期望效用为 ( 3 / 4 ) ⋅ 2 − 1 = 1 / 2 ,改报 L 得到零。真实类型为 L 时,诚实得到零,改报 H 的期望效用为 − 1 。第二人不论报告什么效用都为零。因此诚实构成贝叶斯均衡,机制 BIC,也满足中期个体理性。
但固定第二人的报告为 L ,第一人的真实类型为 H 时,诚实报告的效用为 − 1 ,改报 L 却能得到零。这同时否定 DSIC 和事后个体理性。失败来自状态逐点比较与条件平均比较的差别,不需要复杂的拍卖环境。
推论与应用
直接显示原理:把原来的策略交给机制执行
考虑一个间接机制,每人可发送消息 m i ∈ M i ,结果和支付由 g ( m ) 、q i ( m ) 决定。假设对每个类型已选定一个纯策略消息 σ i ( t i ) ,并且它对任意其他人的消息都是占优策略。构造直接机制
x ( r ) = g ( σ 1 ( r 1 ) , … , σ n ( r n ) ) , p i ( r ) = q i ( σ 1 ( r 1 ) , … , σ n ( r n ) ) . 诚实报告 t i 就让新机制代为发送原策略 σ i ( t i ) 。固定其他人的任意报告 r − i ,它们在原机制中被转换成消息 σ − i ( r − i ) 。直接机制中的任何偏离 r i ,都只是原机制中偏离到消息 σ i ( r i ) 。原占优性已经比较过这个消息,所以新机制的诚实报告也是占优的;全体诚实的结果和支付与原选定策略剖面逐点相同。这就证明了占优策略版本的直接显示原理。
若原机制只给出一个选定的纯策略贝叶斯 Nash 均衡,使用同一个构造,并按真实类型的条件先验求期望。原均衡允许比较每个消息偏离,因而特别允许偏离到 σ i ( r i ) ;得到的正是前面的 BIC 不等式。这里保留的是所选均衡下的结果与支付,并没有把贝叶斯保证加强成占优策略保证。
显示原理允许研究者在寻找某类可实现结果时转向直接机制,但它不凭空产生原机制或均衡,也不排除新机制中存在其他均衡。类型描述还可能很长,替玩家执行原策略也可能很难,因此这个构造没有自动给出高效通信或计算算法。
VCG 机制 公理库 VCG 机制 Vickrey–Clarke–Groves mechanism · Clarke pivot rule · Clarke 枢轴支付 · Groves mechanism 精确最大化申报福利,并按其他参与者损失的福利收费;通过双物品拍卖计算全部枢轴支付、证明诚实占优,再定位近似分配破坏证明的位置。 进一步给出具体答案:在准线性私人价值模型里,用精确福利最大化决定结果,再用别人受到的外部性决定支付,使自己的效用最大化与机制的分配目标对齐。
参考资料