最优拍卖可以很复杂

上一讲中，我们证明了拍卖理论中的最重要结果。回顾一下，对于价值分布为$F_1, \dots, F_n$的单变量环境中的每一个DSIC拍卖$(\mathbf{x}, \mathbf{p})$，期望收入等于期望虚拟福利： $$\mathbb{E}_{\mathbf{v}}\left[\sum_{i=1}^{n} {p_i(\mathbf{v})}\right] = \mathbb{E}_{\mathbf{v}}\left[\sum_{i=1}^{n} \varphi_i(v_i) \cdot x_i(\mathbf{v}) \right] \qquad \qquad \qquad \qquad (1)$$ 定义虚拟福利最大化分配规则如下： $$\mathbf{x}(\mathbf{v}) := \text{argmax}_{X} \sum_{i=1}^{n} \varphi_i(v_i) x_i(\mathbf{v})$$ 对于每一个输入$\mathbf{v}$。 如果每一个$F_i$是正规的，意味着对应的虚拟价值函数 $$\varphi_i(v_i) = v_i - \frac{1-F_i(v_i)}{f_i(v_i)}$$ 是严格递增的，那么虚拟福利最大化分配规则是单调的并且在我们定义了合适的费用后，在所有的DSIC拍卖中最大化期望收入。最优拍卖的这个特性可以被扩展到非正规的分布，但是这种扩展需要更多的工作（见参考文献[1]的第三章）。

作为这个一般特性的推论，我们注意到在独立同分布的投标人和正规的分布$F$情形下最优的单物品拍卖异常简单：它就是Vickrey拍卖，加上了保留价格$\varphi^{-1}(0)$。这是拍卖理论的一个真的“杀手级应用”――它对于拍卖设计给出了干脆的，概念上清晰的，并且实际中有用的指导。

如果我们令问题变得复杂一些，情况变得困难起来。再次考虑单物品拍卖，但是放松投标人的价值分布式相同的假设；它们仍是独立的和正规的。最优拍卖会变得诡异，而且不同于任何实际中使用的拍卖（见练习题）。举例来说，不是最高出价者的投标人可能会赢。赢者的费用几乎不可能向没有学过虚拟价值的人解释清楚——相比之下，独立同分布场景中最优拍卖就简单为有一个合适的起拍价的eBay拍卖。这种诡异性是不可避免的，如果你对模型（例如，所有$F_i$）有100\%的确信并且你希望最大可能的期望收入的话——在现有的分配和支付规则中没有一个是你能用的。

今天我们要寻找比理论上最优的拍卖更简单，更实用和更鲁棒的拍卖。因为最优性要求复杂度，我们只能希望我们的拍卖是近似最优的。这是第二次我们通过近似来逃避完全的最优性带给我们的困扰。在算法机制设计（第4讲），当底层的福利最大化问题是NP难时，我们通过近似来获得计算可行性。类似地，这里我们由于它的“复杂性”拒绝了最优拍卖，并且利用近似来获得相对的简便。不同于算法机制设计，其中“低复杂度”被准确地定义了（多项式运行时间），这里我们留下了大量未定义的类似“简单”，“实用”，“鲁棒”这样的术语。对这些模糊的概念给出定义，并对简单的接近最优的拍卖设计给出有用的指导是这个领域中十分重要的研究问题。

上一讲中介绍的贝叶斯最优拍卖是微观经济学的一部分，可以追溯到1981年[2]。作为比较，这一讲中列出的研究日程主要是在过去的5年中发展起来的，并主要在计算机科学文献中。上一讲中的经典理论是这些最近工作的基础。

先知不等式

这一部分介绍了一个最优停止理论中的有趣结论。下一部分会利用它设计一个非i.i.d.场景下的相对简单并且可证明的接近最优的单物品拍卖。

考虑有$n$个结算的游戏。在阶段$i$，你被提供了服从分布$G_i$的非负奖金$\pi_i$。你事先知道分布$G_1, \dots, G_n$并且这些分布之间独立。你只有在阶段$i$时才被告知$\pi_i$的取值。在看到$\pi_i$，你可以要么接受奖金并结束游戏，要么放弃奖金并进行到下一个阶段。决策的难度起源于在早期接受了一个合理的奖金从而错失了以后的更大的奖金以及不得不在最后的几个阶段中接受一个糟糕的奖金的风险之间的权衡。

