获得诺奖的稳定匹配理论之TTC算法与GS算法

获得诺奖的稳定匹配理论之TTC算法与GS算法

267 2021-03-12 20:07:41

# 引言

在生活和工作中经常会遇到一些需要资源分配的时候，例如

1. 公司发的礼物不喜欢，想跟其他人换
2. 在线扭蛋机的交换系统实现
3. 求职offer的选择
4. 高考投档系统实现

其中1、2属于单边匹配，匹配由单边期望决定，即“买方”决定；3、4属于双边匹配问题，匹配过程需考虑“买卖双方”的期望。

在通常情况下，我们期望获得一个尽可能合理而稳定的分配结果，使得最终整体收益最大化。

罗伊德-沙普利（Lloyd S. Shapley）与他人提出了一系列市场的稳定配置机制，为博弈论和经济学领域做出了巨大的贡献，最终与艾尔文-罗斯（Alvin E. Roth）一同获得2012年获诺贝尔经济学奖。

# 背景

之前写过在业务中遇到了判定业务，而该判定业务实际上是一组给定对象与另一组给定对象的匹配问题：

- 集合`(a, b, c, d)`与集合`(A, B, C, D, E)`的匹配问题，最终得到的结果是多组一对一关系
- 在匹配过程中，有可能出现匹配错误导致的多对一匹配结果
- 为解决匹配冲突，需要对匹配结果进行调整，做到“尽可能让每个对象都满意”，即达到局部最优，资源分配合理的状态

在调整匹配的过程为达到资源分配的稳定性考虑了结果的优先级排序。当时并不清楚这样做是否能达到最优效果，在无意间了解到资源分配的“强核配置”这一概念后，发现自行实现的分配算法逻辑与博弈中的GS算法相同。确认该方式可以做到资源分配稳定的同时，也了解到适用于其他分配场景的实用算法，在此希望能通俗易懂地介绍给大家。

**强核配置**

> 强核配置即满足个体合理性的同时满足帕累托最优状态。
> 强核配置在匹配中不仅是存在的，而且是唯一的，具有抗策略性，即私下交易或说谎都不会使得结果变得比强核配置的结果更好。

**帕累托最优**

> 帕累托最优（Pareto Optimality），也称为帕累托效率（Pareto Efficiency），是指资源分配的一种理想状态，假定固有的一群人和可分配的资源，从一种分配状态到另一种状态的变化中，在没有使任何人境况变坏的前提下，使得至少一个人变得更好，这就是帕累托改进或帕累托最优化。
帕累托最优状态就是不可能再有更多的帕累托改进的余地；换句话说，帕累托改进是达到帕累托最优的路径和方法。
>
> ——百度百科

# 算法介绍

## Top Trading Cycle Algorithm

首位交易循环算法算法，在1974年提出，下称TTC算法。

适用于“分配”或“交易”场景，即单边匹配问题。

### 问题引入

一些公司在节日时给员工发不同颜色的礼品，员工在抽到奖品后对颜色不满意，希望跟其他人交换更喜欢颜色的奖品。

对于员工而言，喜欢的颜色不尽相同，或许与其他人交换之后能获得各方更满意的结果。

### 问题定义

简单起见，我们把问题简化，定义一些限制条件：

1. 给定员工集合E=e1, e2, e3, e4
2. 给定员工对应的礼物G=《e1, g1》, 《e2, g2》, 《e3, g3》, 《e4, g4》
3. 参与的各方都满意才能交换
4. 可以不与他人交换

### TTC算法步骤

1. 每位员工对每个礼物的满意程度排序
2. 员工提出当前最满意的礼物，将员工与期望礼物间建立一条边，同时将礼物与其主人间建立一条边
3. 寻找建立的边是否形成了循环，允许自循环，可能有多个循环
4. 循环中的员工交换礼物，停止参与交换
5. 剩余员工将循环中的名单从表中去除，继续提出当前最满意的礼物，迭代寻找循环
6. 交换全部完成，结束

