到目前为止的故事

上一讲中，我们介绍了Vickrey拍卖并证明了它满足三个理想的保证：

(1) 【强激励保证】DSIC。也就是说，真实报价应该是占优策略（并且永远不会导致负的效用）。

不要忘记我们追求DSIC保证的两个原因。首先，这样的拍卖对于投标人而言容易进行——只需要遵循明显的占优策略。其次，只要假设投标人有占优策略的时候就会遵循占优策略，我们就可以满怀信心地预测拍卖的结果。

(2) 【强性能保证】社会剩余最大。也就是说，假设真实报价（在(1)中已经解释），商品的分配方案应该要最大化$\sum_{i=1}^{n}{v_i x_i}$，其中$x_i$是分配给投标人$i$的商品量。

(3) 【计算高效】拍卖可以在多项式（其实是线性）时间内实施。

想要将这些保证从单物品拍卖拓展到更复杂的问题，例如上一讲中介绍的竞价搜索拍卖，我们提出了一种两步的设计途径。

步骤1：没有理由地假设投标人真实报价。那么我们应该如何分配广告位给投标人，使得上述性质(2)和(3)成立？

步骤2：根据步骤1的结果，我们应该如何设计出售价格使得上述性质(1)成立？

举例来说，在竞价搜索中，步骤1可以通过一个简单的贪心算法（分配第$j$好的广告位给出价第$j$高的投标人）。但是步骤2呢？

这一讲介绍和证明Myerson引理，它是实施步骤2的一个强大而一般的工具。作为一个特殊例子，它适用于竞价搜索拍卖。我们以后也会看到其他应用。

单变量环境

单变量环境(single-parameter environment)适合用来陈述Myerson引理。这样的环境中有一定数量$n$个投标人。每个投标人$i$都有一个私人价值$v_i$，代表了他得到的单位量的商品带给他的价值。最后，这里有一个可行集(feasible set)$X$。$X$的每个元素是一个$n$维向量$(x_1, x_2, \dots, x_n)$，其中$x_i$代表了分配给投标人$i$的商品量。举例而言：

• 在一个单物品拍卖中，$x$是最多只有一个分量为1的0-1向量的集合（即，$\sum_{i=1}^{n} x_i \le 1$）。
• 在有$k$个相同的商品以及每个顾客最多只能得到一个商品的约束下，可行集是满足$\sum_{i=1}^{n} x_i \le k$的0-1向量。
• 在竞价搜索中，$x$是对应于投标人和广告位的分配方案的$n$维向量的集合，其中每个广告位最多分配给一个投标人，每个投标人最多分配到一个广告位。如果投标人$i$分到了广告位$j$，那么分量$x_i$等于它的广告位的点击率$\alpha_j$。

分配和支付规则

回顾一个密封投标拍卖需要做出两个选择：谁赢和谁付出什么。这两个决定分别通过分配规则(allocation rule)和\textbf支付规则(payment rule)正式定义。也就是说一个密封投标拍卖包含三步：

(1) 收集出价$\mathbf{b} = (b_1, \dots, b_n)$。

(2) 【分配规则】选择一个可行的分配$\mathbf{x}(\mathbf{b}) \in X \subseteq \mathcal{R}^n$作为出价的函数。

(3) 【支付规则】选择费用$p(\mathbf{b}) \in \mathcal{R}^n$作为出价的函数。

我们继续使用一个拟线性的效用模型，因此，在一个分配和支付规则分别为$\mathbf{x}$和$\mathbf{p}$的拍卖中，投标人$i$的效用为 $$u_i(\mathbf{b}) = v_i \cdot x_i(\mathbf{b}) - p_i(\mathbf(b))$$ 为出价资料（即出价向量）$\mathbf{b}$的函数。

在这一讲中，我们会将重点放在满足如下条件的支付规则： $$p_i(\mathbf{b}) \in [0, b_i \cdot x_i(\mathbf{b})] \qquad \qquad \qquad \qquad (1)$$ 对于每个$i$和$b$都成立。$p_i(\mathbf{b}) \ge 0$的约束等价于禁止卖家付钱给投标人。$p_i(\mathbf{b}) \le b_i \cdot x_i(\mathbf{b})$的约束保证一个真实报价的投标人得到非负的效用（你能看出来为什么吗？）。

在一些应用中放宽上述关于费用的一个或两个约束是合理的，但我们不会在课件中涉及到。

Myerson引理的陈述

我们现在给出两个重要的定义。它们都阐述了分配规则的某个性质。

定义4.1 (可实现的分配规则). 单变量环境中分配规则是可实现的(implementable)，如果存在支付规则$\mathbf{p}$使得密封竞标拍卖$(\mathbf{x},\mathbf{p})$满足DSIC。

