预算限制

到目前为止的讨论中都假设了每一个代理人具有拟线性效用(quasi-linear utility)，指的是它试图最大化选定的结果$\omega$带给他的价值$v_i(\omega)$和它不得不付的费用$p_i$之间的差值。因此，一个投标人的效用是所付费用的线性函数。我们没有对费用进行限制，除了它们必须是非负的和不超过$i$对给定结果设定的报价$b_i(\omega)$这些最少的条件。

在一些重要应用中，费用是受限的。我们首先关注预算限制(budget constraints)，它限制了一个代理人能够付的钱数。有时候几乎不需要加入预算限制。在一个单物品拍卖中，我们将一个代理人的价值解释为它的最大愿意支付费用，于是他的价值想必被他的预算所限制。在其他应用中，特别是当一个代理人也许最终会买很多物品时，预算是重要的。

举例而言，每一个实际中使用的关键词拍卖都要求每一个投标人提交他的每点击报价（例如，0.25美元）和他的每日预算（例如，100美元）。没物品价值和总的预算很好地建模了在有一系列物品的拍卖中许多人是如何决策的，特别是当物品相同时。

将预算纳入我们现有的效用模型的最简单方法是重新定义当预算为$B_i$时用户$i$对结果$\omega$和$p_i$的效用为： $$\begin{aligned} v_i(\omega)-p_i \;&\text{if} \; p_i \le B_i \\ -\infty \;&\text{if} \; p_i > B_i \end{aligned}$$ 当然也可以研究这个效用函数的平滑版本，也就是当有一个为预算违背量的增函数的代价存在的时候。

类似预算约束这样的费用约束加入了我们之前一直在研究的另外两类约束：激励约束，经常以单调性的形式出现；和分配约束，例如将物品分配给至多一个代理人。剩余最大化，其中费用既不出现在目标函数也不出现在约束条件中（除了要在0和投标人的报价之间），是一种特殊情况。VCG机制，和它在讲义2-4中的先驱，都在“事后”最大化剩余,这意味着像所有的私人数据事先都知道一样。最大化收入，当费用参与到目标函数时需要新的拍卖形式和新的成功标准（讲义5和6）。对于有费用约束的机制设计也是一样的，而这正是这一讲和下一讲的主题。

当有预算约束时，我们肯定不能事后最大化剩余$\sum_{i=1}^{n} v_i(\omega)$。考虑单物品拍卖的简单例子，其中每个投标人有一个已知的预算1和一个私人价值。我们声称在一个单物品拍卖中预算经常是多余的，但是我们要在这里阐述的要点是通用的。Vickrey拍卖向获胜者收取第二高的报价，而这可能会超过他的预算。既然Vickrey拍卖是唯一满足DSIC的剩余最大化拍卖（练习9），剩余最大化在不违背预算的情况下是不可能的。正如练习所示，没有服从预算的DSIC拍卖能够很好地近似剩余。我们需要新的拍卖形式来容纳预算约束。

敲定拍卖

Ausubel[1]提出的原始的敲定拍卖(clinching auction)，是当有多个相同物品时VCG机制的上升形式实现，类比于对于一个物品的英式拍卖。在[1]中，一个投标人可能想要不止一个物品，但是假设他对物品有非增的边际价值。我们在上一讲中讨论过为什么上升拍卖会比直接显示机制更好。不像上一讲中讨论过的SAA形式，[1]中的敲定拍卖不会受到需求减少的干扰。也可以参考问题集#3。

我们讨论Dobzinski等人[2]提出的敲定拍卖的变形，其中容纳了预算约束。有$m$个相同的物品，每一个投标人可能想要它们中的一些（类似关键词拍卖中的点击）。每一个投标人$i$对于他们得到的每一个物品都有一次私人价值$v_i$――因此如果他拿了$k$个商品，他们对他的价值是$k \cdot v_i$。每一个投标人都有一个预算$B_i$，我们假设其公开，这意味着卖家提前知道这个预算。我们想假设预算是私人的，因而也有可能谎报，但是私人的预算会使得问题更加困难，甚至从某些意义上是不可能的。有公共预算的问题版本就已经够难了――正如上文所示，事后的剩余最大化是不可能的――而且它会指给我们一些优雅的和有潜在用途的拍卖形式，而这当然是练习的全部目标。当预算是私人的时，这一节中讨论的敲定拍卖不满足DSIC（见练习）。

