最优机制与迈尔森拍卖 在本章，我们介绍最优机制（optimalmechanism）概念，并且以一件不可分割的 商品为例详细讨论了最优拍卖。迈尔森拍卖（Myersonauction）是最优拍卖领域的著名 机制。这种拍卖提出了使卖者期望收入最大的配置政策与支付规则，与此同时它还保证 激励相容与个体理性得以满足。 21.1最优机制 给定社会计划者想要解决的问题，他面对的一个关键议题是确定哪种直接显示机制 （或等价地，社会选择函数）是最优的（optimal）。我们现在试图将社会选择函数的最 优性和最优机制形式化。 口社会效用函数 我们首先定义社会效用函数的概念。 定义21.1（社会效用函数）社会效用函数是一个映射w：R”→R，它将每个效用组 的效用值。 考虑某个机制设计问题以及对此提出的直接显示机制9=（（O）∈N，f（·））。令 （6，“，0）为智能体的类型组，暂时假设当社会计划者要求他们报告类型时，他们会如 实报告。在这种情形下，给定类型组0=（6，，0），社会计划者实现的社会效用为： w(u(f(0),θ),,un(f(θ),0n）) (21.1)

然而，作为策略型智能体，他们可能不会如实报告自已的类型，除非这是最优策略。一 般来说，智能体的理性意味着智能体根据贝叶斯博弈的均衡s*（·）=（s（·），"， s（·））建议的策略来报告自己的类型；这个贝叶斯博弈是机制诱导出的。在这种情形 下，给定智能体的类型组0=（6，，0），社会计划者实现的社会效用为 w（u（f（s*（0)）,θ），,un(f（s*（0）)，0n）) (21.2) 在一些情形下，上面的均衡（若存在）可能是优势策略均衡。然而，一般来说，它是一个 贝叶斯纳什均衡。如果其中的某个均衡对应着所有智能体如实报告情形，那就太完美了。 口最优机制设计问题 根据上面给出的社会效用函数的定义可知，社会计划者的目标是找到社会选择函数 f（·）使得在既定自然和合理约束条件下，针对给定社会效用函数w（·）的期望社会 效用最大。合意约束条件可能包括我们以前考察过的社会选择函数的一些性质，例如事 后效率、激励相容以及个体理性。这个由社会选择函数组成的集合，称为可行社会选择 函数集（setoffeasiblesocialchoicefunctions），记为F。因此，我们现在可将社会计划 者的问题视为一个最优化问题，其中目标是使得期望社会效用最大，约束条件是社会选 择函数必须来自可行集F。这个问题称为最优机制设计（optimalmechanismdesign）问 题，该问题的解是一个社会选择函数f*（·）EF；社会选择函数f*（·）被用于定义 当前研究问题的最优机制の*=（（O;）∈N，f*（·））。 根据智能体是诚实的还是理性的，最优机制问题可以采取下列两种形式中的一种： 第 maxE。[w（u(f(0）,0),,un(f(θ),0n))] (21.3) f（·)EF 章 maxE。[w（u（f（s*（0））,0)，,un(f（s*（0)),0n）)] (21.4) f（·)EF 最 当智能体是诚实的从而总是显示自己的真实类型时，最优机制问题使用式（21.3）的形 优 机 式。当智能体是策略型的时，最优机制问题使用式（21.4）的形式。读者可能想知道如 制 何定义可行社会选择函数集F。这个集合没有唯一定义，它通常基于社会计划者的主观 与 迈 判断以及被形式化的问题。集合F的选择取决于社会计划者希望最优社会选择函数 尔 f*（·）拥有的合意性质。这些选择包括： 森拍 FDsIc={f：O→XIf（·）是优势策略激励相容的}； 卖 FBIc={f：O→Xf（·)是贝叶斯激励相容的）； FEPIR={f：O→X|f（·）是事后个体理性的）； FmR={f：O→X|f（·）是事中个体理性的）； FEAIR={f：O→Xf（·）是事前个体理性的）； FEPE={f:O→XIf（·）有事后效率}。 可行社会选择函数集F可以为上面的任何一个集合，也可以为其中若干集合的交。 21.2迈尔森最优拍卖 迈尔森最优拍卖是机制设计理论领域的一个里程碑式的结果（Myerson1]）。迈尔

森选择F=FBc门FmR作为可行社会选择函数集。在文献中，这个特别的可行集称为激励 可行集（incentivefeasible set)，这源于Myerson[1]。注意，如果智能体都是诚实的， 那么集合Fpsic与集合FBc将等于整个社会选择函数集。如果智能体是策略型的，那么集 合F=FBcFmR是可行集的一个适当选择。贝叶斯激励相容（BIC）保证了激励相容 性，这个性质比较容易满足，因此是合理的。事中个体理性（IIR）假设智能体知道自 已的类型，但不知道其他智能体的类型（这符合现实）；另外，IIR保证了每个智能体 的自愿参与性。 在本节，我们主要考察一个卖者的问题，他希望将一件不可分割的商品拍卖给n个 买者（竞标人），因此，N={1，""，n}。假设不存在保留价格（保留价格是使得卖者 在卖与不卖之间无差异的价格，若低于这个价格，卖者不会卖）。这里的目标是使得卖 者的期望收入最大。对于这个问题，我们讨论迈尔森发展出的最优机制（Myerson[1]）。 我们假设竞标人i（i=1，"，n）的类型（对拍卖物的评价）位于区间=[0，0]。 另外，我们还施加下列条件： （1）卖者和竞标人（买者）都是风险中性的（更多细节可参见8.6节）； （2）竞标人的类型在统计上是独立的，也就是说，联合密度（·）等于 （3）p;（·)>0，Vi=1，，n; （4）我们允许随机配置拍卖物，这样，结果集X具有一般形式。我们将y（θ）视 为当买者报告的类型组为0=（0，"，0）时买者i得到拍卖物的概率。因此，新的结 博奔论与机制设计 果集为 X={(yo,.,ynto,,tn)1yo∈[0,1],to≥0,yi∈[0,1],t<0, Vi=1.,.,n, {0= =1 i=0 i=1 u（f（0)，0）=u;（（yo（θ)，,yn（θ)，to（θ)，·,t（θ））,0）=θiy;（θ)+t；（θ) 将y（θ）视为v（k（θ)），即令y（θ)=v;（k（θ)）（其中k（θ）是对应于类型组θ的项目选 择），并且将其与上面的条件（2）和（3）放在一起，即可知道这里涉及的是线性环境 （线性环境的定义请参考19.7节）。 在上面的例子中，卖者是社会计划者，他寻找最优直接显示机制来卖掉他的商 品。迈尔森的思想是卖者使用的社会选择函数必须是贝叶斯激励相容和事中个体理性 的，而且必须能带给卖者最大期望收人（Myerson[i]）。因此，在这个问题中，可行社 会选择函数集为F=FBic门FmR。卖者的目标是使得总期望收人最大，在这里，总期望收 人为 Eo[e(u(f(0),θ),,un(f(0),0n))]=—E[∑t;(0)] 注意，在上面的目标函数中，我们使用了f（θ）而不是f（s*（0)）。这是因为在可行社会

