技术摘要：有限面试下的匹配市场双边时间无关遗憾

1. 问题陈述

本文探讨了匹配市场中的双边多臂老虎机学习问题，其中参与者必须在面临显著约束的情况下，通过交互来学习其偏好。该设定涉及 $n$ 个代理和 $m$ 个公司（$n \le m$），双方对彼此具有严格但未知的偏好。核心挑战包括：

1. 有限的筛选（面试）： 参与者在承诺前只能评估一小部分潜在合作伙伴。该模型将此形式化为“预匹配”面试阶段，代理选择一部分公司进行面试。这些交互产生关于匹配质量的噪声、随机信号（提示），但不保证获得奖励。关键在于，代理只能申请他们已面试过的公司。
2. 双边不确定性： 与以往通常假设公司拥有已知且固定偏好的工作不同，本模型假设公司也存在不确定性，必须随时间学习其偏好。
3. 有限的反馈： 在去中心化设定中，代理仅接收到粗粒度的匿名公司端信号。考虑了两种反馈模型：
   • 仅空缺（$V$）： 代理观察到哪些公司当前处于空缺状态。
   • 招聘变更（$V^+$）： 代理观察到哪些公司改变了其招聘状态（空缺或雇佣了不同的代理），但不揭示具体身份。
4. 策略性推迟： 为应对公司端的不确定性，本文引入了一种新颖的动作空间，允许公司策略性地推迟（保持空缺），而不是雇佣当前的首选申请人，如果它们怀疑其估计有误。该机制旨在纠正过早的承诺并稳定去中心化动态。

目标是最小化遗憾，定义为代理在真实偏好下的稳定匹配的预期奖励与 $T$ 轮内累积奖励之间的差距。本文特别针对与时间视界无关的遗憾（即 $O(1)$ 或 $O(\text{poly}(n,m))$，独立于 $T$），这比没有面试的带老虎机匹配中典型的 $O(\log T)$ 界限有了显著改进。

2. 方法论

本文提出了针对中心化和去中心化市场设定的算法，利用面试作为“老虎机提示”的概念。

核心机制

• 面试作为提示： 代理每轮面试 $k$ 家公司（通常 $k=2$）。其中一家公司通过轮询方案（$f^{RR}_a(t)$）选择以确保均匀探索，另一家则是根据偏好估计确定的目标申请公司（$f^{apply}_a(t)$）。
• 策略性拒绝策略（算法 1）： 不确定的公司维护对代理质量的估计。如果公司当前的首选申请人未被估计为优于所有先前被拒绝的申请人（随着估计演变，这些被拒绝者现在可能更受青睐），该公司将策略性地放弃雇佣。这会生成一个空缺信号（$V$ 或 $V^+$），提醒代理重新评估，从而打破由早期公司端估计错误引起的潜在僵局。
• 经验均值： 代理和公司均使用观察到的奖励的经验平均值来更新其偏好列表。

算法范式

1. 中心化设定（算法 6）：

   • 中央面试分配器（CIA）协调面试。
   • CIA 在当前的估计偏好上运行 Gale-Shapley (GS) 算法，以确定每个代理的目标申请公司。
   • 代理面试其目标公司和一家轮询公司，然后向目标公司申请。
   • 该设定通过确保一旦估计“有效”（相对于稳定匹配正确排序），系统立即收敛，从而实现与时间视界无关的遗憾。

2. 去中心化设定：

   • 协调式（算法 7，基于 $V$ 反馈）： 代理在交替的更新和承诺阶段运行。
     • 更新： 代理基于固定的偏好快照同步运行分布式 GS 执行。
     • 承诺： 代理申请其分配的匹配。
     • 协调： 如果代理检测到偏好不一致或策略性拒绝（通过空缺信号），它通过放弃申请来发出切换回更新阶段的信号。
   • 无协调式（算法 3 和 9，基于 $V^+$ 反馈）：
     • 代理独立行动，对招聘变更（$V^+$）做出反应。
     • 代理维护一个候选公司集合，这些公司要么从未拒绝过它们，要么最近改变了雇佣。
     • 通用市场（算法 9）： 为防止在具有多个稳定匹配的市场中出现无限循环，代理使用 $k=3$ 次面试（当前目标、上一目标、轮询），并以概率 $\lambda$ 向一组公司申请。这种随机化打破了阻塞对循环。

3. 主要贡献

1. 针对不确定公司的策略性推迟： 本文将推迟引入为双边学习的模块化原语。这是第一项将公司动作空间从“总是雇佣”扩展出去的工作，允许公司在有限反馈下纠正早期错误并稳定去中心化学习。
2. 恒定面试次数下的时间无关遗憾： 作者证明，每轮恒定数量的面试（具体为 $k=2$）足以实现时间无关的遗憾。这改进了以往带老虎机匹配文献中的 $O(\log T)$ 保证。
3. 解决开放猜想： 在单代理情况下，本文解决了 Bhaskara 等人 [6] 的一个开放猜想，表明使用经验均值时，两个提示（面试）足以实现时间无关的遗憾，而此前猜想需要三个。
4. 匿名下的去中心化学习： 这项工作提供了首个去中心化算法，仅使用匿名公司端状态信号（空缺或招聘变更）即可实现时间无关的遗憾，即使公司存在不确定性和策略性行为。

4. 结果

本文确立了以下遗憾界限（其中 $\Delta$ 代表最小奖励差距）：

• 中心化（算法 6）：

  • 遗憾：$O(nm^2 \Delta^{-2})$。
  • 最优性：在信息论下界 $\Omega(nm)$ 的 $m$ 倍范围内。作者猜想 $O(nm^2)$ 是紧确的。

• 去中心化协调式（算法 7，$V$ 反馈）：

  • $\alpha$-可约市场： $O(n^3m^2 \Delta^{-2})$。
  • 通用市场： $O(n^4m^2 \Delta^{-2})$。
  • 这些界限反映了分布式 GS 执行的成本（$O(n^2)$）乘以中心化学习成本。

• 去中心化无协调式（算法 3/9，$V^+$ 反馈）：

  • $\alpha$-可约市场（$k=2$）： $O(n^3m^2 \Delta^{-2})$（依赖于市场的常数）。
  • 通用市场（$k=3$）： $O(\epsilon^{-1} n^5 m^4 \Delta^{-2})$，其中 $\epsilon$ 取决于随机化参数 $\lambda$，并随 $n$ 和 $m$ 指数衰减。
  • 通用市场中的指数因子源于需要在无协调的情况下打破循环阻塞对动态的需求。

5. 意义与主张

本文声称通过明确建模公司不确定性并引入策略性推迟，提供了一个更通用的去中心化双边学习框架。其意义在于：

• 放宽强假设： 它改进了以往的工作（例如 Liu 等人 [19]），去除了公司拥有已知偏好的假设，并在显著更弱的反馈下运行（匿名信号对比完全匹配身份揭示）。
• 效率： 它证明了仅使用每轮恒定数量的低成本预匹配交互，即可学习稳定匹配，并实现接近最优的、与时间视界无关的遗憾。
• 稳定性： 策略性推迟机制被证明对于纠正公司学习时的去中心化系统中的不稳定性至关重要，防止系统因早期估计错误而陷入次优状态。

作者指出，虽然他们的界限对于中心化和结构化去中心化设定是接近最优的，但通用无协调市场中的指数常数突显了在没有协调或更丰富反馈的情况下解决阻塞对的固有难度。他们将在非结构化市场中推导无协调算法的紧确下界作为一个未解决的问题留待未来研究。