对于密度非递减分布在两个物品场景下的确定性最优机制

《Journal of Mathematical Economics》：On deterministic optimal mechanisms in a two-item setting for distributions with nondecreasing density

　　

**摘要** 考虑如下问题：当两个异质物品被出售给一位对物品拥有独立估值的单一买家时，如何设计一个收入最优的拍卖机制。假设买家对物品的估值的分布具有密度函数，该密度函数在其支撑集 $[c_i, c_i + b_i]$（正半轴上）上是正的、非递减的且连续可微的。我证明，当至少一个最低估值（即 $c_1$ 或 $c_2$）足够高时，最优机制是确定性的。我提供了一种方法来计算 $(c_1, c_2)$ 的阈值，超过该阈值后最优机制即为确定性的。我还提供了买家估值分布满足个体销售机制最优的充分条件。我表明，当 $c_1$ 较低而 $c_2$ 较高时，对卖方而言最优策略是以最低估值 $c_2$ 出售物品 2，从而将问题有效地简化为仅对物品 1 寻找一维设定下的最优机制。我基于令人鼓舞的初步结果提出猜想，认为这一结论可以推广到三物品设定。具体而言，我猜想当 $c_1$ 和 $c_2$ 较低但 $c_3$ 较高时，对卖方而言最优策略是以最低估值 $c_3$ 出售物品 3，从而将问题有效地简化为对物品 1 和 2 寻找二维设定下的最优机制。

**引言** 考虑设计一个收入最优机制以将两个异质物品出售给一位买家的问题。买家对物品的估值 $z$ 是其私人信息，但其估值所服从的分布 $f$ 被假设为共同知识。卖方旨在设计一个最大化其期望收入的机制，其中期望是相对于分布 $f$ 计算的。该问题在一物品设定下的一般解法由 Myerson（1981）给出。他证明，该设定下的收入最优机制具有简单的结构；它仅是一个基于保留价格的"要么接受，要么走开"的报价，该保留价格取决于 $f$。然而，在二物品设定下找到一般解一直是一个公认的难题。此外，该设定下的收入最优机制展现出多种不同的结构。例如，对于某些分布，最优机制具有无限菜单（Daskalakis 等人，2013；Daskalakis 等人，2017）。同样，具有相同分布但不同支撑集的最优机制可能有许多不同的结构（Thirumulanathan 等人，2016；Thirumulanathan 等人，2019b）。

在本文中，我考虑了一类特殊的分布，并证明当至少一个物品的最低估值较高时，最优机制是确定性的。更具体地说，我假设买家对物品 $i$ 的估值的分布具有严格为正、非递减且连续可微的密度函数 $f_i$，其支撑集为 $[c_i, c_i + b_i]$。我分析了当支撑集 $[c_1, c_1 + b_1] \times [c_2, c_2 + b_2]$ 变化时，最优机制的变化情况。主要结果——定理 4——表明，当 $c_1$ 较低且 $c_2$ 较高，或者当 $c_2$ 较低且 $c_1$ 较高时，拍卖者使用 Myerson 的收入最优机制逐个出售物品是最优的；而当 $c_1$ 和 $c_2$ 都较高时，则将物品捆绑出售是最优的。见图 1。

本文的主要结果可以解释如下。从 $(c_1, c_2) = (0, 0)$ 出发，假设分布的支撑集在垂直方向、水平方向或两者上同时趋向无穷。我证明，在所考虑的分布下，最优机制最终要么表现为捆绑销售，要么表现为个体销售，具体取决于 $c_1$ 和 $c_2$ 是否都很高，还是只有其中一个较高。无论哪种情况，最优机制最终都是确定性的。这一解释在图 1 中进行了展示。

此外，我证明对于每一个 $c_1$，都存在一个 $c_2^*(c_1)$，使得对于所有 $c_2 \geq c_2^*(c_1)$，最优机制都是确定性的。我还提供了一种方法来计算任何给定 $c_1$ 的阈值 $c_2^*(c_1)$。对每个 $c_2$ 也存在类似的断言。此外，我还推导了密度函数 $f_i$ 满足个体销售机制最优的充分条件。这些条件主要基于虚拟估值函数和风险率条件，因此对于任何 $f_i$ 都易于验证。