选择函数集中，我们仅考虑贝叶斯激励相容的社会选择函数，对于这些函数，s*（0）= 0，V日E。因此，迈尔森最优拍卖设计问题可以形式化为下列最优化问题。 max E[∑t(0)] (21.5) f(·)EF 其中 F={f（·)=（y（·)，……·，yn（·),t（·),.…,tn（·))1f（·) 是贝叶斯激励相容的和事中个体理性的} 我们现在将迈尔森特征定理（参见19.7节）应用到上面的情形。首先，我们回顾 下列符号： ●令t（0）=E_[t（0，0-）表示当竞标人i报告自己的类型0且所有竞标人 j≠i如实报告他们的类型时竞标人i的期望转移。 ·令（θ)=E_[y（，0-）]表示当竞标人i报告自己的类型θ且所有竞标人 j≠i如实报告他们的类型时竞标人i得到拍卖物的期望概率。 ·U；（0）=0：（0）十t（0）（我们可以取非条件期望，这是因为竞标人的类型彼此 独立）。 我们说上面环境中的社会选择函数f（·）是贝叶斯激励相容的，当且仅当它满足 下列两组条件： （1）y（·）关于0非递减，其中i=1，，n。 (2)U;(0）=U;(0）+ yi（s)ds0∈；Vi=1,.,n。 另外，我们也可以根据事中个体理性定义断言：这里的f（·）是事中个体理性的 最优机制与迈尔森拍卖 当且仅当它满足下列条件 U;(0;)>00:∈0；Vi=1,.,n。 在上式中，我们假设竞标人不参与机制的期望效用为0。 根据上面的架构，最优拍卖机制问题式（21.5）可以改写为 max （0y：（0:）-U（0））（0）d0 (y;(),U;(-)iEN s.t. （i)y:（·）关于0:非递减，Vi=1，，n。 (i)y;(0) ∈ [0,1],y;(0) ≤1, Vi = 1.,,n, V0 ∈ 0。 （ii)U（0）=U;（0）+ y(s）ds，0;∈；Vi=1,.,n。 (iv)U;(0)≥0,0；∈0；Vi=1,.,n。 (21.6) 我们首先注意到如果约束条件（ii）得以满足，那么（iv）也将得以满足当且仅当 U：（0）≥0，Vi=1，，n。因此，我们可以将约束条件（iv）换为

（iv)U;(0;)≥0，Vi=1,.,n。 接下来，将约束条件（ii）代人目标函数，可得 。(0;(θ) -U;(0)-Jy;(s)ds );(0;)d0: 对上式进行分部积分可知，卖者最优化问题可以视为在约束条件（i）、（i）和（iv） 下，选择函数y（·）以及效用值U（θ），，U（0）使得 。[()J()[()]ao..d0 -U;(@) 最大。其中， ：(0:) J;(0;)=(0;1-Φ;(0.))= p;(0:) i(0:） 在上式中，Φ（·）是对应于密度（·）的累积分布函数，而且我们记（0）=1一Φ（0）。 J（o）这样的量称为实际评价（virtualvaluations）。 显然，前面的最大化问题的解必定满足U（0）=0，Vi=1，"，n。因此，卖者的 问题简化为下列问题：在约束条件（i）和（ii）下，选择函数y（·）使得 。[≥y(0.)J;(0)][1 x(0)]ao..d0 博奔论与机制设计 最大。 我们暂时忽略约束条件（i）。考察上面的表达式，可知，y（·）是这个放松约束后 问题的一个解当且仅当对于所有i=1，，n，我们有 [0:若J;（0:）<max{0，maxh≠iJ（0n)} y;(0)= (21.7) [1:若J:（0;）>max{0,maxh≠iJ（0n）} 注意，J（0:）=max{0，maxh≠iJ（0n））是一个零概率事件，它不会发生。 换句话说，如果我们忽略约束条件（i)，那么y：（·）是这个放松约束后问题的一 个解当且仅当拍卖物配置给拥有最高非负评价J：（0）的竞标人。现在，回顾（·）的 定义，可知 y;（0:)=E_[y(0，0-)] (21.8) 现在，如果我们假设J：（·）关于0为非递减的，那么容易看出式（21.7）给出的解 y：（·）关于0也为非递减的，这意味着y（·）关于0为非递减的（考察式（21.8）即 可知道这一点）。因此，在J：（·）为非递减的这个假设下，该放松约束后问题的解事实 上满足约束条件（i)。假设J：（·）为非递减的，式（21.7）给出的解似乎是我们最优 机制设计问题的解。J（·）关于0为非递减的这个条件容易实现，事实上，很多常见 的分布函数，例如均匀分布和指数分布，都能满足这个条件。 到此，我们已计算了最优机制的配置规则。现在我们转向支付规则。支付规则

t:（·）必须满足Vi∈N， t;(0）=E[t（0，0-)]=U;（0:）-0y：（0:）= y；（s）ds-0y（0;）（21.9) 考察上式以及下面的式（21.10）可知，如果支付规则t（·）满足式（21.10），那么它 也满足式（21.9)。 t;（0i，0-i）= yi（s,0-i)ds-0iy:（0,0-i）θ∈ (21.10) 上式可以改写成更符合直觉的形式，我们现在做此事。对于任何向量0-：，我们定义 z;（0-;)=inf{0;1J（0;)>0且J;（0）≥J;（0;），Vj≠i} 于是，2：（0-）是当其他竞标人类型为0-时，竞标人i的所有获胜报价的下确界，因此 {1:若0>2:（0-;) y;(0，0-）= 0:若0:<2;（0-i) 这样，我们有 {0:—2:（0-i）:若0:≥x;（0-:) yi（s,0-i）ds= [o ：若0:<x:（0-) 到此，我们终于可以改写式（21.10）了。将上面的两个表达式，即 yi（s，0-）ds以 及y：（0，0-）代人式（21.10），可得 最优机制与迈尔森拍卖 {—x;（0-:):若θ≥x;（0-i) t;(0，0-）= [o ：若0<z;(0-i) 这是当竞标人i获得拍卖物时必须支付的钱数，而且他支付的钱数等于他最低可能的获 胜报价。这样，我们就完成了对支付规则的描述。 口对迈尔森拍卖的一些观察 实际评价的单调性假设 我们假设实际评价函数J（·）关于0：（i=1，，n）为单调非递减的。如果每个 分布p：（·）使得它的失败率（hazardrate） pi 1一 为单调递增的，那么这个假设条件得以满足。很多常见的分布，例如均匀分布和指数分 布，都能满足这个条件。如果这个假设不能得到满足，我们可以使用所谓的熨平（iron- ing）方法来应急；这个方法源于Myerson[1]，它的思想是使用实际评价函数的最近的 单调变换来替代实际评价。

迈尔森拍卖为优势策略激励相容的 尽管在形式化最优拍卖问题时，我们仅要求激励相容性满足贝叶斯激励相容。然 而，可以证明，迈尔森拍卖事实上是优势策略激励相容的（Myersoni]），这是我们按 迈尔森方法设计拍卖时意外得到的一个合意结果。 迈尔森拍卖未必有配置效率 如果各个竞标人有不同的分布函数Φ：（·），那么拥有最大J：（0）值的竞标人未必 是报价最高的竞标人。因此，迈尔森最优拍卖未必有配置效率，从而未必有事后效率。 竞标人的对称性 如果竞标人是对称的，即==n=而且（·）=…=（·）=Φ（·），那 么迈尔森拍卖的配置规则正好与第一价格密封拍卖和第二价格密封拍卖中的配置规则相 同。在这种情形下，拍卖物将配置给报价最高的竞标人。在这种情形下，最优拍卖也变 得有配置效率。另外，注意，在这种情形下，我们在上面描述的支付规则将与第二价格 拍卖的支付规则相同。换句话说，如果竞标人是对称的，那么第二价格密封拍卖（维克 瑞拍卖）是最优拍卖。因此，很多时候，最优拍卖也称为改进的维克瑞拍卖（modified Vickrey auction) 21.3有效率的最优拍卖 博弈论与机制 KrishnaandPerryL2]认为拍卖应在满足配置效率（AE）、优势策略激励相容 （DSIC）和事中个体理性（IIR）约束下使得卖者收入最大。格林-拉丰定理（第18章） 告诉我们，任何满足DSIC和AE的机制必然是一个维克瑞-克拉克-格罗夫斯（VCG） 机制。因此，我们必须寻找一个VCG机制使得卖者收人最大。Krishna andPerryL2]将 设计 社会效用（socialutility）定义为有效率的配置的价值： SW(θ)= u;(k*(0),0;) j=1 SW-（0）=>;(k*（0），0) j#i 有了这些函数之后，我们可以将克拉克机制（关键人机制）的支付规则写为 t;(θ)=SW-;(O,0-i)-SW-;(0) KrishnaandPerryL2]将其一般化。固定一个向量θ，s=（si，S2，“，Sn）∈⊙称为基 （basis），这是因为它定义了支付规则。伴随基s的VCG机制（VCGmechanismwith basis）的定义为 t;(0|si)=SW(si,0-i)-SW-:(0) 可以看到，这个新机制也是优势策略激励相容的。现在选择一个合适的基，我们总可以 在VCG机制类中找到一个最优拍卖。KrishnaandPerryL2已证明，对于一件不可分割

