常用匹配算法

摘自：「百度百科」

经济学是研究资源最优配置问题的，而真实世界里配置资源的方式多种多样，市场或者说价格机制是经济学研究最多的。但是有一些市场里头，价格的作用受到法律、习俗或伦理道德等限制。最明显的例子就是找对象的时候不是价高者得，而是情投意合才结成夫妻。

匹配算法致力于解决经济学中「稀缺性资源」如何在不同用户之间进行「分配」的问题，从而到达理论上的「最优」。

案例入手

以下表格是一组婚介匹配数据，分为「男生偏好」和「女生偏好」。
表格标记了用户「从左至右」的偏好排名，其中「Φ」表示即使放弃也不愿匹配之后的用户。

贪心算法

摘自：「百度百科」

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

那么基于案例，贪心算法的求解流程如下：

• 第一轮 | 编号 | 男生偏好 | | | | | 结果 | 过程 | | —- | —- | —- | —- | —- | —- | —- | —- | | 1 | 6 | 7 | 5 | Φ | 8 | 成功 |
  | | 2 | 8 | 7 | 6 | 5 | Φ | 失败 | 8只有选择1 | | 3 | 7 | 6 | 5 | Φ | 8 | 成功 |
  | | 4 | 6 | 8 | Φ | 5 | 7 | 失败 | 6已被1选择 |

第一轮匹配「1-6」「3-7」匹配成功。

• 第二轮 | 编号 | 男生偏好 | | | | | 结果 | 过程 | | —- | —- | —- | —- | —- | —- | —- | —- | | 1 | 6 | 7 | 5 | Φ | 8 |
  |
  | | 2 | 8 | 7 | 6 | 5 | Φ | 成功 | 2只有选择5 | | 3 | 7 | 6 | 5 | Φ | 8 |
  |
  | | 4 | 6 | 8 | Φ | 5 | 7 | 失败 | 4放弃 |

第一轮匹配「2-5」匹配成功。

贪婪算法的最终匹配为：

沙普利算法

摘自：「百度百科」

沙普利算法简称「GS算法」或 「延迟接受算法」，是盖尔和沙普利为了寻找一个稳定匹配而设计出的市场机制。

那么基于案例，沙普利算法的求解流程如下：

• 第一轮 | 编号 | 男生偏好 | | | | | | —- | —- | —- | —- | —- | —- | | 1 | 6 | 7 | 5 | Φ | 8 | | 2 | 8 | 7 | 6 | 5 | Φ | | 3 | 7 | 6 | 5 | Φ | 8 | | 4 | 6 | 8 | Φ | 5 | 7 |

匹配结果：

• 第二轮 | 编号 | 男生偏好 | | | | | | —- | —- | —- | —- | —- | —- | | 1 | 6 | 7 | 5 | Φ | 8 | | 2 | 8 | 7 | 6 | 5 | Φ | | 3 | 7 | 6 | 5 | Φ | 8 | | 4 | 6 | 8 | Φ | 5 | 7 |

匹配结果：

• 第三轮 | 编号 | 男生偏好 | | | | | | —- | —- | —- | —- | —- | —- | | 1 | 6 | 7 | 5 | Φ | 8 | | 2 | 8 | 7 | 6 | 5 | Φ | | 3 | 7 | 6 | 5 | Φ | 8 | | 4 | 6 | 8 | Φ | 5 | 7 |

匹配结果：

• 第四轮 | 编号 | 男生偏好 | | | | | | —- | —- | —- | —- | —- | —- | | 1 | 6 | 7 | 5 | Φ | 8 | | 2 | 8 | 7 | 6 | 5 | Φ | | 3 | 7 | 6 | 5 | Φ | 8 | | 4 | 6 | 8 | Φ | 5 | 7 |

匹配结果：

• 揭示了什么？

贪心算法经过两轮高效匹配最终产生了三对情侣。但仔细观察会发现男生2相对于女生5「更喜欢」女生7，而另一方面女生7相对于男生3「更喜欢」男生2，因此算法中暗含了「不稳定」。而沙普利算法因为其「稳定匹配理论」和市场实践于2012年获得了诺贝尔经济学奖。沙普利算法的成功也揭示了两个有趣的定理：

• 表白者优势定理

由男生主动表白最后得到的稳定性匹配称之为「男性最优稳定匹配」，由女生主动表白得到的稳定匹配称之为「女性最优稳定性匹配」。从算法过程来看「主动表白」的一方能能够和喜欢的人在一起的「机会更高」。

• 单身不动点定理

从算法过程来看，无论哪一方「主动表白」形成的「稳定匹配结果」中「单身的依旧还是单身」。