Samuel-Cahn[3]提出的先知不等式(Prophet Inequality)提供了一种几乎能够做到跟一个具有完全看透未来能力的先知一样好的简单策略。

定理2.1 (先知不等式). 对于独立分布的每一个序列$G_1, \dots, G_n$，有一种策略能够保证期望收益$\frac{1}{2} \mathbb{E}_{\pi} [\text{max}_i \pi_i]$。实际上，存在一种阈值策略$t$，当且仅当$\pi_i \ge t$时接受奖金$i$。

证明：令$z^+$表示$\text{max}\{z, 0\}$。考虑阈值为$t$的阈值策略。很难直接比较这种策略的期望收益与先知的期望收益。因此，计划是分别推导容易比较的上下界。

令$q(t)$代表阈值策略根本不接受奖金的概率。注意丢弃最后一个阶段的奖金是明显次优的！随着$t$增加，风险$q(t)$增加，但是接受了的奖金的平均值上升。

这种$t$阈值策略能获得多少收益？以概率$q(t)$是0，而以概率$1-q(t)$至少是$t$。让我们提高第二种情况下的下界。如果刚好有一个奖金$i$满足$\pi_i \ge t$，那么我们应该获得$\pi_i - t$的“额外收益”并且超过我们的基础收益$t$。如果至少两个奖金超过阈值，比如$i,j$，那么情况会复杂：我们的“额外收益”要么是$v_i - t$或$v_j - t$，取决于$i,j$中的哪一个属于更早的阶段。让我们懒一些并且不考虑这种复杂性：当两个或多个奖金超过阈值时，我们只考虑基础值$t$作为策略的收益。

正式的，我们有如下的下界： $$\begin{align} &\;\mathbb{E}[\text{t阈值策略的收益}] &\;\\ &\ge(1-q(t)) \cdot t + \sum_{i=1}^{n} \mathbb{E}[\pi_i -t | \pi_i \ge t, \pi_j < t \; \forall j \ne i]\mathbf{Pr}[\pi_i \ge t] \cdot \mathbf{Pr}[\pi_j < t \; \forall j \ne i] &\qquad (2)\\ &=(1-q(t)) \cdot t + \sum_{i=1}^n \underbrace{\mathbb{E}[\pi_i - t|\pi_i \ge t]\mathbf{Pr}[\pi_i \ge t]}_{=\mathbb{E}[(\pi_i - t)^+]} \cdot \underbrace{\mathbf{Pr}[\pi_j < t \; \forall j \ne i]}_{\ge q(t)} &\qquad (3)\\ &\ge (1-q(t)) \cdot t + q(t) \sum_{i=1}^n \mathbb{E} [(\pi_i - t)^+] &\qquad (4) \end{align}$$

其中在(2)式中我们利用了$G-i$间的独立性分解两个概率项，并且在(3)式中丢弃条件中的$\pi_j < t$，对于每一个$j \ne i$。在(4)式中，我们利用了$q(t) = \mathbf{Pr}[\pi_j < t \; \forall j] \le \mathbf{Pr}[\pi_j < t \; \forall j \ne i]$。

现在我们推导一个容易与(4)式比较的先知的期望收益$\mathbb{E}[\text{max}_i \pi_i]$的上界。原始的表达式并不包含策略的阈值$t$，因此我们加一项减一项$t$之后得： $$\begin{align} \notag \mathbb{E}\left[\text{max}_i \pi_i \right] &= \mathbb{E} \left[t + \text{max}_i(\pi_i -t)\right]\\ \notag &\le t + \mathbb{E}\left[\text{max}_i (\pi_i - t)^+\right] \\ &\le t + \sum_{i=1}^n \mathbb{E}\left[(\pi_i - t)^+\right] \qquad \qquad \qquad \qquad (5) \end{align}$$

