Two-Stage Stochastic Capacity Expansion in Stable Matching under Truthful or Strategic Preference Uncertainty

Each language version is independently generated for its own context, not a direct translation.

这篇论文探讨了一个非常现实且棘手的问题：在不知道大家具体想要什么的情况下，如何提前决定“资源”该增加多少？

为了让你轻松理解，我们可以把这篇论文想象成**“学校扩建与招生”的寓言故事**，并引入几个生动的比喻。

1. 核心故事：校长、学生与未知的未来

想象一下，你是一所大城市的学区管理者（清道夫/中央机构）。你的任务是决定明年给每所学校扩建多少个新教室（增加容量）。

困难点一：时间差（两阶段决策）
你需要在今天就决定扩建多少教室（第一阶段），但学生们明年才会告诉你他们真正想去哪所学校（第二阶段）。
- 比喻： 就像你要在冬天决定明年春天种多少棵苹果树，但你不知道明年春天大家是更想吃红苹果还是青苹果，也不知道大家会不会突然想吃梨。
困难点二：不确定性（随机偏好）
学生的喜好是随机的。有的学生可能突然喜欢离家近的，有的喜欢有游泳池的。这种不确定性是外生的（就像天气一样，不受你控制）。
困难点三：学生的“小心思”（策略性行为）
这是论文最精彩的部分。学生不是只会说真话的机器人。他们会动脑筋：
- 如果我知道 A 学校今年扩招了，录取概率大，我可能会把 A 学校排在第一位，哪怕我其实更喜欢 B 学校。
- 如果我知道 C 学校很难进，我可能根本不敢把它填在志愿表上，以免浪费名额。
- 比喻： 这就像**“点菜”**。如果我知道“红烧肉”今天特价且人手不够，我可能会为了保险起见，把“红烧肉”排在菜单第一位，哪怕我其实更想吃“清蒸鱼”。我的点菜行为（报告偏好）取决于餐厅的库存（学校容量）。

2. 论文解决了什么？

以前的研究通常假设：

学生总是说真话（不管学校扩不扩招，我都只填我最喜欢的）。
或者，学校扩招是基于“平均情况”决定的（比如：大家都喜欢 A 学校，所以多建 A 学校）。

这篇论文说：“不对！现实更复杂！”
它提出了一个**“两步走”的随机规划模型**：

第一步（决策）： 校长在不知道学生具体名单的情况下，根据概率和学生可能的心理活动，决定扩建哪些学校。
第二步（匹配）： 学生根据学校的新容量，结合自己的真实喜好和“录取几率”，提交志愿表。最后，系统用算法（稳定匹配）把学生和学校配对。

3. 三种“学生性格”模型

论文研究了三种学生行为模式，就像三种不同的“点菜风格”：

老实人模式 (UM - 效用最大化)：
- 比喻： 学生是“直肠子”。不管学校扩不扩招，我只填我真心最喜欢的前 K 所学校。
- 结果： 这种不确定性是“外生”的，就像天气一样，学校容量变了，学生的喜好列表不变。
精算师模式 (CEUM - 联合期望效用最大化)：
- 比喻： 学生是“精明的赌徒”。他们会计算：如果我填了 A 学校（虽然我不那么喜欢，但录取率高），万一被 A 录取了，我就去不了我真正喜欢的 B 学校了（因为 B 学校可能没名额了）。他们会权衡**“被录取的概率”和“被更喜欢的学校拒绝的风险”**。
- 结果： 这种不确定性是**“内生”的**。学校容量变了 -> 学生觉得录取几率变了 -> 学生填的志愿表变了。这是一个**“你变我也变”**的循环。
简化版赌徒模式 (IEUM - 个体期望效用最大化)：
- 比喻： 学生也是“赌徒”，但脑子稍微简单点。他们只看“这所学校录取我的概率”和“我喜不喜欢”，忽略了“如果我被这所学校录取，我就去不了更喜欢的学校”这种复杂的连锁反应。
- 结果： 也是一种内生不确定性，但比精算师模式简单。

4. 论文发现了什么？（关键结论）

作者用数学公式和计算机模拟（就像在电脑里跑了几千次模拟实验）发现：

不要只看“平均数”： 如果你只根据“平均喜好”去扩建学校（比如大家都喜欢 A，就只扩 A），结果往往很糟糕。因为当学校真的扩招后，学生的策略会改变，导致原本的计划失效。
- 比喻： 就像如果你只根据平均气温带伞，可能下雨时没带，晴天时带多了。必须考虑“下雨”和“晴天”两种可能性的分布。
猜错学生心思代价很大： 如果你以为学生是“老实人”（模式 1），结果他们其实是“精算师”（模式 2），你扩建的学校可能完全不是学生想要的，导致很多学生进不了理想的学校，或者学校空着。
- 比喻： 你给“老实人”准备了红烧肉，结果来了一群“精算师”，他们因为红烧肉太好抢而不敢点，最后大家都没饭吃。
数学工具很强大： 作者开发了一套新的算法（SAA 方法 + 启发式算法），能在电脑里快速算出“最优扩建方案”。即使学生很狡猾，这套方法也能找到接近完美的方案。

