用途
该技能用于实现 Gale-Shapley（延迟接受）稳定匹配算法，解决双边匹配问题。典型用途包括：根据双方偏好将候选人匹配到职位、将学生分配到学校、将住院医师分配到医院，以及任何需要满足稳定性（不存在阻塞对）的双边匹配场景。
主要能力
- 在两组规模相等的集合之间寻找稳定匹配，即不存在未匹配的双方都更偏好彼此而非当前匹配对象的情况。
- 最坏情况时间复杂度为 O(n²)。
- 具有“提议方最优”特性：提出匹配的一方获得其最优的稳定伴侣，被提议方则获得其最差的稳定伴侣。
- 包含四个阶段：输入校验、核心算法、稳定性验证、结果输出。
- 输出匹配结果及元数据，包括配对数、轮数、阻塞对数量和提议方。
使用方式
触发条件
- 根据双方偏好将候选人匹配到职位。
- 将学生分配到学校或将住院医师分配到医院。
- 任何需要稳定性（无阻塞对）的双边匹配。
不适用场景
- 单边分配（应使用匈牙利算法）。
- 偏好基于分数而非排序（应使用优化方法）。
算法流程
第一阶段：输入校验
收集双方的偏好排序。每位参与者对另一方的所有成员进行排序。要求：完整的偏好列表、规模相等的两组（或通过虚拟条目处理规模不等的情况）。
第二阶段：核心算法
- 所有提议方初始为“自由”（未匹配）状态。
- 当存在自由提议方且其尚未向所有人提议时：
- 自由提议方向其排名最高且尚未提议过的被提议方提出匹配。
- 被提议方若未匹配则接受；若已匹配但更偏好新提议方，则替换当前匹配。
- 被替换的提议方重新变为自由状态。
- 当所有提议方均匹配时终止。
第三阶段：验证
检查稳定性：对于每一对未匹配的 (a, b)，验证至少有一方更偏好其当前匹配对象。无阻塞对即为稳定。要求：发现零个阻塞对。
第四阶段：输出
返回匹配结果并确认稳定性。
输出格式
{
"matching": [{"proposer": "Candidate_A", "reviewer": "Company_X", "proposer_rank": 1, "reviewer_rank": 2}],
"metadata": {"pairs": 10, "rounds": 23, "blocking_pairs": 0, "proposer_side": "candidates"}
}
适用场景
- 求职招聘中的候选人与职位匹配。
- 教育领域的学校招生分配。
- 医疗领域的住院医师分配。
- 任何需要稳定性的双边匹配问题。
限制与注意事项
- 提议方优势：若候选人提议，其匹配结果优于公司提议的情况。这是具有公平性影响的设计选择。
- 偏好不完整：若参与者未对所有人排序，可能出现未匹配结果。可通过可接受伴侣阈值处理。
- 多对一匹配：医院-住院医师匹配使用多对一变体（每家医院有多个名额），需使用 Roth-Peranson 扩展。
- 策略操纵：被提议方可以通过误报偏好（截断列表）获益；提议方则不能，如实报告是提议方的占优策略。
- 偏好获取：在实践中获取诚实、完整的排序很困难，人们往往只做满意化选择而非完整排序。
- 边界情况：所有人偏好相同的第一名时算法仍会终止且稳定；偏好完全相同时存在唯一稳定匹配；双方规模不等时较大一方会有未匹配者，可通过虚拟条目或多对一变体处理。
参考资料
- 多对一匹配（医院-住院医师）：见 references/many-to-one.md
- 策略行为分析：见 references/strategic-manipulation.md