也就是说，可实现的分配规则可以扩展为DSIC机制。等价地，将DSIC机制映射到它们的分配规则也就组成了可实现规则的集合。如果我们的目标是设计一个DSIC机制，我们必须限制在可实现的分配规则中——它们组成了我们的“设计空间”。用这个术语，我们可以重述上一讲最后的悬念：竞价搜索中将第$j$好的广告位分配给第$j$高的投标人的剩余最大化的分配方案是可实现的吗？

举例来说，考虑一个单物品拍卖。将商品奖励给出价最高者的分配规则可实现吗？当然——我们已经构建了一个支付规则，也就是次价规则，使得它满足DSIC。那么将商品分配给出价第二高的投标者的分配方案呢？这里，结果是不明显的：我们还没有看到一种支付规则能将它扩展到DSIC机制，但又难以说明没有任何一种支付规则能行。

定义4.2(单调的分配规则). 单变量环境中分配规则$\mathbf{x}$是单调的(monotone)，如果对于每个投标人$i$和其他人的出价$\mathbf{b}_{-i}$，$i$得到的分配结果$x_i(z,\mathbf{b}_{-i})$关于他的出价$z$非减。

也就是说，在一个单调的分配规则中，出价越高只会使你得到更多的商品。

举例来说，在单物品拍卖中将商品奖励给出价最高者的分配规则是单调的：如果你是赢家并且你提高你的报价（保持其他人的报价不变），你仍然会赢。作为对比，将商品给报价第二高的投标人不是一个单调的分配规则：如果你是赢家，把你的报价提到足够高，你反而会输。

竞价搜索中将第$j$好的广告位分配给出价第$j$高的投标人的剩余最大化的分配规则是单调的。原因是当你提高报价，只会使你在排序后的出价中排位增高，从而使你获得一个位置更好的广告位，而这只会增加你的广告位的点击率。

我们说Myerson引理由三个部分组成，每一部分在概念上都十分有趣，而且在以后的应用中也非常有用。

定理4.1 (Myerson引理[1]). 固定一个单变量环境。

(a) 一个分配规则$\mathbf{x}$是可实现的当且仅当它是单调的。

(b) 如果$\mathbf{x}$是单调的，那么存在一个唯一的支付规则使得密封投标机制$(\mathbf{x},\mathbf{p})$满足DSIC（假设经过了正规化，$b_i = 0$意味着$p_i(\mathbf{b})=0$）。

(c) (b)中的分配规则可以通过一个明确的公式给出（见下面的公式(6)）。

Myerson引理是我们建立大部分机制设计理论的基础。(a)表明定义4.1和4.2实际上定义了相同的分配规则的类。这种等价是非常强大的：定义4.1描述了我们的设计目标，但很难实施和验证，然而定义4.2更加“可操作”，通常并不难检查一个分配规则是否单调。(b)表明当一个分配规则是可实现的话，在如何设计支付规则以获得DSIC性质这个问题上不会产生分歧——因为只有一种方法可以实现。（假设零报价保证零支付；注意到这来自于我们的长期假设公式(1)。）进一步讲，这种支付规则有一种相对简单和明确的公式表示（(c)），我们会在下面的竞价搜索拍卖以及后面课程中的利润最大化的拍卖设计中使用这个性质。

Myerson引理的证明（定理4.3）

考虑一个分配规则$\mathbf{x}$，它可能单调，也可能不单调。假设有一种支付规则$\mathbf{p}$使得$(\mathbf{x},\mathbf{p})$是一个DSIC机制——$\mathbf{p}$会长成什么样子？这个证明的思路就是通过明确地调用严格的DSIC约束来将$\mathbf{p}$的可能性削减到唯一一个可能。我们将会一举建立定理的所有三个部分。

回顾DSIC的条件：对每一个投标人$i$，每一种可能的私人价值$b_i$，其他人的每一种出价集$\mathbf{b}_{-i}$，为了最大化$i$的效用都必须是真实报价。现在，任选$i$和$\mathbf{b}_{-i}$固定住。为了简便，用$x(z)$和$p(z)$分别代表当$i$的出价为$z$时的分配结果$x_i(z,\mathbf{b}_{-i})$和费用$p_i(z, \mathbf{b}_{-i})$。图1给出了$x$可能的两种形式。

图1：分配曲线$x(\cdot)$的两个例子。

我们通过一种简单但巧妙的交换技巧来调用DSIC的限制。假设$(\mathbf{x}, \mathbf{p})$满足DSIC，并考虑任何满足$0 \le y < z$的$y$。因为投标人$i$可能有私人价值$z$并且他愿意的话可以提交虚假的报价$y$，DSIC要求 $$\underbrace{z \cdot x(z) - p(z)}_{\text{utility of bidding} \; z} \ge \underbrace{z \cdot x(y) - p(y)}_{\text{utility of bidding} \; y} \qquad \qquad \qquad \qquad (2)$$