5. 这对我们意味着什么？

这篇论文不仅仅是在讲学校招生，它适用于任何**“先定资源，后看需求”**的场景：

医院： 在不知道明年流感爆发时大家想去哪个科室的情况下，先决定增加多少床位。
难民安置： 在不知道难民家庭具体想去哪个城市前，先决定在各个城市建多少安置房。
疫苗分配： 在不知道大家想去哪个接种点前，先决定每个点发多少疫苗。

一句话总结：
这篇论文告诉我们，在规划未来时，不能只盯着“平均需求”，也不能假设大家都会“老实听话”。必须考虑到未来的不确定性以及人们会根据你的决策而改变策略这一事实。只有用更聪明的数学模型（像论文里那样）来模拟这些复杂的互动，才能避免资源浪费，让每个人（学生、患者、难民）都能得到更好的结果。

Each language version is independently generated for its own context, not a direct translation.

1. 问题背景与定义 (Problem Statement)

核心问题：
该研究解决的是两阶段随机容量扩展稳定匹配问题 (2-STMMP)。这是一个在双边多对一匹配市场（如学校选择、住院医师匹配）中，在学生偏好尚未揭示的情况下，提前决定学校容量扩展的优化问题。

关键特征与时间线：

第一阶段（决策阶段）： 清道夫（Clearinghouse，如教育局）在观察学生偏好之前，根据预算决定学校的容量扩展方案（增加座位数）。此时，学生的真实偏好是未知的随机变量。
第二阶段（匹配阶段）： 学生的真实偏好被揭示（或根据策略生成报告偏好），清道夫基于已确定的扩展容量和学生的报告偏好，运行学生最优稳定匹配算法（如延迟接受算法 DAA）。

不确定性来源：

外生不确定性 (Exogenous Uncertainty)： 学生真实偏好是随机的（例如，受通勤距离、学校质量等影响），且独立于容量决策。
内生不确定性 (Endogenous Uncertainty)： 学生可能策略性地报告偏好。他们的报告偏好不仅取决于真实偏好，还取决于他们感知到的录取概率，而录取概率又直接受第一阶段容量决策的影响。

学生行为模型：
论文定义了三种学生行为模式：

效用最大化 (UM, Utility Maximization)： 学生诚实报告其真实的前 $K$ 所偏好学校。偏好是外生的。
联合期望效用最大化 (CEUM, Conjoint Expected Utility Maximization)： 学生策略性地选择前 $K$ 所学校，以最大化联合期望效用。他们考虑了被更偏好学校拒绝的风险（即“投资组合选择”问题）。
个体期望效用最大化 (IEUM, Individual Expected Utility Maximization)： 学生策略性地选择前 $K$ 所学校，仅最大化每所学校的个体期望效用（录取概率 $\times$ 效用），忽略了被更偏好学校拒绝的风险（一种有界理性的简化模型）。

目标：
在满足预算约束的前提下，选择容量扩展方案，以最小化期望的学生匹配排名总和（即最大化学生福利）。

2. 方法论 (Methodology)

由于偏好空间巨大且连续，直接枚举所有场景不可行，作者采用了样本平均近似 (Sample Average Approximation, SAA) 方法将随机规划问题转化为确定性等价问题。

2.1 数学建模

偏好转换： 对于策略性行为（CEUM 和 IEUM），作者利用 Bazotte 等人 (2025) 的随机变量转换方法，将内生的报告偏好定义为第一阶段容量决策 ( $x$ ) 和外生真实偏好 ( $u$ ) 的函数。
双层规划结构： 在策略性行为下，问题本质上是一个双层规划：
- 上层： 优化容量决策 $x$ 。
- 下层： 学生根据 $x$ 和 $u$ 求解各自的效用最大化问题（Program 4 或 Program 6），生成报告偏好。
单层级化： 作者为 CEUM 和 IEUM 推导了精确的单层级混合整数线性规划 (MILP) 公式。
- 对于 CEUM：基于边际改进算法 (MIA) 构建约束，引入辅助变量线性化非线性概率项。
- 对于 IEUM：基于个体效用排序算法 (IOA) 构建约束。
- 对于 UM：使用改进的 L-约束公式。

2.2 求解算法

由于 SAA 问题在策略性行为下是 NP-hard 的，作者提出了一套精确与启发式相结合的求解工具箱：

