Skip to content

模型Model

直接显示机制

Direct-revelation mechanism · 直接报告机制 · 显示原理 · Revelation principle

用类型报告、结果规则和支付规则区分真实偏好与策略选择,写清占优策略及贝叶斯激励约束,并以策略模拟证明直接显示原理。

形式陈述 ​

设有有限个参与者 N={1,…,n}、非空有限结果集 X,以及每人的非空类型集 Ti。类型 ti∈Ti 是参与者自己知道的偏好信息,其估值为 vi(x;ti)∈R。这里采用私人价值假设:同一结果给参与者 i 带来的价值只由 ti 决定,不依赖别人的真实类型。X 有限不意味着 Ti 有限;例如一件物品的去向只有有限种,每人的估值却可以是任意非负实数。

直接显示机制要求每人报告一个 ri∈Ti,再由两个公开的函数决定结果和支付:

x:∏iTi⟶X,p:∏iTi⟶Rn.

本页采用确定性规则。若规则包含最大化,则用固定、公开的结果顺序处理并列。pi(r)>0 表示参与者向设计者付款,负数表示收款。参与者的准线性效用为

ui(r;ti)=vi(x(r);ti)−pi(r).

报告决定机制做什么,真实类型决定参与者如何评价这个结果。准线性模型允许直接减去钱款;它没有加入硬预算、非线性的金钱效用或参与者秘密控制的可行集。

两种激励约束 ​

机制是占优策略激励相容的(DSIC),若对每位 i、每个真实类型 ti、每个虚假报告 ri 和任意其他人的报告 r−i,都有

vi(x(ti,r−i);ti)−pi(ti,r−i)≥vi(x(ri,r−i);ti)−pi(ri,r−i).

因此诚实报告是弱占优策略:别人可以诚实、撒谎或随意报告,自己都不能靠单方改报获得严格更高的效用。这里允许其他报告同样好,并不声称诚实是唯一最优选择。

为陈述贝叶斯激励相容性(BIC),本页另外限制各 Ti 有限,并给定共同先验 μ,每个允许类型的边缘概率均为正。使用条件期望,BIC 要求对所有 i,ti,ri,

Et−i∼μ(⋅∣ti)[vi(x(ti,t−i);ti)−pi(ti,t−i)]≥Et−i∼μ(⋅∣ti)[vi(x(ri,t−i);ti)−pi(ri,t−i)].

这次假设其他人诚实,只在给定自己真实信息后的平均意义上比较。若类型相关,两边都必须使用 μ(t−i∣ti);虚假报告 ri 不会把自己掌握的信息改成 ri。将 DSIC 的逐点不等式按此分布求和立即得到 BIC,反向推导一般不成立。

参与和收支是另外的约束 ​

规定不参与的效用为零。事后个体理性要求每个真实类型剖面 t 上都有 ui(t;ti)≥0;中期个体理性仅要求给定 ti、其他人诚实时的条件期望效用非负。两者都在比较参与和退出,而激励相容比较参与之后的诚实和改报,不能互相替代。

按本页符号,预算平衡是每个报告剖面都满足 ∑ipi(r)=0;无赤字只要求这个和非负。这些条件约束设计者的收支,既不同于参与者的收益非负,也不同于社会估值总和最大。

直觉

普通博弈把收益函数交给分析者,让分析者研究玩家会选什么。机制设计则先确定想实现的结果,再设计一套“收到什么报告,就分配什么、收多少钱”的规则,使玩家根据自己的偏好行动时能实现该目标。设计者通常不能检查“我值十元”是否真实,因此诚实必须由偏离比较支持,不能写进参与者的行为假设。

固定真实类型后,报告就是策略,效用规则给出了一个报告博弈。当类型集也有限时,它恰是有限策略式博弈;类型集无限时仍可写出同样的单方偏离不等式,但不能直接借用有限策略空间的存在性结论。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 和事后个体理性。失败来自状态逐点比较与条件平均比较的差别,不需要复杂的拍卖环境。

推论与应用

直接显示原理:把原来的策略交给机制执行 ​

考虑一个间接机制,每人可发送消息 mi∈Mi,结果和支付由 g(m)、qi(m) 决定。假设对每个类型已选定一个纯策略消息 σi(ti),并且它对任意其他人的消息都是占优策略。构造直接机制

x(r)=g(σ1(r1),…,σn(rn)),pi(r)=qi(σ1(r1),…,σn(rn)).

诚实报告 ti 就让新机制代为发送原策略 σi(ti)。固定其他人的任意报告 r−i,它们在原机制中被转换成消息 σ−i(r−i)。直接机制中的任何偏离 ri,都只是原机制中偏离到消息 σi(ri)。原占优性已经比较过这个消息,所以新机制的诚实报告也是占优的;全体诚实的结果和支付与原选定策略剖面逐点相同。这就证明了占优策略版本的直接显示原理。

若原机制只给出一个选定的纯策略贝叶斯 Nash 均衡,使用同一个构造,并按真实类型的条件先验求期望。原均衡允许比较每个消息偏离,因而特别允许偏离到 σi(ri);得到的正是前面的 BIC 不等式。这里保留的是所选均衡下的结果与支付,并没有把贝叶斯保证加强成占优策略保证。

显示原理允许研究者在寻找某类可实现结果时转向直接机制,但它不凭空产生原机制或均衡,也不排除新机制中存在其他均衡。类型描述还可能很长,替玩家执行原策略也可能很难,因此这个构造没有自动给出高效通信或计算算法。

VCG 机制进一步给出具体答案:在准线性私人价值模型里,用精确福利最大化决定结果,再用别人受到的外部性决定支付,使自己的效用最大化与机制的分配目标对齐。

参考资料
  • Tim Roughgarden,CS364A Lecture 2: Mechanism Design Basics,2013,§1、§4;准线性拍卖模型、激励相容与显示原理。
  • Asuman Ozdaglar,6.254 Lecture 19: Auction Theory,MIT,2010,slides 5–11、15;贝叶斯拍卖与显示原理。讲义的独立私人价值设定下可用边缘分布求期望;本页对相关类型显式保留真实类型条件。
关系图谱7 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系