### 案例演示

![](/img/pic/2021031220093895009_png_1554_600_173348)
> 根据满意程度组成的表格，按满意度从高（左）到低（右）排序，以及建立的有向图

![](/img/pic/2021031220095882510_png_1546_578_209218)
> 《e1, g3》与《e3, g1》形成了循环，达成交易并离场

![](/img/pic/2021031220110624411_png_1540_566_182905)
> 《e2, g4》与《e4, g2》形成了循环，达成交易并离场，所有交易都已完成

**算法的核心思想：根据当前优先级顺序形成交换循环，意见达成一致的员工与礼物优先交换并离场，剩下的员工从满意度表中去除已离场礼物后继续尝试形成交换循环。**

### 问题解决

TTC有一些特点：

1. 每次迭代一定存在循环，即使是自循环
2. 多个循环之间一定不会出现相交，因为每个节点只有一条出边
3. 能换到的礼物一定不比已有的差，因为最差情况下会形成自循环而离场

尽管我们平常交换公司礼物的方式也是使用TTC算法，但通常来说却少足够的候选交易池和一定的规则，最终的结果不一定能达到最优。

### 补充

TTC算法可以获得强核配置，强核配置具有抗策略性，说谎或私下交易都不会让结果变得更好。

做个不严谨的简单证明：

1. 第一轮交易成功的员工们，说谎或私下交易只会让结果更坏，毕竟已经获得最好结果了
2. 第二轮交易成功的员工，无论自身的满意度排序如何也无法改变一轮交易成功的循环，因此不可能变得更好；私下交易也会损害全局利益
3. 类推第三轮等

## Gale-Shaply Algorithm

盖尔-沙普利算法，又称Deffered Acceptance Algorithm，延迟接受算法，在1962年提出，下称GS算法或延迟接受算法。

适用于“配对”场景（并非必须一对一），即双边匹配问题。

### 问题引入

求职是一个双向选择的过程，需要公司认可求职者并下发offer之后，求职者基于手中的offer对比，并做出接受或拒绝的判断。
对于求职者而言，offer明显需要基于多重考量后选取最优的结果；对于公司而言，职位是有限的，因此招到的员工在公司能力评估排序中越靠前越好。
双方都希望从这个匹配中达到最大化收益，那么怎样的发/接offer策略会达到整体收益最大化即帕累托最优呢？

### 问题定义

同样简单起见，定义一些限制条件：

1. 给定公司集合C=c1, c2, c3, c4
2. 给定求职者集合E=e1, e2, e3, e4，对C中每个公司都提出求职申请
3. 每个公司只录取一名求职者，每个求职者只接受一个offer

### GS算法步骤

1. 每个公司为每名求职者进行满意度排序，求职者对每个公司的offer进行满意度排序
2. 每家公司优先给排序靠前的求职者发offer，如果被拒绝则继续给下一位发offer
3. 求职者在收到offer后并不马上决定，而是等待收到其他offer后进行对比，仅保留最满意的offer，回绝其他offer
4. 计算过程为：C方发一轮offer->E方决策->C方发一轮offer->E方决策......
5. 当所有决定不再变动时，分配结束，求职者接受手中offer

### 案例演示

![](/img/pic/2021031220090180608_png_1544_592_175849)
> C方与E方满意度排序组成的表格以及第一轮offer发放情况，其中 n, m 表示公司对求职者的排位（左）及求职者对公司的排位（右）

![](/img/pic/2021031220120706212_png_1542_584_185892)
> e1获得了2个offer并通过比较拒绝了c2的offer

![](/img/pic/2021031220121701113_png_1540_578_179677)
> c2给下一候选人e4发offer，e4通过比较拒绝了c4的offer

![](/img/pic/2021031220122572914_png_1544_586_199403)
> c4给下一候选人e2发offer，e2通过比较拒绝了c3的offer

![](/img/pic/2021031220124162615_png_1544_582_194783)
> c3给下一候选人e1发offer，e1通过比较拒绝了c1的offer

