学会匹配：具有时间扩展反馈的双边匹配

# 学习匹配：具有时间延展反馈的双边匹配

来源：https://arxiv.org/html/2606.06744

Haijing Zong∗1Yancheng Liang∗2Boyang Zhou2Natasha Jaques2
1Department of Economics, University of Washington, Seattle, United States
2Paul G. Allen School of Computer Science & Engineering, University of Washington, Seattle, United States
∗同等贡献。通讯作者：[email protected]

###### 摘要

双边匹配市场通常涉及随时间推移通过面试、重复互动、学习和分离而展开的信息。现有匹配模型通常将此过程简化为关于固定偏好的即时次高斯反馈，忽略了支付相关信息逐渐揭示并改变未来匹配决策的设置。我们引入了一个具有**时间延展反馈**的框架，将双边匹配形式化为一个部分可观察马尔可夫博弈，其中包含昂贵的匹配前筛选、噪声的匹配后观测、演化的潜在特征以及内生的延续或解散决策。我们在**Learn2Match**中实例化了该框架，这是一个用于动态匹配市场的多智能体强化学习基准。Learn2Match支持对面试对象、匹配对象以及何时解散匹配进行去中心化的决策，同时使用遗憾、社会福利和信息摩擦损失（衡量因潜在偏好不完全揭示而导致的福利差距）来评估策略。我们发现，在时间延展反馈下，独立PPO实现了比赌博机风格的CA-ETC基线更高的累积社会福利和更低的累积遗憾，展示了MARL在动态匹配市场中的潜力。然而，PPO仍然产生了更高的信息摩擦损失，这表明端到端的MARL尚未提供匹配赌博机方法所具有的协调探索结构。这些结果将Learn2Match定位为开发下一代匹配市场算法的基准：这些算法像RL智能体一样具有适应性，像赌博机算法一样具有统计纪律性，并且像稳定匹配机制一样具有结构意识。

## 1 引言

参见图注

图1：Learn2Match概述，一种具有时间延展反馈的动态双边匹配框架。智能体进行面试、匹配、在任期内逐步学习，并决定是保留还是解散关系，这与传统具有即时一步反馈的赌博机匹配形成对比。

