收入最大化的挑战
回顾福利最大化
到目前为止，我们主要关注精确地或近似地最大化福利(welfare)目标的机制设计 在某个集合中的所有可行解上。仅仅是作为一个副作用，收入在福利最大化的拍卖中产生，作为一个激励参与者上报私人信息必需的“恶魔”。这一讲我们开始讨论明确设计来使得收入越高越好的拍卖。
我们一开始考虑福利目标是由于以下几个原因。一是相对很多现实场景拍卖（比如说无线频谱拍卖），首要目标是福利最大化――收入也很重要但通常不是首要目标。同样地，在竞争市场中，通常认为一个卖家应该关注福利最大化，因为否则的话其他人会关注（潜在地会偷走他们的顾客）。
我们通过福利最大化开始的第二个原因是为了教学：福利是特殊的。在每一个单变量环境（甚至更一般的情况下，见课件7），都有一个DSIC机制能够事后(ex post)最大化福利――就好像设计者提前知道所有的私人信息()。在这种意义上，DSIC约束能被“无条件”满足。这是一个非常惊人的强的性能保证，并且它一般不能被其他目标函数所获得。
一个投标人和一个物品
下面这个琐细的例子只是用来示范。考虑只有一个物品和一个投标人的情况，投标人的私人价值为。因为只有一个投标人，直接显示的DSIC拍卖的设计空间很小：就是“标价(posted price)”或者要么接受、要么离开的提议1。如果一个卖家标价为，那么它的收入要么是（如果），要么是0（如果)。
在这种场景下最大化福利的问题没有意义：只要设置，从而你可以一直免费地把这个物品送给投标人。注意到这个最优的标价与无关。
假设我们想要最大化收入。我们应该如何设置？事后地（例如，用心灵感应知道了），我们会设置。但是是私人的，我们应该怎么做？这个问题如何解答并不明显。
关键问题在于，对于收入这个目标，对于不同的输入不同的拍卖会各有好坏。对于一个物品和一个投标人，标价20对于稍微大于或等于20的情况会做得很好，但对于更小的输入做得更差（而在这些情况下，小的标价做得更好）。这样的权衡对于学习算法的学生很常见。举例来说，不同的排序算法（例如，插入排序和快速排序）在不同的输入上各有快慢。对于旅行商问题，不同的启发式算法会有不同的误差。有一个与输入无关的DSIC机制的福利最大化问题确实比较特殊。
贝叶斯分析
想要比较不同的收入最大化的拍卖需要一个用来分析不同的输入造成的权衡的模型。今天我们介绍做这件事情最经典也是研究得最多的模型：平均情况(average-case)或贝叶斯分析(Bayesian analysis)。我们的模型由下面这些元素组成：
- 一个单变量环境（见课件3）。
- 参与者的私人价值假设服从分布，密度函数，支撑集在区间上2。我们假设分布是独立的（但不一定同分布）。在实际中，这些分布一般是从数据中推导出的，例如过去的拍卖中的出价。
- 机制设计者事先知道分布。投标人的具体价值仍然跟之前一样是私人的。因为我们着眼于DSIC拍卖，其中投标人有占优策略，因此他们不需要知道分布3。
在贝叶斯环境中，如何定义“最优的”拍卖是明确的――它是在所有的DSIC拍卖中拥有最高的期望收入的拍卖，其中期望是相对于给定的分布在价值上而言（假设真实出价）。
回顾一个投标人和一个物品
在我们的贝叶斯模型中，一个投标人和一个物品的拍卖现在很容易分析了。标价的期望收入很简单： 给定一个分布，通常很容易求出最好的。对于分布最好的标价被称作垄断价格(monopoly price)。既然DSIC机制用的是标价（或它们的随机），使用垄断价格便是收入最大化的拍卖。举例来说，如果是上的均匀分布（例如，在上成立），那么垄断价格是，期望收入为。
两个投标人的情况更加复杂，并且DSIC拍卖的设计空间变得更大。举例来说，考虑有两个投标人的单物品拍卖，他们的价值服从区间上的均匀分布。我们当然可以使用Vickrey拍卖，它的收入是更小的出价的期望值，也就是（作为练习）。
我们也可以给Vickrey拍卖加上一个底价(reserve price)，就有点类似eBay拍卖中的的“起拍价”。在一个底价为的Vickrey拍卖中，分配规则将物品奖励给出价最高的投标人，除非所有的出价都低于，而在这种情况下没有人会得到这个物品。相应的支付规则要求获胜者（如果有的话）支付第二高的出价或者中的更高的一个。从收入的制高点来看，加入一个底价既有好处也有坏处：当所有的出价都低于的时候你失去了收入，但是当仅有一个出价高于的时候你的收入增加（因为售价被提高了）。在我们的情况下，增加一个的底价被证明带来净收益，将期望收入从提高到了（作为练习）。但是我们能做得更好吗？也许使用一个不一样的底价，或者一个完全不一样的拍卖形式？尽管DSIC拍卖丰富的设计空间是的这个问题变得很吓人，这一讲中剩余的部门会提供一个完整的答案，而这个答案最初来源于Myerson[1]。
期望收入等于期望的虚拟福利
我们的目标是对于每一个单变量环境和分布，描述最优的（即期望收入最大化的）DSIC拍卖4。我们从一个初步的观察开始。
步骤0：根据上一讲中的显示原理，每一个DSIC拍卖都等价于――并且因此拥有相同的期望收入――一个直接显示的DSIC机制。因此从现在开始，我们可以只考虑直接显示机制。我们会在这讲后面的内容中一直假设真实出价(即，)。
一个拍卖的预期收入为
其中期望是相对于投标人的价值的分布而言。现在还不清楚如何直接在DSIC机制的设计空间上最大化表达式(2)。在这一部分，我们推导一个拍卖的预期收入的第二个公式。这个公式只跟一个机制的分配规则有关，而与支付规则无关，因此有一个更加容易最大化的形式。
作为开始，回顾第3讲中的Myerson支付公式： 这个公式假设了分配函数可微。通过标准的高等微积分，这个公式对于更一般的任意单调函数都成立，包括分段常数函数，只需要对导数和对应的积分给出良好的定义。类似地，在下面的证明步骤中，用到的分部积分等积分操作，可以适用于任意的有界的单调函数而不会带来巨大的困难。我们把细节留给感兴趣的读者5。
方程(3)表明支付是完全由分配规则决定的。因此，至少在原理上，我们可以将拍卖的预期收入仅仅表示为它的分配规则的函数，而不需要显示地体现与支付规则的联系。那么这样得到的收入公式与原来的相比是不是更加容易进行最大化呢？这个问题在实际做之前很难回答，因此让我们来做吧。
步骤1：固定和；回顾下是一个随机变量（跟一样），而且之后我们会通过积分消去它。
根据Myerson费用公式(3),我们可以将给定下投标人的预期费用表示为 注意到在第一个等号中我们利用了投标人价值的独立性――固定的与服从的分布毫无关系。
正如我们知道，这一步从原理上是可行的――将费用改写为分配规则的形式。为了使它变得有用，我们需要进行一些简化。
步骤2：当你遇到不知道该怎么办的双重积分（或双重求和）时，总是值得尝试下交换积分顺序。这里，交换积分顺序推导出了一个优美的简化，如下式所示：
步骤3：当试图将积分表示为更容易理解的形式时，分部积分总是值得尝试，特别是当表达式中有一个明显的导数时。这里，我们又进一步简化：
注意到我们可以将最后的表达式理解为一个期望值，其中服从分布。
步骤4：为了简化和帮助理解上面的表达式，我们引入了一些新的符号。虚拟价值(virtual valuation)表示如下：
注意到一个投标人的虚拟价值只取决于它自己的价值和分布，与其他人无关。
举例来说，假设投标人的价值服从上的均匀分布。那么，，以及，对于。注意到虚拟价值可能为负！在练习中可以看到更多的例子。
步骤1-4小结：对每一个投标和，有
注2.1：虚拟价值在贝叶斯最优拍卖的设计中起到中心作用。对于他们意味着什么有什么直觉的解释吗？一种简单的理解形式如下：
将变作从投标人那里得到的最大收入，第二项看做由于提前不知道导致的不可避免的收入损失（即，“信息租金”）。第二种更准确的解释把看做“收入曲线”在处的斜率，而收入曲线描绘的是从价值服从的用户那里得来的期望收入，作为售出概率的函数。练习题说明了这种解释。
步骤5：在公式(4)的两边对取期望得：
步骤6：（两次）利用期望的线性来完成推导： 公式(5)中的最后一项就是我们对于一个拍卖的期望收入的第二个公式，并且我们应该为它的简洁感到高兴。注意到如果我们从表达式中移去，我们就会剩下一个老朋友：拍卖的期望福利。基于这个原因，我们定义为拍卖的虚拟福利。我们已经证明了，对每一个拍卖： 特别地，在DSIC拍卖的设计空间上最大化期望收入归结到最大化期望虚拟福利。
贝叶斯最佳拍卖
一个像(6)这么简单的公式居然会成立。它表明了，尽管我们只考虑费用，我们可以将注意力放在一个只跟机制的分配规则有关的优化问题上。第二种形式更加具有可操作性，并且我们将决定最大化期望虚拟福利的拍卖。
最大化期望虚拟福利
作为热身，让我们做两个额外的假设。首先，考虑一个单物品拍卖。其次，假设投标人服从独立同分布。也就是说，所有的都是一个相同的，因此所有的虚拟价值函数都相同。
我们应该如何选择分配规则来最大化期望虚拟福利 我们对于每一个输入有选择的自由，但是无法控制输入分布或虚拟价值。因此，最明显的解决方法是逐点最大化：对于每一个输入，选取使得虚拟福利最大（受制于可行性）。我们称其为虚拟福利最大化分配规则(virtual welfare-maximizing allocation rule)。
在一个单物品拍卖中，对于每一个有可行性约束，虚拟福利最大化规则只需把物品奖给拥有最大虚拟价值的投标人。然而不全是这样：回顾下虚拟价值可能是负的（例如，，其中在0到1之间均匀分布）。如果每一个投标人都有一个负的虚拟价值，那么当不把物品给任何人时虚拟福利取得最大值。（我们已经在一个投标人的例子中见到了在某些情形下通过不卖物品来最大化收入。）
对每个分别选取最大化定义了一种在所有分配规则（无论单调与否）中最大化期望虚拟福利(7)的方法。关键问题是：这个虚拟福利最大化规则单调吗？如果是的，那么它可以被扩展成一个DSIC拍卖，而且根据(6)这个拍卖有最大可能的期望收入。
对这个关键问题的回答取决于价值分布。如果对应的虚拟价值函数递增，那么虚拟福利最大化分配规则是单调的。
定义3.1. 一个分布是正规的(regular)，如果对应的虚拟价值函数是严格递增的。
对于大部分应用，定义3.1可以被放松为非减的虚拟价值函数。
我们看到上的均匀分布有虚拟价值函数，因而是正规的。对于其他均匀分布，指数分布和对数正态分布也是这样。不正规的分布包括许多多模分布和有着足够重尾的分布。具体例子见练习题。
让我们回到投标人服从独立同分布的单物品拍卖中，并加上假设价值分布是正规的。虚拟福利最大化分配规则，将物品分配给具有最高非负虚拟价值的投标人（如果有的话），是单调的并产生最优拍卖。进一步地，因为所有投标人都拥有相同的递增虚拟价值函数，拥有最高的虚拟价值的投标人同时拥有最高价值。因此这个分配规则等于保留价格为的Vickrey拍卖。从而对于独立同分布的投标人和一个正规的价值分布，eBay（有一个合适的起拍价时）采用了最优的拍卖形式。考虑到DSIC拍卖设计空间的丰富，令人惊叹的是这样一个简单而实用的拍卖是最优的。
更一般的，考虑任意一个单变量环境和价值分布，虚拟福利最大化分配规则现在被定义为，对于每一个，选取最大化虚拟福利的可行分配。如果每一个是正规的，那么这个分配规则是单调的（见练习）。把它与满足DSIC约束的唯一的支付规则结合起来，我们得到了最优拍卖。在这个意义上，我们已经解决了每一个有正规的价值分布的单变量环境下的贝叶斯最优拍卖问题。
进一步拓展
这一讲中提出的理论（见于[1]）更加具有一般性。首先，它可以被扩展到非正规的价值分布6。因为在这种情况下虚拟福利最大化分配规则不是单调的，必须更加努力地去求解最大化期望虚拟福利的单调的分配规则。这可以通过“整理”虚拟价值函数使得它们单调来实现，同时保留重要的虚拟福利。见Hartline[2]的第三章。
其次，虽然今天的课件为了简单，局限在了DSIC拍卖，我们求出的（DSIC）最优拍卖在一个更大的“贝叶斯激励相容”机制的集合上也是最优的。举例而言，首价拍卖形式无法获得比最好的DSIC拍卖更多的收入（在均衡时）。因此，对于单变量问题中的收入最大化，DSIC约束无条件满足。这种扩展并不需要今天我们所涉及内容之外的重大的新的想法。我们会在课程CS364B中讨论。
脚注：
1 准确的说，这些是确定性的拍卖方法。你也可以在标价中进行随机，但是这个例子想要说明的重点是一样的。
2 回顾下表示一个服从分布的随机变量值最多为的概率。
3 这一讲中的结论也适用于更一般的“贝叶斯纳什激励相容(Bayes-Nash incentive-compatible)”的拍卖；在这种情况下，投标人也必须知道分布。
4 我们今天不会证明，但是我们设计的拍卖在一个更强的意义上也是最优的，见3.2小节的讨论。
5 举例而言，每一个有界的单调函数都可积，并且除了一系列零点都可微。
6 分布间的独立性是至关重要的，并且无法在不改变结果的情况下进行放松。
参考文献
[1] Roger B Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58-73, 1981.
[2] Jason D Hartline. Mechanism design and approximation. Book draft. October, 2013.