![](/img/pic/2021031220125106516_png_1550_588_209254)
> c1给下一候选人e2发offer，e2通过比较拒绝了c1的offer

![](/img/pic/2021031220130391117_png_1550_596_194095)
> c1给下一候选人e3发offer，此时匹配达到稳定状态

达到稳定状态后，资源得到最大化利用。

**算法的核心思想：主动方（C方）按照优先级申请匹配，而被动方（E方）根据优先级进行比较，只保留最合适的匹配申请最后统一决定，最终达到稳定匹配，因此被称为“延迟接受”。**

### 问题解决

GS算法被证明不会无限循环执行，最终状态会达到稳定的匹配状态。这一点比较好理解，毕竟任何公司发offer的对象不会重复且在排序表上越来越靠后，最差情况下需执行n^2次，其他一些证明在[参考文献](https://xjdkc.github.io/Stable%20Matching-%E7%A8%B3%E5%AE%9A%E5%8C%B9%E9%85%8D%E9%97%AE%E9%A2%98.html)中有提到。

当然，实际情况下受到岗位数量、offer期限、发offer时间等的影响问题会变得复杂很多，但核心还是保持不变的。

仔细想想，我们在实际发/接offer时不也几乎都是这样决策的吗？这说明在长期的劳资双方博弈下延迟接受算法确实是一种实现各方利益最大化的良好选择，也经受住了市场的考验。

在最理想的状态下，所有C方统一发offer，E方统一接受/拒绝，可以达到整体利益的最大化。但对于竞争力弱的主动方公司来说，自身需求可能得不到较好的满足，因此出现offer决策时间短（不允许延迟决策的情况可以参考[秘书问题](https://baike.baidu.com/item/%E7%A7%98%E4%B9%A6%E9%97%AE%E9%A2%98/9444825)）、提前发offer抢人等操作，导致整体资源分配不稳定不合理，甚至产生恶性竞争。

### 补充

有趣的是，对于上文给出的案例数据，会发现各位求职者拿到的都不是最满意的那个offer，各公司招到的员工也不是最满意的那个，比如最优秀的e1求职者和c4公司。这也没办法，谁让你在最心仪的公司/员工面前表现那么差（末位）呢？这说明也许匹配的过程中双方看对眼或许比自身条件还重要。（同样适用于找对象场景）

在如下场景中，由C方主动发起匹配和由E方主动发起匹配最终GS算法的结果是不一样的。由C发起的稳定匹配对于C而言结果更好；而由E发起的则完全相反。所以，尽量在这样的匹配场景中掌握主动权，或许会给自己带来更好的结果。（这条在找对象场景也适用，hhh）

![](/img/pic/2021031220142416918_png_574_324_24463)

GS算法对于主动方具有抗策略性。

# 总结

稳定匹配理论在不增减资源的前提下，仅仅对现有资源进行重新排列组合，就能使各方都达到相对满意状态，整体达到最优。在升学志愿、学校分配、捐献器官交换、岗位分配等领域，这些理论思想都有得到广泛应用，在匹配问题也比较常见的计算机领域应该也有不少应用场景。

# 参考资料

[SF2972: Game theory - www.kth.se](https://www.math.kth.se/matstat/gru/sf2972/2013/matchingslides.pdf)

[盖尔-沙普利算法 - 百度百科](https://baike.baidu.com/item/%E7%9B%96%E5%B0%94-%E6%B2%99%E6%99%AE%E5%88%A9%E7%AE%97%E6%B3%95)

[双边匹配理论及其应用研究新进展\[张卫东，黄春华\]pdf下载](https://ctti.nju.edu.cn/CTTI/attachmentInfo/download.do?attachmentId=5307)

[Stable Matching-稳定匹配问题 - 橡胶大口吃のBlog](https://xjdkc.github.io/Stable%20Matching-%E7%A8%B3%E5%AE%9A%E5%8C%B9%E9%85%8D%E9%97%AE%E9%A2%98.html)