主要结果（定理 4）的另一种解释如下。当 $c_1$ 较低且 $c_2$ 较高时，卖方发现以物品 2 的最低估值 $c_2$ 出售物品 2 是最优的。因此，问题实际上简化为仅对物品 1 寻找一维设定下的最优机制。我猜想这一性质可以推广到三物品设定。具体而言，我考虑了一个例子，其中物品的估值独立地服从 $\text{Unif}[0,1] \times [0,1] \times [c_3, c_3 + 1]$ 分布，且 $c_3 \geq 3$，并证明在此例子中，最优机制是以最低估值 $c_3$ 出售物品 3，并按二维设定下的最优机制出售物品 1 和 2。基于此例子，我猜想当 $c_1$ 和 $c_2$ 较低但 $c_3$ 较高时，问题实际上简化为对物品 1 和 2 寻找二维设定下的最优机制。

我的方法从最优菜单定理出发（Daskalakis 等人，2017）。该定理为具有有限个常数分配区域的机制提供了必要且充分的最优性条件。这些必要且充分条件基于定义在二维空间上的测度的二阶随机优势。在实践中，这些条件很难验证。在本文中，我将个体销售机制视为一个特例，并利用最优菜单定理推导出支撑集参数 $(c_1, c_2)$ 的充分条件，以证明该机制的最优性。

更具体地说，我将注意力限制在密度函数在其定义域上是正的、非递减且连续可微的分布上，并发现当 $c_1$ 较低且 $c_2$ 较高，或者当 $c_2$ 较低且 $c_1$ 较高时，个体销售机制是最优的。此外，我观察到在二维设定下寻找最优机制的问题可以简化为一维问题。本文的技术贡献在于为一类广泛的分布证明了定义在二维空间上的测度的二阶随机优势。

然后我考虑捆绑销售机制，并计算该机制最优时 $(c_1, c_2)$ 的取值。这些取值利用 Menicucci 等人（2015）的结果以直接方式计算得出，该结果提供了捆绑销售机制在特定条件下最优的充分条件。我证明当 $c_1$ 和 $c_2$ 都足够高时，捆绑销售机制是最优的。此外，我还提供了一种方法来计算 $(c_1, c_2)$ 的阈值，从该阈值开始，个体销售机制或捆绑销售机制之一是最优的。

最后，我考虑了三维设定以检验是否能得到类似的结果。我首先利用最优菜单定理证明，当 $c_1$、$c_2$ 和 $c_3$ 都较高时，捆绑销售机制是最优的。然后我考虑了一个特定例子，其中估值服从均匀分布，并利用最优菜单定理证明，当 $(c_1, c_2) = (0, 0)$ 但 $c_3 \geq 3$ 时，三维问题可以简化为二维问题。因此，我证明了定义在三维空间上的一个测度的二阶随机优势，但这仅针对一个特定例子。

自 1981 年 Myerson 刻画一维设定下的最优机制以来，多维最优机制的设计一直是文献中关注的领域。关于该文献的全面综述请参见 Rochet 和 Stole（2003）。在本小节中，我将注意力限制在那些要么推导出多维设定下的精确解，要么利用虚拟估值或风险率条件推导定性结果的工作中。

在二物品设定下，Daskalakis 等人（2013）和 Giannakopoulos 及 Koutsoupias（2015）已为一大类分布显式计算了最优机制。具体而言，Daskalakis 等人（2013）设计了一个算法来计算最优机制，当分布产生良构的典范划分时。然而，他们考虑的分布的支撑集形式为 $[0, b_1] \times [0, b_2]$。对于具有一般支撑集 $[c_1, c_1 + b_1] \times [c_2, c_2 + b_2]$ 的分布的最优机制，在文献中仅针对极少数分布进行了推导。在本文中，我分析了当分布的支撑集变化时最优机制的变化情况。

关于具有一般支撑集的分布，Daskalakis 等人（2017）证明了最优菜单定理，并为一些支撑集不受坐标轴包围的示例分布提供了显式解。Thirumulanathan 等人（2016）、Thirumulanathan 等人（2019b）将注意力限制在均匀分布上，并为所有可能的支撑集 $[c_1, c_1 + b_1] \times [c_2, c_2 + b_2]$ 推导了精确的最优机制。在 $n$ 物品设定下，Giannakopoulos 和 Koutsoupias（2014）在买家估值的分布在 $[0,1]^n$ 上均匀时提供了精确解（$n \leq 6$）。Babaioff 等人（2018）表明，对于任何买家估值分布，二物品设定下的最优确定性机制是次模的且单调的，但当物品数量超过两个时，该机制可能是超模的且非单调的。Hashimoto 等人（2025）考虑了 $n$ 物品中的单位需求设定，并证明当买家估值的分布是尺度单调的时，以相同价格出售每个物品是最优的。Chen 等人（2019）考虑了多物品多买家设定，并证明对于每一个激励相容的随机机制，都存在一个等效的确定性机制，该机制能提供相同的社会剩余。