第一个切入点：利用市场出清价格

我们首先描述一个比敲定拍卖更加简单的拍卖。你可以把敲定拍卖看成是这个简单拍卖的修改了的更复杂的版本。我们给出一个直接显示描述；会很明显它有一个上升形式的实现。

第一个拍卖基于在“市场出清价格(market-clearing price)”时销售商品，即当供给等于需求时。很明显供给是$m$，即商品的数量。投标人的需求依赖于当前价格，价格越高意味着需求越少。正式地，我们定义在价格$p$上投标人$i$的需求为： $$D_i(p) = \begin{cases} \text{min}\left\{\lfloor \frac{B_i}{p} \rfloor, m \right\} \; &\text{if} \; p<v_i \\ 0 \; &\text{if} \; p>v_i \end{cases}$$ 解释一下，回顾投标人$i$对每一个得到的物品有价值$v_i$。如果价格超过$v_i$，他什么都不会想要（即，$D_i(p) = 0$），而当价格低于$v_i$时他想要尽可能多的他能负担得起的物品（即，$D_i(p) = \lfloor \frac{B_i}{p} \rfloor$）。当$v_i=p$时，投标人不关心他得到了多少商品，只要他的预算被满足，于是在拍卖和它的分析中我们可以根据需要在$\{0,1,2,\dots,\lfloor \frac{B_i}{p} \rfloor \}$中选一个方便的整数作为$D_i(v_i)$。

随着价格$p$上升，需求$D_i(p)$下降，从$D_i(0) = m$到$D_i(\infty) = 0$。一个需求下降可以有两种不同形式：从一个任意的正整数到0（当$p$等于$v_i$）或每步降低一个单位值（当$\lfloor \frac{B_i}{p} \rfloor$变得越来越小）。

令$p^*$表示满足$\sum_i{D_i(p^*)} = m$的最小价格。或者，更一般地，满足$\text{lim}_{p \uparrow p^*} \sum_i D_i(p) \ge m \ge \text{lim}_{p \downarrow p^*} \sum_i D_i(p)$的最小值。然后，拍卖将$D_i(p^*)$个商品给投标人$i$，每一个的价格为$p^*$（对于$v_i = p^*$的投标人$i$定义$D_i(p^*)$使得所有$m$个商品全部分配掉）。

好消息是，根据需求$D_i(p)$的定义，这个拍卖满足了投标人的预算。坏消息是它不满足DSIC；与上一讲中讨论过的同时上升拍卖形式类似，它很容易遇到需求减少的问题。

例子2.1（市场出清价格不满足DSIC） 假设有两个商品和两个投标人满足$B_1 = +\infty, v_1 = 6$和$B_2=v_2=5$。首先假设两个投标人都真实报价都真实报价。直到价格到达5前，总的需求$\sum_i D_i(p)$至少是3，而$D_1(5)=2,D_2(5)=0$。拍卖会以5的价格把两个商品都分配给投标人1，获得的效用为2。然而如果投标人1谎报3，得到的结果更好。原因是在价格为$\frac{5}{2}$时投标人2的需求降为1（他再也不能同时负担两件商品），并且拍卖会在价格为3时终止，终止时刻上$D_1(3)$被定义为1。投标人只会得到一个商品，但是价格只是3，因此效用为3，比真实报价得到的效用更高。

自从Myerson引理（课件3）之后我们还没有研究过任何非DSIC拍卖，而Myerson引理从某种意义上给出了我们现在看到的拍卖这样的单变量场景中，DSIC拍卖设计的完整解。如果你愿意检查的话，市场出清价格拍卖中的分配规则是单调的，因此例子2.1告诉我们费用规则是错的。我们可以在这个分配规则上利用Myerson引理来推导合适的费用以恢复DSIC，但是我们也想要更加复杂一些的分配规则。

有预算投标人的敲定拍卖