精确方法 (Exact Methods)：
- 使用商业求解器 (Gurobi) 直接求解 SAA 的 MILP 公式。
- 对于策略性行为，由于内生性导致线性松弛较弱，精确求解在大规模问题上非常困难。
拉格朗日松弛启发式 (Lagrangian Heuristic, LR)：
- 适用场景： 主要针对 UM 行为。
- 原理： 松弛稳定性约束，利用次梯度法求解拉格朗日对偶问题，获得紧的下界。结合 DAA 算法计算上界。
- 优势： 比线性松弛提供更强的下界，计算效率高。
局部搜索启发式 (Local Search Heuristics)：
- 贪婪局部搜索 (LS)： 爬山法，通过增加容量、转移容量或交换容量来探索邻域。
- 模拟退火 (SA)： 概率性搜索，允许接受劣解以跳出局部最优。
- 通用性： 适用于所有三种行为模式 (UM, CEUM, IEUM)。
- 流程： 在邻域内生成新容量方案 $\to$ 根据行为模型计算学生报告偏好 $\to$ 运行 DAA 计算匹配结果 $\to$ 评估目标函数。

3. 主要贡献 (Key Contributions)

问题形式化： 首次正式定义并研究了在偏好不确定性（包括内生性策略偏好）下的两阶段稳定匹配容量扩展问题 (2-STMMP)。
行为建模与转换： 将三种学生行为（诚实、CEUM、IEUM）整合到统一的优化框架中。特别是通过随机变量转换技术，将内生的策略性偏好转化为第一阶段的显式函数，解决了内生不确定性建模的难题。
算法创新：
- 提出了针对策略性行为的精确单层级 MILP 公式。
- 开发了高效的启发式算法（LR, LS, SA），能够处理大规模实例和复杂的内生不确定性，填补了该领域求解方法的空白。
实证分析： 通过大量实验，量化了不确定性建模和行为建模对容量决策的影响，证明了忽略这些因素会导致显著的效率损失。

4. 实验结果 (Experimental Results)

实验使用了小规模（50-100 学生）和大规模（500-1000 学生）实例，对比了 SAA 方法与确定性平均场景方法 (EV)。

4.1 随机解的价值 (Value of Stochastic Solution, VSS)

SAA 优于 EV： 在所有行为模式下，SAA 方法得出的容量决策均显著优于基于平均场景的确定性方法。
指标提升：
- 匹配质量： SAA 方案使学生匹配到更偏好学校的比例更高（VSS 在 UM 下可达 9.33%）。
- 入学与改进： 在预算较大时，SAA 方案能显著增加未匹配学生的入学率（VSS-E）和已匹配学生的升级率（VSS-I）。
结论： 显式建模偏好不确定性对于制定有效的容量规划至关重要。

4.2 行为假设的影响 (Impact of Behavioral Assumptions)

错误假设的代价： 如果清道夫假设学生是诚实的 (UM)，而学生实际上是策略性的 (CEUM 或 IEUM)，容量决策的质量会显著下降。
- 当 $K$ （偏好列表长度）较小时，策略性行为与诚实行为差异巨大，导致决策失误严重。
- 当 $K$ 较大时，CEUM 行为下的报告偏好更接近 UM，此时假设 UM 带来的损失较小；但 IEUM 行为下差异依然显著。
策略模型误判： 即使假设了策略性行为，如果错误地假设了具体形式（例如假设 IEUM 而实际是 CEUM），也会导致显著的性能损失。这表明准确识别策略行为的具体形式与识别策略行为的存在同样重要。

4.3 计算性能

UM 行为： 拉格朗日松弛 (LR) 和模拟退火 (SA) 表现优异，能在短时间内获得高质量解（上界差距 < 0.5%）。
策略性行为 (CEUM/IEUM)： 精确求解非常困难（大规模实例往往无法在 8 小时内收敛）。
- SA 启发式表现最佳，在计算时间和解质量之间取得了最佳平衡，显著优于 LS 和精确求解器。
- 策略性行为下的计算成本比 UM 高 2-3 倍，主要源于需要为每个场景运行 MIA 或 IOA 算法来生成偏好。

5. 意义与启示 (Significance)

政策制定指导： 对于学校选择、医疗资源分配等公共政策领域，该研究证明了在容量规划阶段必须考虑未来的不确定性和参与者的策略行为。仅基于历史平均数据或假设参与者诚实的规划会导致资源错配（过度建设或建设不足）和学生福利损失。
理论突破： 将内生不确定性（决策依赖分布）引入稳定匹配领域，并提供了有效的求解框架，扩展了随机规划和匹配理论的应用边界。
实际应用价值： 提出的启发式算法工具箱使得在大规模现实场景（如数千名学生、数十所学校）中快速制定容量决策成为可能，特别适用于需要快速响应或预算受限的决策环境。
未来方向： 该框架可进一步扩展至容量缩减、学费减免分配、共同配额限制等更复杂的场景，以及难民安置、医疗资源分配等其他两阶段匹配问题。

总结： 该论文通过严谨的数学建模和高效的算法设计，揭示了在稳定匹配市场中，“何时做决策”（容量决策在偏好揭示之前）与**“如何建模行为”**（是否考虑策略性）对系统绩效的决定性影响，为优化公共资源配置提供了强有力的理论支持和实用工具。