文献中的多篇论文利用虚拟估值函数和风险率条件获得了最优机制的定性结果。Menicucci 等人（2015）、Pavlov（2011a）以及 Haghpanah 和 Hartline（2015）、Haghpanah 和 Hartline（2021）的论文利用买家的虚拟估值证明了某些机制的最优性。Pavlov（2011b）、Tang 和 Wang（2017）、Wang 和 Tang（2014）以及 Manelli 和 Vincent（2006）的论文考虑满足风险率条件的分布，并证明了在二物品设定下最优机制的定性结果。在我的论文中，虚拟估值和风险率条件都被用来建立确定性机制的最优性。

此外，关于计算最优机制的近似解也有大量文献。关于近似解的相关文献请参见 Babaioff 等人（2017）、Babaioff 等人（2014）、Cai 等人（2016）、Cai 和 Zhao（2017）、Chawla 等人（2015）、Chawla 和 Miller（2016）、Hart 和 Nisan（2012）、Yao（2014）等。一些近期文献也涉及利用深度学习方法计算最优机制，例如 Dütting 等人（2019）、Dütting 等人（2021）、Dütting 等人（2024）、You 等人（2023）等。然而，我的论文专注于通过解析方法推导精确解。

本文其余部分组织如下。第 2 节描述了论文中考虑的两物品一买家设定以及本文其余部分将使用的术语定义。第 3 节陈述并证明了关于密度函数非递减的分布的最优确定性机制的主要结果。第 4 节描述了向三物品设定的推广。第 5 节为结论。

**第 2 节片段：预备知识**

考虑在 $n$ 物品一买家设定下设计收入最优机制的问题，此时买家对物品的精确估值 $z = (z_1, \ldots, z_n)$ 是其私人信息，但其估值所服从的分布是共同知识。我假设 $z_i$，$i = 1, 2, \ldots, n$，是绝对连续的随机变量且彼此独立，并且 $z_i \sim f_i$，$(z_1, \ldots, z_n) \sim f\left(= \prod_{i=1}^{n} f_i\right)$。累积分布函数记为 $F_i$。$f_i$ 的支撑集为

**第 3 节：主要结果**

我首先考虑将两个异质物品出售给一位买家的设定。我考虑买家估值的分布满足某些充分条件，并证明当至少一个物品的最低估值足够高时，最优机制是确定性的。

**第 4 节：向三物品设定的推广**

现在我考虑一个推广情形，即将三个异质物品出售给一位买家。

因此，我考虑三种分布，其密度函数由 ????:[0,????]→??, ??=1,2,3 给出，每个密度函数在其定义域上严格为正、非递减且连续可微。买家对物品 ?? 的估值分布由 ?????(????)={?????(?????????)，若 ????∈[????,????+????]；0，其他} 给出，其中 ????≥0 为某个常数。我现在分析最优机制如何随 (??1,??2,??3) 变化。我首先观察到 ?? 的性质以及结论 I

我研究了将两个异质物品卖给单一买家的问题，买家对物品的估值 (??1,??2)～??1???2，且 ???? 的支撑集为非负轴上的区间 [????,????+????]。我将注意力限制在密度函数 ??1 和 ??2 上，这些函数满足严格为正、非递减且连续可微的条件。我分析了当分布固定而支撑集参数 (??1,??2) 变化时，最优机制如何变化。我证明了最优机制是确定性的

利益冲突声明：作者声明不存在可能影响本文所报告工作的已知的竞争性经济利益或个人关系。

致谢：本工作得到了科学与工程研究委员会在核心研究资助 (CRG) 计划下的资助 [批准令号：CRG/2022/009169]；以及印度坎普尔理工学院在启动资助计划下的资助 [项目编号：IITK/ECOS/2020123]。作者感谢 Debasish Mishra 教授提供了非常富有启发性的讨论。

D. Thirumulanathan