我们会再次给出一个直接显示描述，但是记住这个拍卖有一个自然的上升实现，而这只是敲定拍卖的出发点。

与其在一轮中将物品全部售出，我们会在不同的价格上将物品逐个售出。除了现在的价格$p$，拍卖也会记下现在的供给$s$（初始值为$m$）以及每个投标人$i$剩余的预算$\hat{B}_i$（初始值为$B_i$）。在价格$p$上投标人$i$的需求$\hat{D}_i(p)$是剩余预算和供给的函数，当$p<v_i$时为$\text{min}\{\lfloor \frac{\hat{B}_i}{p} \rfloor, s \}$,而当$p > v_i$时为0。

有预算投标人的敲定拍卖如下：

• 初始化$p=0,s=m$。
• 当$s>0$：
  • 增加$p$直到有一个投标人$i$满足$\underbrace{s - \sum_{j \ne i} \hat{D}_j(p)}_{:=k} >0$。
  • 将$k$的商品以价格$p$给投标人$i$（这些商品是“敲定”的）。
  • 在$s$上减去$k$。
  • 在$\hat{B}_i$上减去$p \cdot k$。

观察到不同的商品是以不同的价格售出的，而售出价在拍卖的过程中上升。观察到预算也是满足的――投标人$i$敲定的商品数量$k$最多为他当前的需求$\hat{D}_i(p)$。如果不是这样的话，那么$\sum_j \hat{D}_j(p) < s$。但是拍卖保持了如下的不变性：总需求至少是现在的供给。

例子2.2 让我们回到例子2.1中的场景――两个商品和两个投标人，其中$B_1=+\infty, v_1=6, B_2=v_2=5$。假设两个投标人都真实报价。在例子2.1中，两个物品都以5的价格给了投标人1。在这里，由于第二个投标人的需求$D_2(p)$一旦$p=\frac{5}{2}$就会降到1，投标人会以$\frac{5}{2}$的价格敲定一个商品。第二个商品会以5的价格卖给投标人2，这跟之前一样。因此在敲定拍卖中，当投标人1真实报价时效用为$\frac{7}{2}$。正如我们会看到的那样，没有假的报价可以做得更好。

定理2.1. 有公开预算投标人的敲定拍卖满足DSIC。

证明：我们可以验证分配规则是单调的和费用满足Myerson费用公式，但是更容易直接验证DSIC条件。因此固定一个投标人$i$和其他人的报价$\mathbf{b}_{-i}$。因为投标人$i$的预算是公开的，他不能影响需求函数$\hat{D}_i(p)$中的$\lfloor \hat{B}_i / p \rfloor$这一项。他只能改变他从拍卖中出局的时间（意味着永远为$\hat{D}_i(p) = 0$），而这恰恰是当价格$p$到达他的报价$b_i$的时候。注意到当$p < v_i$时投标人$i$敲定的每一个商品都会对他的效用有正的贡献，而当$p > v_i$时敲定的每一个商品有负的贡献。

首先比较当报价$b_i < v_i$时获得的效用和真实报价时获得的效用。想象一下同时进行两次敲定拍卖，一次中$i$报价$b_i$，而另一次中$i$报价$v_i$。通过对迭代次数的推导，当价格从0上升到$b_i$时，两种场景中的敲定拍卖的执行会变得完全一样。因此，通过报价$b_i$，在价格区间$[b_i, v_i]$上，投标人只可能失去它本可能（以非负的效用）敲定的商品。

类似地，如果$i$报价$b_i > v_i$，所有的改变是在价格区间$[v_i,b_i]$上，投标人可能会以非正的效用获取一些额外的商品。因此，没有虚假的报价使得$i$获得比真实报价更高的效用。#

如果反过来预算是私人的，并且敲定拍卖是以上报的预算进行，那么它不再满足DSIC（见练习）。

单独来看，定理2.3并不引人注目。还有其他简单的满足预算的DSIC拍卖，例如随机地将商品送给投标人。我们想额外地说明敲定拍卖计算出了一个“好”的分配。例如（在预算约束下）接近最大可能的剩余。原始的敲定拍卖[1]，在没有预算的情况下，实现了VCG的结果，因而是剩余最大化的。正如我们所看到的，没有满足预算的机制能够拥有接近VCG机制（不需要满足预算）的剩余。

