Stability and Efficiency of Random Serial Dictatorship

技术摘要：随机序列独裁制的稳定性与效率

问题陈述
本文探讨了“截断表示”框架在大型匹配市场中的有效性，具体背景为随机序列独裁制（RSD）机制。尽管由 Azevedo 和 Leshno（2016）以及 Menzel（2015）提出的截断表示法已成为研究大型市场的标准且易于处理的分析工具（并构成了 Abdulkadroğlu 等人（2017）等实证研究的基础），但其理论有效性此前仅在渐近极限下得到确立，即学生数量（$n$）趋于无穷大，而学校数量（$m$）保持有限。

核心问题在于，这种表示法在“现实世界”情境中是否依然准确，即当 $n$ 和 $m$ 同时大幅增长，特别是当两者量级相当时。本文研究了在任意学生偏好下，RSD 截断值（定义为被录取学生中排名最低者的归一化排名）向确定性对应值的非渐近收敛性。

方法论
作者摒弃了传统的机制设计文献，转而采用随机算法和离散概率中的分析工具。核心方法论包括：

1. 概率界限：建立 RSD 彩票概率和截断值的集中不等式。
2. Lipschitz 分析：利用 Talagrand 的测度集中结果（Talagrand, 1995）以及排列上汉明距离的性质，来界定偏好特定学校的学生数量的波动范围。
3. 相变分析：探究学生数量（$n$）与学校数量（$m$）之间的关系，以识别截断值收敛与发散的机制。

分析基于学生随机排列 $\Pi$ 定义学校的截断值 $\gamma_k$。它将观测到的随机截断值与确定性截断值 $\bar{\gamma}_k$ 进行比较，后者通过偏好某学校胜过其被分配选项的学生数量的期望值来定义。

主要贡献与结果

• 相变阈值：本文确定了 RSD 截断值行为中的一个关键相变，发生在 $m \ln m \asymp n$ 的区域。

  • 低于阈值（$n \lesssim m \ln m$）：截断值不统一收敛。本文提供了一个示例，证明如果 $n \leq \alpha m \ln m$（其中 $\alpha$ 为有限常数），则最小截断值不会依概率收敛于 1，这意味着截断表示法无效。
  • 高于阈值（$n \gg m \ln m$）：截断值以高概率统一收敛于 1（更一般地，收敛于其确定性对应值）。

• 非渐近收敛定理（定理 1）：
  对于固定的学生偏好和均匀随机排序，本文证明对于任何容量为 $\alpha_k$ 的学校 $k$，观测到的截断值 $\gamma_k$ 会集中在一个确定性值 $\bar{\gamma}_k$ 周围。具体而言：
  $$P(|\gamma_k - \bar{\gamma}_k| \geq \varepsilon) \leq 17 \exp\left\{ -\frac{\varepsilon \alpha_k}{32 \bar{\gamma}_k} \right\}$$
  该界限即使在面对对抗性（任意）学生偏好时依然成立。

• 统一收敛（推论 1）：
  通过对所有 $m$ 所学校应用联合界，本文确立了截断值向量的统一收敛性，其概率为 1，前提是容量为 $n/m$ 且满足条件 $m \ln m \ll n$ 的渐近序列。

• 结果的尖锐性：
  本文证明了条件 $m \ln m \ll n$ 是尖锐的。所提供的示例表明，若缺乏该条件（特别是当 $n$ 与 $m \ln m$ 相当时），即使在简化的确定性偏好结构中，统一收敛也会失效。

意义与主张
本文声称解决了关于截断表示法是否能充分描述学校和学生的数量规模相近的现实世界匹配市场这一开放性问题。通过证明在条件 $m \ln m \ll n$ 下的非渐近收敛，作者为以下方面提供了理论依据：

1. 依赖截断表示法的统计估计量（例如估算学校的增值效应）的有限样本准确性。
2. 在 $n$ 和 $m$ 均趋于无穷大的情境下截断表示法的渐近有效性，前提是学生的增长速度超过 $m \ln m$。

该工作的独特之处在于表明，RSD 概率的集中性即使在面对对抗性偏好时也成立，这种鲁棒性是此前仅限于有限学校极限的渐近结果所无法保证的。研究结果表明，虽然 RSD 在相对于学校数量足够大的市场中是稳定且高效的，但如果学校数量相对于学生数量增长过快，“大市场”近似将失效。