类似地，因为投标人也可能有私人价值$y$，并且可以提交虚假的报价$z$，$(\mathbf{x}, \mathbf{p})$必须满足 $$\underbrace{y \cdot x(y) - p(y)}_{\text{utility of bidding} \; y} \ge \underbrace{y \cdot x(z) - p(z)}_{\text{utility of bidding} \; z} \qquad \qquad \qquad \qquad (3)$$ Myerson引理实际上试图在给定$\mathbf{x}$后解出支付规则$\mathbf{p}$。整理不等式(2)和(3)，得到所谓的“费用差三明治不等式”，给出了$p(y) - p(z)$的上下界： $$z \cdot [x(y) - x(z)] \le p(y) - p(z) \le y \cdot [x(y) - x(z)] \qquad \qquad \qquad \qquad (4)$$ 费用差三明治已经暗示了Myerson引理的一个主要部分——你看出来为什么了吗？

因此，我们可以假设在接下来的证明中$\mathbf{x}$是单调的。在接下来的表述中我们可能会有点不严格，但会涵盖证明的主要要点。

在公式(4)中，固定$z$，并使$y$趋近于$z$。我们主要考虑图1中$x$是分段常数的情况。在这种情况下，除了几个有限数量的“跳跃点”，$x$是平的。当公式(4)中，$y$趋近于$z$时，如果$x$在$z$处没有跳跃，则不等式的左右两边都变为0。如果在$z$处的跳跃量为$h$，那么不等式的左右两边都倾向于$z \cdot h$。这意味着对每个$z$而言，有对$p$的如下限制： $$\text{jump in} \; p \; \text{at} \; z = z \cdot \text{jump in} \; x \; \text{at} \; z \qquad \qquad \qquad \qquad (5)$$ 因此，假设正规化$p(0) = 0$，我们已经推导出了如下的支付公式(payment formula)，对每个投标人$i$，其他人的出价$\mathbf{b}_{-i}$和$i$的报价$b_i$，有 $$p_i(b_i, \mathbf{b}_{-i}) = \sum_{j = 1}^{l} z_j \cdot \text{jump in} \; x_i(\cdot, \mathbf{b}_{-i}) \; \text{at} \; z_j \qquad \qquad \qquad \qquad (6)$$ 其中$z_1, \dots, z_l$是分配函数$x_i(\cdot, \mathbf{b}_{-i})$在$[0, b_i]$区间上的断点。

另一种情况是当$x$是单调函数时，并不一定需要分段常数。举例来说，假设$x$是可微的。在费用三明治不等式(4)上除以$y-z$，并且取极限$y \downarrow z$会产生如下限制 $$p^\prime (z) = z \cdot x^\prime (z)$$ 并且假设$p(0) = 0$，有支付公式 $$p_i(b_i, \mathbf{b}_{-i}) = \int_{0}^{b_i} z \cdot \frac{d}{dz} x_i(z, \mathbf{b}_{-i})dz \qquad \qquad \qquad \qquad (7)$$ 对于每一个投标人$i$，出价$b_i$和其他人的出价$\mathbf{b}_{-i}$。

我们重申(6)中的支付公式是唯一的有机会将给定的分段常数的分配规则$\mathbf{x}$扩展为一个DSIC机制的支付规则。因此，对于每一个支付规则$\mathbf{x}$，只有最多一种支付规则$\mathbf{p}$使得$(\mathbf{x},\mathbf{p})$满足DSIC（定理4.3的部分(b)）。但是证明并不完整——我们还必须检查当$\mathbf{x}$单调时这个支付规则可用！实际上，我们已经知道当$\mathbf{x}$不单调时，这个支付规则也会失败。

我们通过画图来证明，当$\mathbf{x}$是单调和分段常数，$\mathbf{p}$由公式(6)定义时，$(\mathbf{x}, \mathbf{p})$是一种DSIC机制。同样的论证也适用于更一般的不是分段常数的单调的分配规则以及由公式(7)定义的费用。这样就可以完成Myerson引理的所有三个部分的证明。

图2： 通过画图来证明，当$\mathbf{x}$是单调和分段常数，$\mathbf{p}$由公式(6)定义时，$(\mathbf{x}, \mathbf{p})$是一种DSIC机制。三列分别考虑真实报价，抬高报价和压低报价的情况。三行分别代表剩余$v \cdot x(b)$，费用$p(b)$和效用$v \cdot x(b) - p(b)$。在(h)中，实的区域代表正的效用而划线区域代表负的效用。