研究者们至少探索了三种途径试图从剩余的角度来说明敲定拍卖的正当性。没有一个是完全令人满意的。尽管有强烈的信念认为敲定拍卖是“正确的解决方案”，研究者仍然在努力建立一种模型使得这种直觉更加准确。

最主要的挑战是找到一个好的基准与敲定拍卖的表现进行比较。Dobzinski等人[2]研究了帕雷托最优，而不是一个目标函数。一个分配是帕雷托最优(Pareto optimal)的，当且仅当没有办法重新分配商品和费用使得一些代理人（投标人或者卖家）的结果变得更好的同时不让另一些人受损害，其中卖家的效用是它的收入。好消息是帕雷托最优强烈地支持了敲定拍卖――它是唯一一个始终产生帕雷托最优分配的确定性的DSIC拍卖。坏消息是为了得到一个好的拍卖，帕雷托最优性并不总是需要的或必需的。举例而言，下面要讨论的贝叶斯最优拍卖并不需要满足帕雷托最优。

第二种途径是加上投标人价值的分布，并且求解在给定预算限制下最大化期望剩余的DSIC机制（可以与课件5对比）。在这种平均情况途径中，对于“最优”的拍卖有清晰的定义――具有最高期望剩余的那些拍卖。在这样的场景下证明“简单的接近最优”和“无先验知识的”近似也很有意思，可以联系到课件6中的结果。这些方向上的进展很慢但一直在推进[3]。公共预算现在比一般预算要研究得更好，并且在这种特殊情况下敲定拍卖很可能接近最优[4]。

第三种途径是修改剩余目标函数以考虑进去预算。最常见的提议是将$\sum_i v_i x_i$换为$\sum_i \text{min}\{B_i, v_i x_i\}$。好消息是在这个目标函数下，敲定拍卖很可能接近最优。坏消息是在某些场景下这个修改后的目标没有意义。见练习和[5]的3.10小节。

没有金钱的机制设计

在一系列重要的应用中存在重大的动机困难而金钱又是不可行或不合法的。这等价于所有的代理人预算为零。没有金钱的机制设计跟投票，器官捐赠，学校选择和劳力市场的设计和理解有关。设计者的能力被没有金钱所限制――甚至比有预算约束还要紧。举例而言，这时肯定没有VCG拍卖。除了这个和在一般场景中的强不可能结果，一些机制设计的巨大突破是由没有金钱的应用激发的。

Shapley和Scarf[6]定义了如下的房屋分配问题(house allocation problem)。有$n$个代理人，每个人一开始拥有一间房子。每个代理人对于$n$个房屋都有一个总的排序，并且并不需要喜欢自己的房屋超过别人的。问题是：如何合理地重新分配房屋使得代理人变得更好？考虑如下的最优交易循环算法(Top Trading Cycle Algorithm, TTCA)，在文献[6]中归功于Gale：

• 当有代理人剩下时：
  • 每一个剩余的代理人指向他最喜欢的剩余房屋。这就在剩余的代理人上产生了一个有向图$G$，其中每个结点的出度为1（图1）。
  • 图$G$至少有一个有向环。保持跟踪指出的边，最终，一个结点会重复，从而产生一个有向环。自环也可以被算作有向环。
  • 根据有向环进行重新分配，有向环$C$上的每个代理人都将房屋给指向他的代理人，也就是$C$上的前继结点。
  • 删掉在上一部中重新分配的代理人和房屋。

图1：有两个有向环的最优交易循环算法的一次迭代。

观察到TTCA终止时每个代理人刚好拥有一间房屋。作为对它的合理性的检查，观察到这个算法只会使每个代理人变得更好。想要看出来为什么，注意到算法保持了这样的不变性质，剩下的代理人保留了他们原来的房屋。因此，在每一轮中，每一个代理人指向他自己的房屋或他更喜欢的房屋。最终，当一个代理人被删除后，他得到自己指向的那个房屋。

当代理人的偏好是私人的，我们可以在一个直接显示机制中根据代理人上报的偏好实施TTCA。代理人没有动机谎报他们的偏好。