双边匹配研究的是市场中对立两侧的智能体如何根据对彼此的偏好形成配对关系。其核心解概念是**稳定性**[[15](https://arxiv.org/html/2606.06744#bib.bib99)]：不应存在一对未匹配的智能体互相偏爱对方胜过其当前配对的伙伴。经典的Gale-Shapley框架和延迟接受算法构成了这一系列工作的基础，应用于劳动力市场、住院医师匹配、学校选择、婚姻和约会市场[[15](https://arxiv.org/html/2606.06744#bib.bib99), [47](https://arxiv.org/html/2606.06744#bib.bib53), [48](https://arxiv.org/html/2606.06744#bib.bib100), [1](https://arxiv.org/html/2606.06744#bib.bib112), [18](https://arxiv.org/html/2606.06744#bib.bib9), [56](https://arxiv.org/html/2606.06744#bib.bib10)]。

然而，许多现实世界的匹配市场偏离了静态的Gale-Shapley模型[[1](https://arxiv.org/html/2606.06744#bib.bib112), [21](https://arxiv.org/html/2606.06744#bib.bib5), [6](https://arxiv.org/html/2606.06744#bib.bib56), [57](https://arxiv.org/html/2606.06744#bib.bib57), [52](https://arxiv.org/html/2606.06744#bib.bib111)]。因此，最近的研究已将稳定匹配扩展到包含学习、去中心化、不确定性和上下文信息[[22](https://arxiv.org/html/2606.06744#bib.bib61), [31](https://arxiv.org/html/2606.06744#bib.bib40), [9](https://arxiv.org/html/2606.06744#bib.bib42), [25](https://arxiv.org/html/2606.06744#bib.bib118), [45](https://arxiv.org/html/2606.06744#bib.bib120), [41](https://arxiv.org/html/2606.06744#bib.bib121), [60](https://arxiv.org/html/2606.06744#bib.bib126), [43](https://arxiv.org/html/2606.06744#bib.bib117), [5](https://arxiv.org/html/2606.06744#bib.bib124), [26](https://arxiv.org/html/2606.06744#bib.bib125), [19](https://arxiv.org/html/2606.06744#bib.bib103), [30](https://arxiv.org/html/2606.06744#bib.bib65)]。这些模型缩小了经典匹配理论与实际匹配系统之间的差距，但它们通常假设每个匹配决策都会产生即时奖励、观察或噪声信号。

然而，在许多市场中，由匹配决策产生的支付相关信息仅通过未来状态才得以实现。我们称这种现象为**时间延展反馈**。例如，在劳动力市场中，匹配质量可能在雇佣开始后随着工人获得经验、企业了解生产力以及双方决定是否继续或分离而演变[[14](https://arxiv.org/html/2606.06744#bib.bib95), [3](https://arxiv.org/html/2606.06744#bib.bib114), [27](https://arxiv.org/html/2606.06744#bib.bib43), [49](https://arxiv.org/html/2606.06744#bib.bib94), [55](https://arxiv.org/html/2606.06744#bib.bib96), [40](https://arxiv.org/html/2606.06744#bib.bib113)]。类似地，匹配前的过程如搜索、筛选、面试和谈判，在任何匹配形成之前可能会消耗大量的日历时间和精力[[34](https://arxiv.org/html/2606.06744#bib.bib44), [13](https://arxiv.org/html/2606.06744#bib.bib45), [39](https://arxiv.org/html/2606.06744#bib.bib46), [44](https://arxiv.org/html/2606.06744#bib.bib50), [11](https://arxiv.org/html/2606.06744#bib.bib97)]。因此，匹配决策可以通过持久的状态变化影响未来的机会、信息和福利，而不仅仅是通过单期反馈。在劳动力市场中，这种持久性常被描述为**职业路径依赖**：即使没有频繁的重新匹配，一个匹配也能塑造未来结果，因为雇佣关系随着任期变得更稳固[[14](https://arxiv.org/html/2606.06744#bib.bib95), [55](https://arxiv.org/html/2606.06744#bib.bib96)]。这种路径依赖的产生是因为工人随时间了解匹配契合度并积累特定职业的人力资本，因此当前匹配会影响未来的生产力、信息和流动性成本[[35](https://arxiv.org/html/2606.06744#bib.bib34), [23](https://arxiv.org/html/2606.06744#bib.bib35), [16](https://arxiv.org/html/2606.06744#bib.bib36)]。

我们提议明确地对具有时间延展反馈的双边匹配市场进行建模。与匹配赌博机公式（其中每个匹配决策产生关于固定底层偏好的一次性反馈）不同，我们将市场视为一个部分可观察马尔可夫博弈：一个顺序决策问题，其中潜在状态控制着观察、奖励和匹配机会随时间如何演变。该公式捕捉了时间反馈的三个来源：演化中的智能体特征、昂贵且持久的匹配前或匹配后阶段，以及关于潜在匹配质量的噪声部分观察。因此，智能体不仅要决定与谁匹配，还要决定何时搜索、筛选、继续、分离和探索。

我们通过**Learn2Match**实例化了该框架，这是一个用于动态双边匹配市场的基准。Learn2Match模拟了具有演化潜在特征、昂贵的匹配前和匹配后决策、噪声观察以及内生的继续或分离的智能体。我们评估了多智能体强化学习方法[[33](https://arxiv.org/html/2606.06744#bib.bib28), [46](https://arxiv.org/html/2606.06744#bib.bib27), [59](https://arxiv.org/html/2606.06744#bib.bib13), [58](https://arxiv.org/html/2606.06744#bib.bib29), [50](https://arxiv.org/html/2606.06744#bib.bib30)]与从匹配文献改编的赌博机风格基线[[42](https://arxiv.org/html/2606.06744#bib.bib33), [38](https://arxiv.org/html/2606.06744#bib.bib119)]的性能对比。我们的评估包括匹配遗憾、社会福利和**信息摩擦损失**：即基于当前观察或相信的偏好采取行动与通过充分互动揭示的真实潜在偏好所诱导的稳定匹配之间的差距。

我们在Learn2Match上测试了最先进的多智能体强化学习（MARL）算法——独立PPO[[50](https://arxiv.org/html/2606.06744#bib.bib30), [58](https://arxiv.org/html/2606.06744#bib.bib29)]，并将其与赌博机风格基线CA-ETC[[42](https://arxiv.org/html/2606.06744#bib.bib33)]进行比较。我们证明，MARL智能体在累积社会福利方面表现更好，并降低了累积遗憾，显示了MARL在时间延展反馈下的匹配市场决策中的潜力。值得注意的是，尽管性能更高，但MARL的信息摩擦损失仍高于赌博机风格算法，后者因算法设计而具有协调的探索过程。更广泛地说，Learn2Match开启了MARL与匹配理论之间的共同研究议程：它挑战MARL社区构建能够在结构化市场中协调探索和利用的智能体，同时挑战匹配和赌博机社区超越一次性偏好估计，转向在信息随时间展开时仍保持有效的算法。从这个意义上说，Learn2Match不仅是评估现有方法的基准，也是设计下一代匹配市场学习算法的呼吁：这些算法应像RL智能体一样具有适应性，像赌博机方法一样具有统计纪律性，并且像稳定匹配机制一样具有结构意识。

我们的贡献有三重。首先，我们引入了Learn2Match，一个用于具有时间延展反馈的动态双边匹配的基准，具有多轮信息获取、演化中的智能体特征以及内生的提议、回应和解散决策。其次，我们提供了将多智能体强化学习与基于赌博机的基线进行比较的初步实证研究。第三，Learn2Match开启了多智能体强化学习与匹配理论交叉领域的共同研究议程，并灵活支持现实世界应用建模——从劳动力市场和住院医师匹配到学校选择、约会和叫车调度。每当经典匹配理论的静态、完全揭示假设不成立时，该基准上的进步都能转化为更好的结果。

## 2 相关工作

具有静态信息的稳定匹配。双边匹配历来通过稳定性的视角进行研究，始于Gale-Shapley框架及其在劳动力市场、学校选择和其他集中分配场景中的应用[[15](https://arxiv.org/html/2606.06744#bib.bib99), [47](https://arxiv.org/html/2606.06744#bib.bib53), [48](https://arxiv.org/html/2606.06744#bib.bib100), [1](https://arxiv.org/html/2606.06744#bib.bib112)]。现有工作研究如何从噪声观察中学习稳定匹配或偏好，但通常假设底层静态匹配值或偏好结构[[22](https://arxiv.org/html/2606.06744#bib.bib61), [31](https://arxiv.org/html/2606.06744#bib.bib40), [9](https://arxiv.org/html/2606.06744#bib.bib42), [25](https://arxiv.org/html/2606.06744#bib.bib118), [41](https://arxiv.org/html/2606.06744#bib.bib121), [45](https://arxiv.org/html/2606.06744#bib.bib120), [60](https://arxiv.org/html/2606.06744#bib.bib126), [43](https://arxiv.org/html/2606.06744#bib.bib117), [26](https://arxiv.org/html/2606.06744#bib.bib125), [5](https://arxiv.org/html/2606.06744#bib.bib124), [30](https://arxiv.org/html/2606.06744#bib.bib65), [19](https://arxiv.org/html/2606.06744#bib.bib103)]。这些模型通常将不确定性简化为关于固定潜在偏好的噪声（如零均值次高斯）观察，并在每次互动后立即揭示反馈。这对于匹配质量通过互动和历史演变的设置是不够的。例如，在约会市场中，伴侣的特征会随着他们年龄增长和积累生活经验而演变。我们的工作建立在这些文献的基础上，同时将注意力从单纯的稳定结果识别转向一个更丰富的顺序环境，在该环境中智能体选择如何获取信息、是否匹配以及是否随时间保持匹配。

**摩擦性搜索和匹配后学习**被大量经济学文献广泛研究[[34](https://arxiv.org/html/2606.06744#bib.bib44), [13](https://arxiv.org/html/2606.06744#bib.bib45), [39](https://arxiv.org/html/2606.06744#bib.bib46), [44](https://arxiv.org/html/2606.06744#bib.bib50), [53](https://arxiv.org/html/2606.06744#bib.bib89), [11](https://arxiv.org/html/2606.06744#bib.bib97)]，强调雇佣匹配不是即时分配。这些市场受昂贵的职位空缺发布、筛选和招聘摩擦的影响[[8](https://arxiv.org/html/2606.06744#bib.bib59), [10](https://arxiv.org/html/2606.06744#bib.bib98), [20](https://arxiv.org/html/2606.06744#bib.bib101)]，随后是雇主学习、人力资本积累、人员流动和昂贵的匹配后调整[[37](https://arxiv.org/html/2606.06744#bib.bib93), [14](https://arxiv.org/html/2606.06744#bib.bib95), [3](https://arxiv.org/html/2606.06744#bib.bib114), [27](https://arxiv.org/html/2606.06744#bib.bib43), [49](https://arxiv.org/html/2606.06744#bib.bib94), [55](https://arxiv.org/html/2606.06744#bib.bib96), [40](https://arxiv.org/html/2606.06744#bib.bib113), [54](https://arxiv.org/html/2606.06744#bib.bib60)]。近期关于稳定匹配的工作[[4](https://arxiv.org/html/2606.06744#bib.bib37), [2](https://arxiv.org/html/2606.06744#bib.bib123), [38](https://arxiv.org/html/2606.06744#bib.bib119), [7](https://arxiv.org/html/2606.06744#bib.bib122)]将筛选和信息视为揭示潜在偏好的互补匹配前信号，未能捕捉到信息可能在匹配开始后到达。Learn2Match填补了这一空白，并将上述机制转化为一个可控的多智能体学习环境。然而，这些模型是风格化的分析工具，在可处理性假设下隔离单一机制以解释聚合行为；它们不是智能体从互动中*学习*匹配策略的可控环境。Learn2Match填补了这一空白：一个根植于该文献的可模拟基准。尽管劳动力市场是我们的主要例子，但相同的结构特征——持久状态、昂贵的信息获取和匹配质量的逐步揭示——出现在约会、学校选择和基于平台的匹配中，该框架同样适用。

**动态匹配与多智能体强化学习（MARL）**。Min等人[[36](https://arxiv.org/html/2606.06744#bib.bib92)]率先开展了匹配市场中的RL理论研究。虽然他们的模型允许市场上下文跨轮次演变，但每一轮仍实现一个集中近视稳定匹配规划器，并为匹配对接收即时噪声效用反馈。我们的智能体则采用完全去中心化的决策范式，具有时间延展反馈。[[32](https://arxiv.org/html/2606.06744#bib.bib41)]研究马尔可夫交换经济中的福利最大化，[[51](https://arxiv.org/html/2606.06744#bib.bib62)]为双边市场中的离线策略评估开发了MARL框架。更广泛地说，现代MARL为去中心化部分可观察多智能体决策提供了工具[[33](https://arxiv.org/html/2606.06744#bib.bib28), [46](https://arxiv.org/html/2606.06744#bib.bib27), [59](https://arxiv.org/html/2606.06744#bib.bib13), [58](https://arxiv.org/html/2606.06744#bib.bib29), [50](https://arxiv.org/html/2606.06744#bib.bib30)]，并已被用于模拟市场规模的系统，例如