Twenty Lectures on Algorithmic Game Theory 算法博弈论二十讲 Lecture 5 Revenue-Maximizing Auctions （上）

Twenty Lectures on Algorithmic Game Theory 算法博弈论二十讲 Lecture 5 Revenue-Maximizing Auctions （上）

Lecture 5 Revenue-Maximizing Auctions

第 2 至第 4 讲聚焦于设计能够最大化社会福利的机制，无论是精确还是近似。这类机制的收益产生仅仅是副作用，是激励代理人如实报告私人信息的必要之恶。本讲研究旨在最大化收益的机制，并对基于代理人估值先验分布的期望收益最大化机制进行特征描述。

第 5.1 节解释了为何收益最大化的推理比福利最大化更为困难，并介绍了贝叶斯环境。第 5.2 节是本讲的核心，它将期望收益最大化机制描述为“虚拟福利最大化者”。第 5.3 节描述了这一理论如何被用于提升 Yahoo 的赞助搜索收益。第 5.4 节证明了第 5.2 节所需的技术引理。

5.1 The Challenge of Revenue Maximization

5.1.1 Spoiled by Social Welfare Maximization

有几个理由解释为什么在机制设计的研究中，首先以最大化社会福利为目标。第一个理由是这一目标与许多现实场景相关。例如，在政府拍卖（例如，出售无线频谱；见第 8 讲）中，主要目标是福利最大化。虽然收益也是这些拍卖中的一个考虑因素，但通常不是首要目标。此外，在竞争市场中，一般的规则是卖方应该关注福利最大化，否则竞争对手会（从而抢走他们的客户）。

第二个理由是教学上的：社会福利具有特殊性。在每一个单参数环境中，都存在一个 DSIC 机制，该机制在每个私人估值配置下，假设真实出价，计算出福利最大化的结果（参见练习 4.1）。这样的机制在优化社会福利方面表现得像是所有私人信息事先已知一样——DSIC 约束条件得到了免费满足。

这种被称为“事后”保证的惊人强性能保障，一般无法在其他目标函数上实现。

5.1.2 One Bidder and One Item

以下这个简单的例子能够很好地阐明问题。假设有一个物品，且只有一个竞标者，拥有一个私人估值 v。在只有一个竞标者的情况下，直接揭示的 DSIC 拍卖空间很小：它们恰好是固定价格拍卖，即“要么接受要么放弃”的报价。设定一个固定价格 $ ，拍卖的收益要么是 r （如果 ，拍卖的收益要么是r（如果 ，拍卖的收益要么是r（如果v \geq r ），要么是 0 （如果 ），要么是0（如果 ），要么是0（如果v < r ）。 ）。 ）。r \geq 0$

在这种情况下，最大化社会福利是显而易见的：只需将 r 设为 0，这样拍卖总能将物品免费授予竞标者。这一最优的固定价格与 v 无关。

假设我们想要最大化收益。我们应该如何设置 r 呢？如果我们能心灵感应地知道 v，我们会将 r 设为 v。但当 v 对竞标者而言是私密的，我们该怎么做呢？关于这个问题，推理并不那么明确。

根本问题在于，收益最大化的拍卖会随着私人估值的变化而变化。对于单个物品和竞标者，当 v 为 20 或稍大时，设定一个 20 的固定价格效果会很好；而当 v 小于 20 时，效果则会很糟糕（而较低的固定价格则会表现得更好）。相比之下，福利最大化问题中存在一个与输入无关的最优 DSIC 机制，这确实是特别之处。

5.1.3 Bayesian Analysis

要比较两个不同拍卖的收益，我们需要一个模型来比较不同输入间的权衡。经典的方法是使用平均情况或贝叶斯分析。我们考虑一个包含以下要素的模型：

一个单参数环境（见第 3.1 节）。我们假设存在一个常数 M，使得对于每个参与者 i 和每个可行解 ( x 1 , … , x n ) ∈ X (x_1, \dots, x_n) \in X (x1​,…,xn​)∈X，都有 x i ≤ M x_i \leq M xi​≤M。

独立分布 F 1 , … , F n F_1, \dots, F_n F1​,…,Fn​具有正且连续的密度函数 f 1 , … , f n f_1, \dots, f_n f1​,…,fn​。我们假设参与者 i 的私人估值 v i v_i vi​是从分布 F i F_i Fi​中抽取的。我们还假设每个分布 F i F_i Fi​的支持集属于 [ 0 , v max ] [0, v_{\text{max}}] [0,vmax​]，其中 v max < ∞ v_{\text{max}} < \infty vmax​<∞。

一个关键假设是机制设计者知道分布 F 1 , … , F n F_1, \dots, F_n F1​,…,Fn​。如同往常一样，代理人的估值实现 v 1 , … , v n v_1, \dots, v_n v1​,…,vn​是私密的。由于我们关注的是 DSIC 拍卖，即代理人具有占优策略的拍卖，因此代理人不需要知道分布 F 1 , … , F n F_1, \dots, F_n F1​,…,Fn​。

在贝叶斯环境中，定义“最优”机制显而易见——它是在所有 DSIC 机制中，具有最高期望收益的机制（假设真实出价）。期望值是相对于给定的估值分布 F 1 × F 2 × ⋯ × F n F_1 \times F_2 \times \cdots \times F_n F1​×F2​×⋯×Fn​来计算的。

5.1.4 One Bidder and One Item, Revisited

在我们的贝叶斯模型中，单一竞标者、单一物品的拍卖很容易进行推理。固定价格为 r 的期望收益简单地表示为：

r ⋅ ( 1 − F ( r ) ) r \cdot (1 - F(r)) r⋅(1−F(r))

给定一个分布 F，通常可以很简单地求解出最佳固定价格 r。最优的固定价格被称为分布 F 的垄断价格（monopoly price）。

由于 DSIC 机制就是固定价格（或其分布），设定垄断价格就是一个收益最大化的拍卖。例如，如果 F 是[0, 1]区间上的均匀分布，即 F ( x ) = x F(x) = x F(x)=x在 [0, 1]上成立，那么垄断价格为 1/2，可实现的期望收益为 1/4。

5.1.5 Multiple Bidders

当涉及两个竞标者时，情形就变得复杂了，此时 DSIC 拍卖的空间比固定价格的空间更为复杂。例如，考虑一个有两个竞标者的单一物品拍卖，他们的估值是独立地从[0, 1]区间上的均匀分布中抽取的。当然，我们可以运行一个二价拍卖（见第 2.4 节）；其期望收益是较小出价的期望值，即 1/3（练习 5.1(a)）。

我们还可以为二价拍卖添加一个保留价，这类似于 eBay 拍卖中的起拍价。在带有保留价 r 的二价拍卖中，分配规则将物品授予最高出价者，除非所有出价都低于 r，这种情况下，物品将不会授予任何人。相应的支付规则是向获胜者（如果有的话）收取较高的第二高出价或保留价 r。

从收益的角度来看，添加保留价 r 有利有弊：当所有出价都低于 r 时，你会损失收益，但当恰好一个出价高于 r 时，保留价会提升收益。对于两个独立地从 [0,1] 区间上的均匀分布中抽取估值的竞标者，添加一个 1/2 的保留价会将二价拍卖的期望收益从 1/3 提高到 5/12（练习 5.1(b)）。我们能做得更好吗？无论是通过使用不同的保留价，还是采用一种完全不同的拍卖形式？