比较(4)式和(5)式，我们可以设置$t$使得$q(t) = \frac{1}{2}$——即，有50\%的几率接受奖金——来完成证明。如果由于$G_i$的质点没有这样的$t$，那么对表达式进行一个小小的扩展也能产生相同的结果（见问题集2）。#

我们对定理2.1的证明中表明了下一部分中会用到的更强的结论。我们的关于$t$阈值策略的下界(4)当至少有两个奖金超过阈值$t$时只考虑了$t$单位的价值；只有当刚好有一个奖金超过阈值时才会对(4)中的第二项“额外收益”有贡献。这意味着，即使当有多个超过阈值的奖金存在时，策略选取它们中最差（最小）的一个，$\frac{1}{2}\mathbb{E}[\text{max}_i \pi_i]$的收益保证也成立。

简单的单物品拍卖

我们现在开始研究一个单物品拍卖的例子，其中有$n$个投标人，价值服从正规的分布$F_1, \dots, F_n$（并不一定同分布）。我们利用先知不等式来设计一个相对简单的，接近最优的拍卖。

关键点在于投标人的虚拟价值$\varphi_i(v_i)^+$，如果非负的话为第$i$阶段的奖金。（$G_i$是$F_i$推导出的对应分布；既然$F_i$是独立的，$G_i$也是。）为了看出与先知不等式的基本联系，注意到一个最优拍卖的期望收入为$\mathbb{E}_{\mathbf{v}}[\sum_i \varphi_i(v_i) x_i(\mathbf{v})] = \mathbb{E}_{\mathbf{v}}[\text{max}_i \varphi_i(v_i)^+]$，而后一项正是一个面对奖金$\varphi_1(v_1)^+, \dots, \varphi_n(v_n)^+$的先知所获得的期望价值。

现在考虑任何具有下面形式的分配规则：

(1) 选取$t$使得$\mathbf{Pr}[\text{max}_i \varphi_i(v_i)^+ \ge t] = \frac{1}{2}$。

(2) 将物品给$\varphi_i(v_i) \ge t$的投标人$i$（如果有符合这个条件的投标人的话），当出现平局时在多个候选的赢者之中任意选一个（保证单调性）。

先知不等式的更强形式立刻表明对于上述形式的每一个拍卖都满足： $$\mathbb{E}_{\mathbf{v}} \left[\sum_{i=1}^{n} \varphi_i(v_i)^+ x_i(\mathbf{v}) \right] \ge \frac{1}{2} \mathbb{E}_{\mathbf{v}}\left[\text{max}_i \varphi_i(v_i)^+ \right]$$

举例来说，这里有一个具体的这样的分配规则：

(1) 对每一个投标人$i$设置一个保留价格$r_i = \varphi_i^{-1} (t)$，其中$t$如上文定义。

(2) 将物品给满足保留价格的最高投标人（如果有的话）。

这个拍卖首先通过保留价格过滤投标人，然后简单地把物品给剩下的人中出价最高的。这个拍卖从两方面看来比最优拍卖明显简单。首先，赢的投标人的相应费用正式他的保留价格和满足保留价格的其他人的最高出价中的更大的一个，因此虚拟价值函数只被用来设置保留价格，并且只有$\varphi^{-1}(0)$有用。其次，只要出价最高的投标人达到了他的保留价格，他就会赢。

这种“简单”的拍卖似乎比一个最优拍卖更加容易实施，但是还有一个问题：保留价格对于不同的投标人而言是不同的。一些现实的拍卖会使用非匿名的保留价格——在竞价搜索拍卖中，“高质量”广告主通常会比低质量广告主有一个更低的保留价格——但这种情况很少见。举例而言，在eBay上，你只需要设置一个起拍价，即使你知道（例如从拍卖历史）投标人是非i.i.d.的。

一个有趣的开放研究问题是理解在一个价值服从非i.i.d.正规分布的单物品拍卖中，一个具有匿名的保留价格的Vickrey拍卖（例如eBay）能够在多好的程度上近似最优的期望收入。部分结果是已知的：有拍卖能够至少取得最优收入的25\%。但是没有拍卖能够一直取得超过50\%的最优收入[4]。

更一般的，设计可证明的近似最优收入的简单拍卖在过去的5年时间里一直是一个热点研究问题。综述见[1]的第4章。