图2(a)-(i)分别描述了当一个投标人真实报价、抬高报价和压低报价时获得的效用。在三种情况下，分配曲线$x(z)$和私人价值$v$都是相同的。回顾一下当投标人报价为$b$时的效用为$v \cdot x(b) - p(b)$。我们将第一项$v \cdot x(b)$描述为一个宽为$v$，高为$x(b)$的阴影下的长方形（图2(a)-(c)）。用公式(6)，我们可以发现费用$p(b)$可以用$[0,b]$区间上分配曲线左边的阴影区域表示（图2(d)-(f)）。投标人的效用是这两项之间的差（图2(g)-(i)）。当投标人真实报价时，他的效用刚好是在$[0,v]$范围上分配曲线下方的区域。在这种情况下，消费者投标人贡献的社会剩余($v \cdot x(v)$)自然地分成了他的效用（或“消费者剩余”），即曲线下面的区域，和卖家收入，曲线上方的区域（都在$[o,v]$区间上）。当投标人抬高报价，他的效用是相同的区域，但要减去$[v,b]$区间上分配曲线上方的区域（图2(h)）。当投标人压低报价，他的效用是$[0,v]$区间上分配曲线下方区域的一个子集（图2(i)）。既然在第一种情况下投标人的效用最大，我们也就完成了证明。

应用支付公式：竞价搜索的解决方案

Myerson支付公式(6)很容易理解并可以在许多应用中使用。作为开始，考虑一个单物品拍卖，其中分配规则将商品分配给出价最高者。固定$i$和$\mathbf{b}_{-i}$，直到$B=\max_{j \ne i} b_j$，$x_i(\cdot, \mathbf{b}_{-i})$都是0，而之后，$x_i(\cdot, \mathbf{b}_{-i})$都是1。公式(6)要么是0（如果$b_i < B$），或当$b_i > B$，仅有一个断点（在$B$处跳跃量为1），从而费用为$p_i(b_i, \mathbf{b}_{-i}) = B$。因此，作为一个特例，Myerson引理推出了Vickrey拍卖。

现在让我们回到竞价搜索拍卖。回顾上一讲中我们有$k$个广告位，其点击率满足$\alpha_1 \ge \alpha_2 \ge \cdots \ge \alpha_k$。记\mathbf{x}(\mathbf{b})为将第$j$好的广告位分配给出价第$j$高的广告主的分配规则，其中$j=1,2,\dots,k$。我们之前已经注意到这个规则是剩余最大化（假设真实报价）和单调的。应用Myerson引理，我们可以推导出唯一的支付规则$\mathbf{p}$使得$(\mathbf{x},\mathbf{p})$满足DSIC。为了描述它，考虑一个出价向量$\mathbf{b}$；我们可以对投标人重新排列使得$b_1 \ge b_2 \ge \cdots \ge b_n$。为了直观，我们关注第一个投标人并想象将他的投标从0增加到$b_i$，并保持其他人出价固定。随着$z$从0到$b_1$，分配结果从0变到$\alpha_1$，当$z$变成$(z,\mathbf{b}_{-i})$中的第$j$高的出价，即$b_{j+1}$时会有一个$\alpha_j - \alpha_{j+1}$的跳跃。因此，一般而言，Myerson费用公式具体为 $$p_i(\mathbf{b}) = \sum_{j = i}^{k} b_{j+1} (\alpha_j - \alpha_{j+1}) \qquad \qquad \qquad \qquad (8)$$ 对于报价第$j$高的投标人（其中$\alpha_{k+1} = 0$）。

回顾我们的假设，投标人并不在乎广告带来的印象（即他们的链接被展示了），除非它带来了一次点击。这一点启发了我们按点击次数收费，而不是展示次数。对于投标人的每点击费用只需要在公式(8)中乘以$\frac{1}{\alpha_i}$： $$p_i(\mathbf{b}) = \sum_{j = i}^{k} b_{j+1} \frac{\alpha_j - \alpha_{j+1}}{\alpha_i} \qquad \qquad \qquad \qquad (9)$$ 观察到公式(9)有一个很好的解释是，当它的链接被点击了，一个广告主会支付一个合适的其他更低报价的凸组合。

由于历史原因，现在实际生活中使用的竞价搜索拍卖是基于“广义次价(Generalized Second Price, GSP)”拍卖[2, 3]，它是上述DSIC拍卖的一个更简单（也许并不正确）的版本。GSP中的每点击费用仅仅是下一个更低的报价。由于Myerson引理表明(9)中的支付规则才是唯一一个能保证DSIC性质的规则，我们能够立刻下结论GSP拍卖不满足DSIC。然而它仍然拥有一系列好的性质，并且在精确的意义上“部分等价”于DSIC拍卖。作业会要求你去探索这种等价的细节。

参考文献

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

[2] Benjamin EDELMAN, Michael OSTROVSKY, and Michael SCHWARZ. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. The American economic Review, 97(1):242-259, 2007.

[3] Hal R Varian. Position auctions. International Journal of Industrial Organization, 25(6):1163-1178, 2007.