的商品来说，经典的维克瑞拍卖是一个最优且有效率的拍卖。他们还证明了，当所有其 他竞标人的需求曲线都向下倾斜时，对于同一种商品多单位（数量）拍卖情形，维克瑞 拍卖是VCG机制中的一个最优机制。 21.4小结与参考文献 在本章，我们描述了迈尔森拍卖，它是机制设计理论中的一个重要结果。对于一个 卖者将一件不可分割的商品在一组竞标人中拍卖的情形，维克瑞拍卖在贝叶斯激励相容 与事中个体理性的约束条件下，使得卖者的期望收人最大。事实上，可以证明迈尔森拍 卖也是优势策略激励相容的，尽管它未必有配置效率。如果竞标人是对称的，那么迈尔 森拍卖有配置效率，而且它事实上与维克瑞拍卖相同。迈尔森拍卖也适用于购买一件不 可分割的商品的情形。 在描述迈尔森拍卖之前，我们构建了最优机制设计问题。用于确定最优机制的一个 适当机制可行集是所谓的激励可行集，这个集合由所有同时满足贝叶斯激励相容和事中 个体理性的社会选择函数组成。 在描述了迈尔森拍卖之后，我们简要介绍了有效率的最优拍卖，它们是在配置效 率、优势策略激励相容以及事中个体理性的约束条件下，使得卖者收入最大的拍卖。对 于一件不可分割的商品的拍卖来说，维克瑞拍卖是有效率的最优拍卖。 第 对于迈尔森拍卖的详细处理，读者可以参考Myerson[1]这篇经典论文，或者Vijay Krishna[2]这本优秀教材。 章 RileyandSamuelson[3]也独立地研究了一件不可分割的商品情形下的最优拍卖设计 最优 问题。他们假设竞标人是对称的。 机 对于后向拍卖（采购拍卖）情形下的迈尔森最优机制，读者可以参考Narahari， 制 与 Garg, Narayanam, and Prakash[4]。 迈 尔森拍卖 很多学者已从多个方面扩展和改进了迈尔森拍卖，以使其适用各种不同的具体环 境。下一章（第22章）讨论迈尔森拍卖在赞助搜索拍卖中的应用和扩展问题。 口参考文献 [1]Roger B.Myerson.“Optimal auction design".In:Mathematics of Operations Research 6(1)(1981)，pp.58-73. [2]Vijay Krishna.Auction Theory.Academic Press,San Diego,California, USA,2002. [3]J.G.Riley and W.F.Samuelson.“Optimal auctions".In:AmericanEconomic Review71（3）（1981)，pp.383-392. [4]Y.Narahari,Dinesh Garg，Ramasuri Narayanam,and Hastagiri Prakash. GameTheoreticProblemsinNetworkEconomicsandMechanismDesignSolutions. Springer,London,2009.

21.5习题 （1）考虑含有一个卖者和两个买者（智能体）的密封拍卖。卖者想卖掉一件不可分 割的商品。竞标人（买者）是对称的，他们的私人价值独立抽自[0，1]上的均匀分 布。报价最高者获胜。对于这个问题： ·若使用第一价格密封拍卖，求竞标人的均衡报价策略。 ·若使用第一价格密封拍卖，求卖者的期望收入。 ·若使用第二价格密封拍卖，求卖者的期望收人。 ·若使用迈尔森拍卖，求卖者的期望收人。 （2）迈尔森拍卖显然是贝叶斯激励相容的（因为贝叶斯激励相容是迈尔森拍卖的约 束条件之一）。我们还指出，迈尔森拍卖也是优势策略激励相容的。请证明这一点。 （3）在后向拍卖（采购拍卖）中，买者希望购买一件不可分割的商品，他的问题是 在贝叶斯激励相容与事中个体理性约束条件下使得期望成本最小。请对此构建迈尔森拍 卖。（提示：参见参考文献[4]） （4）考察当拍卖物是多件相同商品而不是只有一件不可分割的商品时，使用迈尔森 拍卖可能遇到的难题。特别地，考察拍卖物为两件相同商品的情形。