algo-hr-matching

Compare original and translation side by side

🇺🇸

Original

English

🇨🇳

Translation

Chinese

Gale-Shapley Stable Matching

Gale-Shapley稳定匹配

Overview

概述

Gale-Shapley (deferred acceptance) finds a stable matching between two equally-sized sets where no unmatched pair prefers each other over their current match. Runs in O(n²) worst case. Proposer-optimal: the proposing side gets their best stable partner.

Gale-Shapley（延迟接受算法）可在两个规模相等的集合间找到稳定匹配，即不存在未匹配的配对双方都更偏好彼此而非当前匹配对象的情况。最坏情况下时间复杂度为O(n²)。该算法对提议方最优：提议方会获得其最优的稳定匹配对象。

When to Use

适用场景

Trigger conditions:

Matching candidates to job positions based on mutual preferences
Assigning students to schools or residents to hospitals
Any two-sided matching where stability (no blocking pairs) is required

When NOT to use:

For one-sided assignment (use Hungarian algorithm)
When preferences are based on scores, not rankings (use optimization)

触发条件：

根据双方偏好将候选人与工作职位匹配
分配学生到学校或住院医师到医院
任何需要稳定性（无阻塞配对）的双边匹配场景

不适用场景：

单边分配问题（请使用Hungarian algorithm）
偏好基于分数而非排名的场景（请使用优化算法）

Algorithm

算法说明

IRON LAW: The Proposing Side Gets Their BEST Stable Partner
Gale-Shapley is proposer-optimal and reviewer-pessimal. If employers
propose, they get their best stable match; candidates get their worst.
The CHOICE of who proposes determines which stable matching is found.

IRON LAW: The Proposing Side Gets Their BEST Stable Partner
Gale-Shapley is proposer-optimal and reviewer-pessimal. If employers
propose, they get their best stable match; candidates get their worst.
The CHOICE of who proposes determines which stable matching is found.

Phase 1: Input Validation

阶段1：输入验证

Collect: preference rankings from both sides. Each participant ranks all members of the other side. Gate: Complete preference lists, equal-sized groups (or handle unequal with dummy entries).

收集双方的偏好排名。每个参与者需对另一集合的所有成员进行排名。 校验要求： 完整的偏好列表、规模相等的两组（若规模不等，可添加虚拟条目处理）。

Phase 2: Core Algorithm

阶段2：核心算法

All proposers are "free" (unmatched)
While any proposer is free and hasn't proposed to everyone:
- Free proposer proposes to their highest-ranked unproposed-to reviewer
- Reviewer accepts if unmatched, or replaces current match if new proposer is preferred
- Replaced proposer becomes free again
Terminate when all proposers are matched

所有提议方初始状态为“未匹配”
当存在未匹配且未向所有对象提议过的提议方时：
- 未匹配的提议方向其排名最高且未提议过的被提议方发起匹配请求
- 被提议方若未匹配则接受请求；若已匹配，若新提议方排名高于当前匹配对象，则替换当前匹配，原匹配对象变为未匹配
- 被替换的提议方重新变为未匹配状态
当所有提议方均已匹配时，算法终止

Phase 3: Verification

阶段3：稳定性验证

Check stability: for every unmatched pair (a,b), verify that at least one of them prefers their current match over the other. No blocking pairs = stable. Gate: Zero blocking pairs found.

检查稳定性：对于每一对未匹配的组合(a,b)，验证至少其中一方更偏好当前匹配对象而非对方。无阻塞配对则说明匹配稳定。 校验要求： 未发现任何阻塞配对。

Phase 4: Output

阶段4：输出结果

Return matching with stability confirmation.

返回带有稳定性确认信息的匹配结果。

Output Format

输出格式

json

{
  "matching": [{"proposer": "Candidate_A", "reviewer": "Company_X", "proposer_rank": 1, "reviewer_rank": 2}],
  "metadata": {"pairs": 10, "rounds": 23, "blocking_pairs": 0, "proposer_side": "candidates"}
}

json

{
  "matching": [{"proposer": "Candidate_A", "reviewer": "Company_X", "proposer_rank": 1, "reviewer_rank": 2}],
  "metadata": {"pairs": 10, "rounds": 23, "blocking_pairs": 0, "proposer_side": "candidates"}
}

Examples

示例

Sample I/O

输入输出示例

Input: 3 candidates, 3 companies, each with full preference rankings Expected: Stable matching with zero blocking pairs. Candidate-proposing gives candidate-optimal result.

输入： 3名候选人、3家公司，双方均提供完整的偏好排名 预期结果： 无阻塞配对的稳定匹配。若由候选人作为提议方，将得到对候选人最优的匹配结果。

Edge Cases

边缘情况

Input	Expected	Why
All prefer same #1	Still terminates, stable	Rejected proposers move to next choice
Identical preferences	Unique stable matching	Only one possibility
Unequal sides	Some unmatched on larger side	Add dummy entries or use many-to-one variant

输入	预期结果	原因
所有参与者都偏好同一排名第1的对象	算法仍会终止并得到稳定匹配	被拒绝的提议方会转向下一个选择
双方偏好完全一致	唯一的稳定匹配	仅存在一种可能的匹配结果
两组规模不等	规模较大的组中部分成员无法匹配	添加虚拟条目或使用多对一变体算法

Gotchas

注意事项

Proposer advantage: If candidates propose, they get better matches than if companies propose. This is a design choice with equity implications.
Incomplete preferences: If participants don't rank everyone, unmatched results are possible. Handle with acceptable-partner thresholds.
Many-to-one: Hospital-resident matching uses the many-to-one variant (each hospital has multiple slots). Use the Roth-Peranson extension.
Strategic manipulation: The reviewing side CAN benefit from misreporting preferences (truncating lists). The proposing side cannot — truthful reporting is dominant strategy for proposers.
Preference elicitation: Getting honest, complete rankings is hard in practice. People satisfice rather than fully rank all options.

提议方优势：若由候选人作为提议方，他们得到的匹配结果会比由公司作为提议方时更好。这是一个带有公平性影响的设计选择。
不完整偏好：若参与者未对所有对象排名，可能会出现未匹配的结果。可通过设置可接受对象阈值来处理。
多对一匹配：医院-住院医师匹配使用多对一变体算法（每家医院有多个名额）。请使用Roth-Peranson扩展算法。
策略性操纵：被提议方可通过误报偏好（截断排名列表）获益。而提议方无法通过该方式获益——如实报告偏好是提议方的占优策略。
偏好收集：在实际场景中，获取真实、完整的排名难度较大。人们通常会选择满意选项而非对所有选项进行完整排名。

References

参考资料

For many-to-one matching (hospital-resident), see
```
references/many-to-one.md
```
For strategic behavior analysis, see
```
references/strategic-manipulation.md
```

有关多对一匹配（医院-住院医师），请参阅
```
references/many-to-one.md
```
有关策略性行为分析，请参阅
```
references/strategic-manipulation.md
```