定理3.1. TTCA推出了一个DSIC机制。

证明：令$N_j$表示当所有代理人真实上报时TTCA中第$j$轮中分配了的代理人。$N_1$中的每一个代理人得到了他的第一选择，因此没有动机谎报。$N_2$中的某个代理人$i$没有在第一轮中被$N_1$中的任何代理人指向――否则，$i$会属于$N_1$而不是$N_2$。因此，$i$没有办法通过谎报获得$N_1$中代理人原来拥有的房屋。既然$i$得到了$N_1$中代理人拥有的房屋之外的第一选择，他没有动机谎报。一般而言，$N_j$中的代理人$i$没有在TTCA的前$j-1$轮中被$N_1 \cup \cdots \cup N_{j-1}$中的任何代理人指向过。因此，无论他如何上报，$i$不会得到$N_1 \cup \cdots \cup N_{j-1}$中的代理人拥有的房屋。既然TTCA给了$i$这个集合之外最喜欢的房屋，他没有动机谎报。#

与敲定拍卖一样，定理3.1本身不令人惊讶――每个代理人保留他原来房屋的机制也满足DSIC。为了说明TTCA在某种意义上是最优的，我们引入核心分配(core allocation)的概念――一种使得没有一个代理人的联盟可以通过内部重分配使得成员更好的分配。

定理3.2.对每个房屋分配问题，TTCA计算出的分配结果是唯一的核心分配。

证明：为了证明计算出的分配结果是一个核心分配，考虑一个任意的代理人子集$S$。如定理3.1证明中那样定义$N_j$。令$\ell$表示$N_\ell \cap S \ne \emptyset$的第一轮，其中代理人$i \in S$在TTCA的第$\ell$轮获得了他的房屋。TTCA给了代理人$i$除了$N_1, \dots, N_{\ell - 1}$拥有的房屋之外他最喜欢的房屋。既然$S$中没有代理人属于$N_1, \dots, N_{\ell - 1}$，没有$S$中代理人之间的重新分配能够使得$i$严格变好。

我们现在证明唯一性。在TTCA分配中，$N_1$中的所有代理人得到了他们的第一选择。这一点必须在任何核心分配中也正确――在一个没有这项性质的分配中，$N_1$中没有得到他们的第一选择的代理人会形成一个联盟，而他们内部的重新分配会使每个人严格变好。类似地，在TTCA分配中，$N_2$中的所有代理人得到了除$N_1$之外的第一选择。考虑到每一个核心分配都满足TTCA对$N_1$中的代理人的分配结果，这样的分配结果也必须对$N_2$中的代理人成立――否则，$N_2$中没有得到除了$N_1$之外第一选择的代理人可以通过内部重分配全部得到提高。继续推导，我们发现TTCA分配是唯一的核心分配。#

参考文献

[1] Lawrence M Ausubel. An ecient ascending-bid auction for multiple objects. American Economic Review, pages 1452-1475, 2004.

[2] Shahar Dobzinski, Ron Lavi, and Noam Nisan. Multi-unit auctions with budget limits. Games and Economic Behavior, 74(2):486-503, 2012.

[3] Mallesh M Pai and Rakesh Vohra. Optimal auctions with financially constrained buyers. Journal of Economic Theory, 150:383-425, 2014.

[4] Nikhil R Devanur, Bach Q Ha, and Jason D Hartline. Prior-free auctions for budgeted agents. In Proceedings of the fourteenth ACM conference on Electronic commerce, pages 287-304. ACM, 2013.

[5] Noam Nisan, Jason Bayer, Deepak Chandra, Tal Franji, Robert Gardner, Yossi Matias, Neil Rhodes, Misha Seltzer, Danny Tom, Hal Varian, et al. Google's auction for tv ads. In Automata, Languages and Programming, pages 309-327. Springer, 2009.

[6] Lloyd Shapley and Herbert Scarf. On cores and indivisibility. Journal of mathematical economics, 1(1):23-37, 1974.

[7] Shahar Dobzinski and Renato Paes Leme. Effciency guarantees in auctions with budgets. In Automata, Languages, and Programming, pages 392-404. Springer, 2014.