背包拍卖
接下来我们会设计背包拍卖(Knapsack Auctions)中的DSIC机制。它属于单变量环境，所以Myerson引理成立。
问题定义
在一个背包拍卖中，每一个投标人都有一个公开的大小(size)（例如一个电视广告的持续时间）和一个私人价值（例如一个公司为了让它的广告在超级碗期间播出愿意付出的代价）。卖家有一个容量（例如一个商业间隔的长度）。可行集定义为一个维的0-1向量，其满足。（与通常一样，代表是一个获胜的投标人。）这种背包拍卖模型的其他情景还包括想要在共享的服务器上存储文件，或是通过共享的通信链路传输数据流，或是想要在共享的超级计算机上运行程序的投标人。（当有一个容量有限的共享资源时，你面对的就是背包问题。）注意到物品拍卖（个相同的商品，每一个顾客只能买一个）是对于所有，以及的特殊情况。这里，不同的投标人可以有不同的大小。
现在让我们试着用我们的两步设计方案设计一个令人惊叹的拍卖。回顾一下，我们首先无理由地假设出价等于价值，从而决定我们的分配规则。然后我们接受这个假设带来的后果，并设计一个能够将分配规则扩展成DSIC机制的支付规则。
一个剩余最大化的DSIC机制
因为令人惊叹的拍卖注定要最大化剩余，第一步的答案是明确的：定义分配规则如下也就是说，分配规则解决了一个物品（即投标人）价值为给定的出价以及物品大小为事先已知的的背包问题1。根据定义，当投标人真实出价，这个分配规则能够最大化社会剩余。
临界出价
Myerson引理（部分(a)和(b)）保证了存在一种支付规则使得机制满足DSIC。这个支付规则很容易理解。固定投标人和其他投标人的出价。因为分配规则是单调的和0-1的，分配曲线非常简单：直到断点之前一直是0，在处它跳到1（如图1所示）。回顾支付公式：其中是分配函数在区间上的断点。因此，如果出价低于，他会输掉并且费用为零。如果出价高于，他支付。因此，支付他的临界出价(critical bid)――（在保持其他人出价不变的情况下）他保持获胜的最低出价。注意到这跟Vickrey拍卖完全一致。
图1：一个单调的0-1分配规则。
剩余最大化的计算困难性
1.2小节中提出的机制在假设真实报价——由DSIC性质支持的一个假设——的情况下能够最大化社会剩余。因此这个机制好像在提前知道价值的情况下解决了带有未知数据（）的剩余最大化问题。但是这个机制从Vickrey拍卖（课件2）的角度来看是令人惊叹的吗？回顾一下这意味着：
(1) DSIC.
(2) 假设真实报价的话,最大化剩余。
(3) 多项式运行时间。
答案是否定的。原因是背包问题是NP难的。因此除非，否则（1）中的分配规则没有多项式时间复杂度的实现方式。因此，上述性质（2）和（3）不相容。
没有令人惊叹的背包拍卖的现实（假设）激发了放松至少上述三个目标中的一个目标的尝试。但是放松哪一个呢？首先，注意到放松DSIC条件不会有任何帮助，因为是后面两个性质发生了冲突。
一个完美的有效途径是放松第三个限制，这一点在这门课程中不需要过多讨论。这一点对于背包拍卖而言更加吸引人，因为分配规则（1）可以通过动态规划的方法在伪多项式运行时间内实现（再一次的，细节参考任何一本本科生算法教科书）。更一般地，如果你的实例是小的或足够结构化的并且你有足够的时间和计算能力去实施最优的剩余最大化的，请尽力去做——这样得到的分配规则是单调的并可以被扩展为DSIC机制2。
算法机制设计
圣杯：无条件的DSIC
算法机制设计(Algorithmic mechanism design)是算法博弈论最初和研究得越多的分支，但我们没有时间在这门课程中完全涵盖它的内容。算法机制设计的主要思路是在保证第一个（DSIC）和第三个（多项式时间）约束前提下，尽可能少地放松第二个（剩余最优）约束。对单变量环境，Myerson引理暗示了以下目标是等价的：设计一个多项式时间和单调的分配规则并使它尽可能接近最大化社会剩余。
在过去的15年中算法机制设计能够取得如此巨大进步的一个原因是从技术角度讲，它跟一个相对成熟的领域近似算法(approximation algorithms)有很大的相似性。近似算法的首要目标是在多项式时间约束下，为NP难问题设计尽可能接近最优的算法。算法机制设计（对于单变量环境而言）刚好有相同的目标，除了算法还需要服从单调性的约束。Myerson引理暗示了算法机制设计归结到在一个有奇特约束（体现在单调性上）的“计算模型”中的算法设计问题——整个设计目标的博弈论都被整齐地装进了一个对分配规则的相对直觉的额外约束。
需要明确的是，算法机制设计中的“圣杯”是：在的大前提下，对尽可能多的感兴趣的NP难问题，应用已知的近似保证来逼近剩余最大化算法（并不一定要单调）——甚至用最好的近似保证。也就是说，除了我们为了多项式时间约束的损失之外，我们希望DSIC或单调约束增加尽可能少的剩余损失。回顾下到目前为止我们已经被宠坏的情况：通过精确的剩余最大化，DSIC及单调约束是“无条件”满足的，并且对于未知数据的精通的剩余最大化归约为已知数据的精确的剩余最大化。这种类似地归约对于近似的剩余最大化也成立吗？
背包拍卖（回顾）
为了在一个具体场景中探索上述问题，让我们回到背包拍卖。背包问题已经有一系列有好的最差性能保证的启发式算法。举例而言，考虑如下的分配规则，它通过一个简单的贪心算法在给定出价时选择一个可行集——一个总大小最多为容量的胜者的集合。不失一般性，我们假设对于每个都成立（删去那些的投标人不会造成坏的影响）。
(1) 对投标人进行排序并重新赋予下标，使得3 (2) 按照这个顺序挑选胜者直到加入某人后不满足可行性条件，然后停止4。
(3) 返回第(2)步中的结果，或出价最高的投标人，取决于谁创造了更多的剩余5。
上述的贪心算法是对背包问题的近似算法，因而有如下保证：
定理2.1. 假设真实出价，贪心分配规则的剩余至少是最大可能剩余的。
证明： （提纲）考虑真实的出价，已知大小和一个容量。假设，作为一个想象中的实验，我们放松这个问题的约束使得一个投标人可以以分数的形式被选择，同时带来等比例的价值。举例来说，如果一个价值为的投标人的被选中，那么他对剩余的贡献值为。对这个“分数背包问题”有一个贪心算法：按照上面步骤(1)对投标人进行排序，然后按照这个顺序选择获胜者直到整个容量全部用尽（按照需要，可以选取分数倍的最后的获胜者）。一种简单的exchange argument方法可以证明在分数背包问题的所有可行解上这个算法最大化剩余。
假设在最优的分数解中，排序后前个投标人获胜，而第个投标人部分获胜。步骤(1)和(2)取得的剩余刚好是前个投标人的总价值。贪心分配规则步骤(3)中取得的剩余至少是第个投标人的总价值。这两个解中更好的一个至少是最优分数解的剩余的一半，而最优分数解的剩余最少也是原问题的最优（非分数）解的剩余。#
如果有进一步的假设，贪心分配规则会变得更好。例如，如果对每一个投标人有，其中，那么，即使第3步省略了，近似也能保证提高到。
我们知道剩余最大化能够生成一个单调的分配规则，那么近似的剩余最大化呢？至少对于上述的贪心分配规则，我们仍有单调性（见习题18）。
你可能会误以为每一个合理的分配规则都单调。我们见过的唯一一个不单调的规则是单物品拍卖中的“出价第二高的投标人获胜”的规则，而这个规则我们不关心。警告：自然的分配规则并不总是单调的。举例来说，对每个，背包问题都有一个多项式时间复杂度的近似算法——一个“完全的多项式时间近似方案(FPTAS)”。按照这个算法直接实施的分配规则并不单调，尽管它可以在不影响近似保证的前提下被调整为满足单调性（细节见习题）。这是算法机制设计的工作特点：考虑一个NP难的优化问题，检查现在的近似算法是否直接导出一个DSIC机制，如果不是，调整它或设计一个新的近似算法，同时希望不要损失近似保证。
黑盒归约
到我们目前为止讨论的单变量问题中，算法机制设计十分成功。对这类问题的现有近似算法要么是单调的，要么可以被修改为单调的，正如在上述的背包拍卖和习题中那样，这种成功影响如此之广以至于不得不问：
是否存在一个自然的单变量问题，通过多项式时间算法取得的最好近似保证严格好于一个多项式时间并且单调的算法的最好近似保证？
当然，一个否定性的结果会令人格外兴奋——这会意味着，正如精确的剩余最大化那样，单调性/DSIC约束能被无条件地加上。一种证明这样的笼统的肯定性结果的方法是通过“黑盒归约(black-box reduction)”：一种通用的将可能不单调的指数时间算法在不牺牲近似保证的前提下转变为一个单调的指数时间算法。这样的归约十分有趣，即使会使近似系数有一个常数量的损失。
Chawla et al.[1]最近表明对于单变量环境，没有一个完全通用的黑盒归约。尽管对于它的一些重要子集，黑盒归约确实存在。举例来说，这样的归约是否应用于向下封闭的(downward-closed)环境？在这样的环境中，正如我们遇到的所有问题一样，给一个投标人更少的物品并不导致一个不可行的结果6？
显示原理
回顾DSIC条件
到目前为止我们的机制设计理论只研究了DSIC机制。我们再次重申有很好的追求DSIC保证的原因。首先，对于参与者而言很容易弄清在DSIC机制中做什么：只需要遵循明显的占优策略。其次，在一个相对比较弱的假设，即所有的参与者都遵循占优策略下，设计者可以预测机制的结果。然而，类似首价拍卖这样的非DSIC机制在实践中也很有用。
那么非DSIC机制能否做到DSIC机制做不到的事情呢？为了回答这个问题，让我们将DSIC定义中混为一谈的两个分别的假设拆开：
(1) 不管私人价值是什么，机制中的每个参与者都有一个占优策略。
(2) 这个占优策略是直接显示的(direct revelation)，即所有参与者向机制真实汇报他的私人信息。
有一些机制满足(1)但不满足(2)。举一个愚蠢的例子，想象一个单物品拍卖中，一个卖家在给定出价为时按照出价实施Vickrey拍卖。此时每个投标人的占优策略是按价值的一半出价。
超越占优策略均衡
假设我们放宽条件(1)。缺陷是我们需要更强的假设来预测参与者的行为和机制的结果；举例来说，我们可能考虑在公共前提下的贝叶斯纳什均衡（见关于首价拍卖的习题6）或一个完全信息模型中的纳什均衡（见关于GSP竞价搜索拍卖的习题3）。但是如果我们愿意做出这样的假设，我们能比DSIC机制做得更好吗？
答案是“有时候是的”。为了这个原因，并且因为非DSIC机制在实践中很常见，建立超越DSIC机制的理论也很重要。我们会在更高级的课程中涉及这个内容。一个简单的原则是，像我们之前介绍的那些足够简单的问题，DSIC机制能够做到任何非DSIC机制做的事。在高级课程中讨论的更复杂的问题中，减弱DSIC约束（例如实施贝叶斯纳什均衡）经常会使你做到一些DSIC机制做不到的事情（假设参与者能够弄清并遵循我们想要的均衡）。在这样的场景中，DSIC和非DSIC机制无法比较——前者有更强的激励保证，后者有更好的性能保证。哪一个更重要取决于应用的细节。
显示原理和诚实的无关性
显示原理表明，给定3.1小节中的要求(1)，就没有必要放松要求(2)：它是无条件随之而来的。
定理3.1(显示原理). 对于每一个参与者都有占优策略（无论私人信息是什么）的机制，都有一个等价的直接显示的DSIC机制。
证明： 利用一种模拟方法证明。见图2。根据假设，对于某一个参与者和可能有的私人信息，在给定的机制中有一个占优策略。
图2：显示原理的证明。在给定一个有占优策略的机制的情况下构造一个直接显示的机制。
构造如下的机制，其中参与者代理了遵循合适的占优策略的责任。准确的说，（直接显示）机制从局中人那里接受密封的报价。它提交报价给机制，并选择和相同的结果（例如拍卖的获胜者和出售价格）。
机制满足DSIC：如果一个参与者有私人信息，那么上报一个不等于的出价会导致在中进行一个不是的策略，而这只会降低的效用。#
定理3.1的要点在于，至少在原理上，如果你设计了一个有占优策略的机制，那么也可以设计一个直接显示（在拍卖中是诚实报价）是占优策略的机制。
很多除了占优策略均衡之外的均衡概念，例如贝叶斯纳什均衡，也有他们各自的显示原理。这样的原理表明，给定了激励约束，直接显示是一种不失一般性的做法。因此，诚实本身并不重要。真正使机制设计困难的地方在于一个在某种均衡意义下想要的结果（不失一般性，假设为真实上报）的要求。改变均衡概念的选择会导致完全不同的机制设计理论，其中更强的均衡概念（例如占优策略均衡）相对更弱的均衡概念（例如贝叶斯纳什均衡）而言要求更弱的行为假设，但更难达到。
脚注：
1 一个背包问题由个变量定义：物品价值，物品大小和一个背包容量。目标是计算能够最大化总价值同时总大小最多为的物品的子集。更多细节请参阅任意一本本科生教材。
2 警告一下，费用也需要被计算，并且通常要额外解个剩余最大化问题（对每一个局中人需要求解一个）。见练习题16。
3 高的出价和小的大小使一个投标人更具吸引力。我们通过对投标人按照每单位容量带来的价值排序来进行权衡。
4 也可以继续按照这个顺序往后挑刚好还合适的投标人——这只会使结果变得更好。
5 这一步的原因是第(2)步中的结果当存在一个价值很大而大小有很大的投标人的时候会变得高度次优。也可以将投标人按照非减的出价进行排序并且贪心地挑选他们——这只会使结果变得更好。
6 如果DSIC约束被减弱为贝叶斯纳什均衡的实现，那么确实存在相当一般的黑盒归约。我们会在以后更高级的课程中讨论。
参考文献
[1] Shuchi Chawla, Nicole Immorlica, and Brendan Lucier. On the limits of black-box reductions in mechanism design. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, pages 435-448. ACM, 2012.