无先验信息的拍卖和Bulow-Klemperer定理

这一节中讨论上一讲中提到的对最优拍卖的另一个批评：假设卖家提前知道了价值分布$F_1,\dots, F_n$。在某些应用中，有很多的数据并且投标人的偏好并不会剧烈变化时，这是一个合理的假设。但是如果卖家不知道，或不肯定价值分布呢？这是在一个“轻市场”中的相关问题，当没有很多的数据时，包括很少使用（但很有潜在价值）的搜索查询的关键词排名。

将对分布的先验知识的移除似乎会将我们推回之前单投标人单物品中的困惑（课件5），而之前的困惑导出了贝叶斯分析途径。区别在于我们会继续假设投标人的价值服从某些分布，只是这些分布事先不知道。也就是说，我们现在在拍卖的分析中利用分布，而不是在拍卖的设计中。目标是设计一个描述上与底层分布无关的拍卖，同时又能够取得跟事先知道分布的情况一样好的性能。这种设计好的无先验信息的(prior-independent)的拍卖最早由[5]提出，并且在过去的三年中一直是一个活跃的话题，想要了解最近的发展可以参考[1]的第5章。

今天，我们要讨论一个古典拍卖理论中优雅的结果，同时也是无先验信息的拍卖的重要先去。Vickrey拍卖的期望收入明显比最优拍卖的要少，然而下面由Bulow和Klemperer[6]提出的结果显示，在Vickrey拍卖的环境变得稍微更加具有竞争性时，上面的不等式关系会发生逆转。

定理4.1 (Bulow-Klemperer定理[6]). 令$F$表示一个正规分布，$n$表示一个正整数。那么 $$\mathbb{E}_{v_1, \dots, v_{n+1}} [Rev(VA) (n+1 \; bidders)] \ge \mathbb{E}_{v_1, \dots, v_{n+1}}[Rev(OPT_F)(n \; bidders)] \qquad \qquad \qquad \qquad (6)$$ 其中$VA$和$OPT_F$分别代表Vickrey拍卖和对应分布$F$的最优拍卖。

注意到(6)式左边的Vickrey拍卖中没有保留价值，因而是无先验信息的，这意味着它的描述与底层分布$F$无关。(6)式右边的拍卖通过保留价格的形式取决于底层分布$F$。在这个意义上，一个拍卖（Vickrey拍卖）同时与投标人的价值服从i.i.d.的正规分布情况下的所有单物品环境中的无穷多个不同的最优拍卖都具有竞争性。定理4.1中的保证表明，对于每一个拥有$n \ge 2$个投标人的环境，Vickrey拍卖的期望收入至少是（对于同样数量的投标人的）最优拍卖的$\frac{n-1}{n}$倍。细节见练习题。

对Bulow-Klemperer定理的通常解释，同时也是貌似被实践验证的，是更多的竞争比获得一个刚好合适的拍卖形式更重要。也就是说，将你的资源投入到获取更多的认真的参与者，而不是增加你对他们的偏好的知识（当然，如果可以的话两项都做）。参考习题中对Bulow-Klemperer定理的更多扩展和变形。

对定理4.1的证明: (6)式的两边很难直接比较，因此为了分析我们定义了一个虚拟拍卖A来促成比较。这个拍卖在一个有$n+1$个投标人的环境中进行，如下所示：

(1) 在前$n$个投标人$1,2,\dots, n$中模拟最优拍卖$OPT_F$。

(2) 如果物品在第1步中没有卖出去，那么就将它免费送给投标人$n+1$。

我们定义了A来获得两个对分析有用的性质。首先，它的期望收入（对$n+1$个投标人而言）正好与$OPT_F$（对$n$个投标人而言）相等。其次，A总是能将物品分配出去。

