如何为玩家匹配到合适的队友/对手类型——稳定婚姻问题介绍

作者：clatterrr 博客“露出你的犬牙” 2019-10-11

简介：

稳定婚姻问题（stable marriage problem）通俗的表述是这样的：假如我们要促成n位男生和n位女生的婚姻，每个人对每个异性都有一个排序，代表对他们的好感度。那么稳定婚姻方案（Stable Matching）指的是，当我们已经安排好n对配偶后，不存在不是配偶的一男一女，他们对各自的好感度都大于自己的配偶。接下来将介绍稳定婚姻问题在游戏中的应用。如果你对稳定婚姻问题感兴趣，不妨看看《数学里的爱情观---稳定婚姻问题》一文。

玩家分类

例如一款双人合作游戏，里面有种模式叫做大佬带小白，即让一名技术熟练的玩家带领一位新手合作闯关。为了简化问题，就把所有玩家按照游戏类型分为速通型，收集型，潜伏型，社交型。

不同类型的玩家会想要不同类型的对手。例如速通型的大佬不愿意带收集型的小白，而社交型的小白更希望遇上社交型的大佬。让每个类型的玩家对希望遇上的玩家类型排序，得出下面一份表格：


假如游戏中有8名玩家希望匹配，每个玩家正好是一种不同的类型，那么我们尝试为它们匹配时，如果得到的部分方案是下面这样

（收集大佬，速通小白），(速通大佬，收集小白)

按照之前表格中的排序，收集大佬显然比起乱动机关的速通小白，更喜欢与收集小白合作一些。收集小白比起不怎么探索游戏隐藏内容的速通大佬来说，更希望和收集大佬一起游玩。收集大佬与收集小白都更希望匹配到对方，而不是和目前的队友一起。这个方案显然是不稳定的。

Gale-Shapley算法

稳定婚姻问题最初起源于美国医学院的学生毕业时如何分配工作的问题，算法在1962年的时候由Gale和Shapley给出，根据他们的算法，任何一个稳定婚姻问题都有解的，也就说总有至少一个方案是稳定的。详细过程为：

每一轮中，每个尚未的匹配的大佬在他还没有尝试匹配过的小白中选择自己最希望的一个，递出邀请函。

然后这个小白在所有给自己递出邀请函的大佬中选择自己最希望的那个，并拒绝其他人，并暂时匹配在一起。注意这儿递出邀请函的大佬也包括暂时和自己匹配在一起的。所以小白可能把暂时和自己匹配在一起的大佬踢开，并接受自己更想要的结果。

如果所有的大佬和小白都匹配好了，就让他们开始游戏吧！

在本文的例子里，这个算法看起来是这样的。首先速通大佬向速通小白发出了友善的消息，速通小白接受，他们暂时匹配在一起。

收集大佬和收集小白也这样暂时匹配在一起，但潜伏大佬也向收集小白递出了邀请函，在收集小白眼里，潜伏大佬更加能让自己知道怎么把一款游戏玩成另一款游戏，于是接受了潜伏大佬的邀请，暂时匹配在一起。让收集大佬一边凉快去了。

之后是社交大佬和社交小白也暂时匹配在了一起。这时候匹配结果为：

（速通大佬，速通小白），（潜伏大佬，收集小白），（社交大佬，社交小白）

收集大佬还没有匹配到队友，但自己最想要的收集小白并不愿意和自己在一起。于是向自己第二想一起玩的速通小白递出了橄榄枝。速通小白虽然已经和速通大佬暂时匹配在一起了，但速通小白内心更加愿意让收集大佬带自己找游戏菜单，解锁成就的，于是愉快的接受了收集大佬，让速通大佬又变成孤零零的。

（收集大佬，速通小白），（潜伏大佬，收集小白），（社交大佬，社交小白）

速通大佬也没有匹配到自己最希望的玩家，只好向自己的第二希望潜伏小白，表达了一起玩的愿望。一直没人理的潜伏小白也只好接受，最后一次匹配也完成。最终的匹配结果是：

（速通大佬，潜伏小白），（潜伏大佬，收集小白），

（收集大佬，速通小白），（社交大佬，社交小白）

接下来，他们就准备好耳机和肥宅快乐水，随时大干一场了！

证明

不过，这种方法能确保每个人都匹配队友，而不会出现永远等待中的情况嘛？不会的。每个小白一旦暂时匹配上大佬，就一直会有某位大佬暂时匹配着他，因此如果有小白一直没有找不到队友，那是因为还从来没有大佬向他表达过愿意一起玩的愿望。但这是不可能的，如果有位大佬一直找不到队友，那么在结束游戏之前一定会向所有小白发出邀请函。

那么怎么保证这个方案是稳定且唯一呢，不至于让玩家互相为了更心仪的队友而退出当前游戏呢？考虑任意大佬A和小白a，假设最后A和b匹配在一起，a和B匹配在一起,是否有可能A相较于b更喜欢a，而a把A和B比较更想要和前者在一起玩？如果A更喜欢a，那么算法过程中，肯定已经向a发出过邀请函了，而且a拒绝了A。但a拒绝A之后，是不可能选择自己更不想要的B的。

如果改变算法的顺序，例如我们不从速通大佬开始，而是从其它大佬开始，所得到的结果是一样的。如果改变了顺序就出现了不一样的结果，那么这就和这个方案是稳定且唯一的说法矛盾了。

但这种方法也有一点残酷的地方。主动发出邀请函的是大佬，接受邀请函的是小白，所以所有大佬都能匹配到自己可能的最希望的小白，而小白却相反——只能匹配给自己有可能的最差的，最不希望的大佬。因为大佬按照自己喜欢的顺序邀请，如果自己不能和自己更想要的小白匹配在一起，那么能确保那位小白在收到自己邀请函后已经明确拒绝了自己。而小白是被动的，不能保证自己希望一起玩的大佬向自己发出过邀请，因为大佬是被排在自己之前的小白拒绝后才来找自己的。这个证明并不严密，但也足可窥见一斑。

问题变种

还有与许多婚姻问题相似的问题。这里仅简单介绍。

不完全名单

例如某些玩家只想和某一类型的玩家匹配在一起，否则干脆不玩。而某些玩家不会对所有类型的玩家都排个序，只考虑了自己想要一起玩的前几种玩家。这时候，我们需要一位虚拟出的大佬和一位虚拟的小白帮助他们匹配。

弱序名单

如果有的玩家，觉得某种类型玩家和另一种类型玩家差不多，匹配给谁都无所谓。我们则需要修改稳定方案的定义，才能保证稳定方案存在。

稳定医院

如果这是个多人合作问题，每个小白和可以和多个大佬合作。也有与稳定婚姻类似的算法来解决。但这个时候稳定方案不唯一，算法的顺序可能导致结果不同，例如从大佬A开始安排起，和从大佬B开始安排起可能导致不同的结果。

稳定室友

假如我们取消掉大佬和小白的区分，让任意玩家都能匹配在一起的话，就不能保证有稳定方案的存在了。

结语

嗯，该算法的发明者Gale和Shapley是一对夫妇，他们最后就如他们提出的算法那样，在一起幸福地白头偕老了。

参考

数学里的爱情观---稳定婚姻问题
刘汝佳，陈峰《算法竞赛入门经典训练指南》
stable marriage wiki
稳定医院算法动画演示HOW THE MATCHING ALGORITHM WORKS

作者：clatterrr
来源：博客“露出你的犬牙”
地址：https://clatterrr.com/archives/1724

参与评论