我们通过证明在i.i.d.的正规的投标人价值的情况下，Vickrey拍卖在所有的保证能将物品分配出去的拍卖中最大化期望收入。根据期望收入和期望虚拟福利的等价最优拍卖总是将物品分配给虚拟价值最高的投标人。Vickrey拍卖将物品分配给价值最高的投标人。因为投标人的分布式i.i.d.的和正规的，所有投标人共享同一个递增的虚拟价值函数$\varphi$。因此拥有最高虚拟价值的投标人总是拥有最高价值的投标人。我们得出结论，Vickrey拍卖（对于$n+1$个投标人而言）至少拥有每一个总是将物品分配出去的拍卖（包括A）那么高的期望收入，因此它的期望收入至少是$OPT_F$（对$n$个投标人而言）的期望收入。#

案例分析：雅虎关键词拍卖中的保留价格

最优拍卖理论要怎么用呢？我们接下来要讨论一个由Ostovsky和Schwarz[7]在2008年实施的实验，实验的目的是探索拍卖理论中学到的经验能否被用来增加雅虎在关键词搜索拍卖中的收入。

回顾课件2中的关键词拍卖的标准模型。怎样的拍卖能够最大化期望收入，至少在理论上？假设投标人的每点击价值是i.i.d.的，并服从一个正规分布$F$，只需要在对所有的投标人加上垄断的保留价格限制后按照出价对投标人排序（从最好的广告位到最差的）。细节见练习。

雅虎在到2008年的时候做了什么？首先，他们用了相对低的保留价格——开始是0.01美元，后来是0.05美元，到了2008年是0.10美元。可能看上去更幼稚的是，他们对所有的关键词都使用了相同的保留价格0.10美元，即使一些关键词肯定可以保证更高的保留价格（例如，比较搜索“离婚律师”和“披萨”）。如果对每个关键词单独而言，保留价格改变成理论最优了，雅虎的收入会怎么变？

[7]中描述的实验包含两个部分。首先基于过去的拍卖数据，假定对50万关键词的每一个都服从一个对数正态的价值分布。因为跟其他搜索引擎一样，雅虎使用的是基于GSP拍卖的非DSIC拍卖（见问题3），你不能指望出价是真实的。在[7]中，价值通过对过去的出价进行逆向工程获得，假设了投标人处在了与DSIC拍卖中的占优策略结果相同的均衡结果中。这一步显得有些自以为是但没有证据表明最后的结果依赖于这里的细节（例如使用的分布的具体形式）。

接下来，假设价值服从拟合的分布，对于每个关键词计算了理论上最优的保留价格。同预想的一样，对于不同的关键词最优的保留价值差别很大，但是有很多的关键词的理论最优价格在0.30美元到0.40美元之间。因此，雅虎的统一的保留价格相对理论建议，在很多关键词上都太低了。

明显的实验是尝试理论最优（一般更高一些）的保留价值，看它们会怎样。然而雅虎的高层希望更保守一些，并设了新的保留价格为旧值（0.10美元）和理论最优值的平均。事后证明，无论理论上还是经验上，这种变化带来了大部分的收入增加。进一步的增加保留价值对于收入并没有太大的影响。改变起作用了：拍卖收入上升了几个百分点（相对一个巨大的基数而言）。新的保留价格对于那些有价值但“薄”的市场格外有效，具体指的是那些竞争不是很激烈的市场（少于6个投标人）。雅虎的总裁在2008年第三季度的财报中将更好的保留价格视为搜索收入增长的最大原因。

参考文献

[1] Jason D Hartline. Mechanism design and approximation. Book draft. October, 2013.

[2] Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981.

[3] Ester Samuel-Cahn. Comparison of threshold stop rules and maximum for independent nonnegative random variables. the Annals of Probability, pages 1213-1216, 1984.

[4] Jason D Hartline and Tim Roughgarden. Simple versus optimal mechanisms. In Proceedings of the 10th ACM conference on Electronic commerce, pages 225-234. ACM, 2009.

[5] Peerapong Dhangwatnotai, Tim Roughgarden, and Qiqi Yan. Revenue maximization with a single sample. Games and Economic Behavior, 2014.

[6] Jeremy Bulow and Paul Klemperer. Auctions versus negotiations. American Economic Review, 86(1):180-194, 1996.

[7] Michael Ostrovsky and Michael Schwarz. Reserve prices in internet advertising auctions: A field experiment. In Proceedings of the 12th ACM conference on Electronic commerce, pages 59-60. ACM, 2011.