大约一个月前，马萨诸塞州的许多人开始保持社交距离，目前还看不到结束的迹象。如果你一个人住，也许你已经准备好了在你度过这段艰难时期后与某人配对。今天的嘉宾博客竹内俊二，为您提供了一个完美的算法。我喜欢这是由一个乍一看似乎不太技术或相关的问题激发出来的。但它确实如此！

内容

它始于一个脸书的帖子

有一天我遇到Facebook帖子在一个帮助人们应对社交距离的群体中，它开始了：

“一个需要解决的编码挑战和谜题!”最近，诺贝尔经济学奖(我的课题)授予了对匹配市场的研究，在匹配市场中，你不仅关心总体上的需求和供应，还关心谁得到什么。听起来是不是很熟悉?那是米隆加，对吧?”(a milonga是阿根廷探戈舞蹈项目)

这就是我如何了解稳定匹配问题（SMP）的原因。最初的海报希望人们应用SMP来解决为舞伴舞蹈匹配人的问题。这听起来很琐碎，但实际问题有许多相应的应用。

确实，100%保证找到SMP解决方案的算法赢了金宝搏官方网站2012年诺贝尔经济学奖获得者．

问题定义

给定两组同等规模的参与者，如医科学生和住院医生项目，并有他们的固定偏好，如:

S1 = {r1 r2 r3} r1 = {S1 s3 s2} s2 = {r3 r1 r2} r2 = {S1 s2 s3} s3 = {r1 r3 r2} r3 = {s3 S1 s2}

我们能找到稳定的匹配吗?在这种情况下，稳定性意味着:

一个解决方案可能是这样的:

(s1, r1)， (s2, r2)， (s3, r3)

它之所以稳定是因为:

那么保证生成SMP解的算法是什么呢?金宝搏官方网站

盖尔夏普利算法

这个非凡的算法叫做Gale-Shapley算法这是令人惊讶的直接。

的伪代码维基百科页面如下:

算法稳定匹配是初始化所有M∈M和W∈W来免费的而∃免费男人。M谁仍然有A.女人W来提出来做W：=第一个女人在m尚未向其提出建议的m的名单如果w是免费的然后(w m)订婚了其他的一些一对(m ', w)已经存在如果w喜欢M来m的那么m "变成免费的(w m)订婚了其他的(m ', w)依然存在订婚了终止如果终止如果重复

下面是来自维基百科页面的样本数据。有四个提议者和四个接受者。行表示提议者或接受者，具体取决于表，列表示排序后的首选项，其中数字是首选匹配项的索引。

prefProposers =(2, 1, 3, 4, 4, 1, 2, 3, 1、3、2、4、2、3、1、4]prefAcceptors =(1、3、2、4;3、4、1、2、4、2、3、1;3、2、1,4]wikiSolution =[1,1; 2、4、3、3、4、2];

预提议者=2 1 3 4 1 2 3 1 3 2 4 2 3 1 4预接受者=1 3 2 4 3 4 1 2 2 3 1 2 4

不幸的是，使用数字来遍历这个示例并不是很直观。为了避免出现cliché，我试着想出一个与性别无关的例子，但我想不出一个令人信服的例子。例如，Loren让我应用SMP来匹配人们最喜欢的食物，但我无法想象披萨或寿司会拒绝我(不确定我是否能处理好)。

这不是很有创意，但至少我可以在我们的小简·奥斯丁戏剧中扭转传统的性别角色，让女孩约男孩出去。

提案人=[“夏洛特”,“简”,“丽萃”,“莉迪亚”];受体= [“彬格莱先生”,“柯林斯”,“达西”,“韦翰”];

第一行prefProposers代表夏洛特的偏好，她的首选是2，即柯林斯。第二个是选择，或者叫彬格莱，等等。

precharlotte = preproposers (proposers ==“夏洛特”,:)

4 . n .诱惑，诱惑

伪代码按字面意思实现为函数galeShapley1(见功能部分)，它依次遍历请求者以找到它们的匹配。while循环中的例程在子函数中findMatch．

它使用向量匹配跟踪约定，最初都是零。行1到4映射到各自的提议者。如果所有元素都是0，那么您就知道所有的提议者都是免费的。

匹配=[0；0；0；0]

匹配= 0 0 0

当Charlotte向Collins求婚并被他接受时，第一个元素被替换为2，它映射到Collins。现在他们订婚了。我们继续这样下去，直到莉迪亚向柯林斯求婚，而柯林斯已经和夏洛特订婚了。

匹配=(2、4、1,0)

= 2 4 1 0

因为柯林斯更喜欢丽迪亚而不是夏绿蒂，他改变了主意，夏绿蒂变得自由了。我们知道这个是因为第一个元素是零。

匹配=[0；4；1；2]

1 . 1 = 0

现在我们想找到匹配夏洛特的人。既然她已经被她的第一个人选拒绝了，我们就去找她的第二个人选，彬格莱，他已经和丽萃订婚了。彬格莱更喜欢夏绿蒂。现在莉兹自由了。

匹配=[1；4；0；2]

2 .你的工作是什么

丽萃的第二选择是达西，达西自由了。现在他们订婚了。

匹配= (1,4;3;2)

= 1 4 3 2

现在所有人都参与了，算法终止了。

让我们运行MATLAB代码。

stableMatch1 = galeShapley1 (prefProposers prefAcceptors);

这就是结果。

namedMatch =字符串(大小(stableMatch1, 1), 1);namedMatch(: 1) =建议者';对于ii = 1:length(acceptors) namedMatch(stableMatch1(:，2) == ii,2) = acceptors(ii);终止命名匹配

namedMatch = 4×2 string array“Charlotte”“Bingley”“Jane”“Wickham”“Lizzy”“Darcy”“Lydia”“Collins”

这是数字上的结果，它与解决方案在GIF动画从维基百科页面。

doesMatch = isequal (wikiSolution stableMatch1)

doesMatch =逻辑1

改进的实现

我们知道顺序的方法不是很有效。在第一轮，还没有人被拒绝或匹配。接受人应该接受任何最初的建议。因此，在这一轮中，我们不必对每个提议者进行迭代。我们可以复制他们的第一个选项。

匹配=(2、4、1;2)

= 2 4 1 2

然后我们需要检查是否有任何接受方收到了多个提案，例如本例中的2 (Collins)，并对它们进行处理。

函数galeShapley2实现这个想法。从第二轮开始，我们用原来的套路。我们可以这样做，因为在Gale-Shapley算法中，执行顺序不会影响结果，如下面的输出所示。

[stableMatch2，分数]=galeShapley2（预提议者，预接受者）；

输出与前面的结果匹配。

doesMatch=isequal（stableMatch1，stableMatch2）

doesMatch =逻辑1

他们有多幸福?

具有galeShapley2，第二个返回变量分数显示参与者对比赛的满意程度。它包含了他们最后比赛的排名。第一列是提议者，第二列是接受者。

分数

分数= 2 1 1 2 2 3 1 2

我们可以把排名相加，看看谁做得更好。分数越小越好。

总分=总分（分数）

总分=6.8分

似乎提议者比接受者得到了更好的匹配。

扭转的角色

让我们看看如果我们交换提议者和接受者会发生什么。

[stableMatch3,分数]= galeShapley2 (prefAcceptors prefProposers);

这就是结果。你看到结果和以前不一样了。

stableMatch3

stableMatch3 = 1 1 2 3 3 4 4 2

这是比分。

分数

分数= 1 2 1 1 1 3 2 2

总分=总分（分数）

总分=5.8分

同样，那些提议的人比那些接受的人得到了更好的匹配。

模拟超过100次试验

在Gale-Shapley算法下，提议者通常比接受者做得更好。

让我们使用该函数随机生成一个数据集生成数据集并绘制出提议者和接受者的分数。你可以看到，提议者的分数通常低于接受者，因此他们得到了更好的匹配。

iter = 100;totalScores = 0 (iter, 2);对于ii = 1:iter [preproposers,prefAcceptors] = generateSMPdataset(4,4);[~， scores] = galeShapley2(preproposers, prefaceptors);totalScores (ii):) =总和(分数);终止图的阴谋(1:iter, totalScores (: 1))在阴谋(1:iter totalScores (:, 2))从包含(“试验”) ylabel (“分数-越低越好”)标题(Gale-Shapley算法-角色评分;“分数越低越好”])传奇(“提议”,“受体”,“地点”,“最好的”)

做提议者比做接受者好

天真地说，成为接受者看起来更好，因为他们可以说不，不必面对羞辱性的拒绝。但是，作为被拒绝的痛苦的交换，申请人得到了更好的选择，这导致了更好的结果。我们也知道，如果接受者通过撒谎来拒绝更多的喜好，那么他们就可以利用系统来迎合自己的喜好。

让这成为你人生的一课：开始并冒被拒绝的风险，因为这会给你更好的选择。

同样重要的是，当我们设计一个系统时，考虑谁将是提议者，这将影响到系统中谁受益最大。

这个系统不需要以这种方式建立，但它们就是这样，因为它们的设计是为了让一种类型的参与者受益于另一种。

回到最初的挑战

现在我们已经熟悉了SMP和Gale-Shapley算法的基本公式，让我们回到原始海报给我们的挑战。

在milonga(舞蹈活动)中，我们有4个追随者和4个领导者。

namesF = [“安娜”,“林”,“卡罗琳”,“多米尼克”];namesL = [“奥利弗”,“托马斯”,“亨利。”,“弗兰克”];

他们的排名如下：

prefF =[1、2、3、4、1、3、2、4、2、4、1、3、3、1、4、2]prefL =[4、3、2、1,3,4,1,2,2,3,4,1;3、1、4、2]

prefF = 1 2 3 4 1 3 2 4 2 4 1 3 3 1 4 2 prel = 4 3 2 1 3 4 1 2 2 3 4 1 3 1 4 2

谜题

编码的挑战

这是函数milongaMatch来迎接编码的挑战。我们唯一需要处理的新规定就是人们不能再和同一个人跳舞了。请注意，这个变体不再100%保证每个人都有一个舞伴(舞者，请注意)。当自由的求婚者找不到可求婚的对象时，求婚就停止了。

坦达斯=米隆加马奇（prefL，prefF，3）；

让我们为输出赋值名称。

解决方案=字符串（大小（tandas））；对于ii = 1:length(namesF) solution(tanda == ii) = namesF(ii);终止解决方案= array2table(解决方案,“RowNames”namesL,．..“变量名称”,“Tanda”+(1:尺寸(tandas, 2)))

解= 4×3 table Tanda1 Tanda2 Tanda3 ___________ ___________ ___________ Oliver "Dominique" "Brigitte" "Caroline" Thomas "Caroline" "Anna" "Brigitte" Henri "Brigitte" "Dominique" "Anna" " Frank "Anna" "Caroline" "Dominique"

这个谜题的答案

我对盖尔·夏普利的一个不满是，它要求两种类型的参与者人数相等。当涉及到社交舞蹈时，这种情况从未发生过——通常我们的追随者比领导者多。我想出了一个变种flexibleGS它可以处理申请人和接受人数量不相等的情况。试试吧!

prefProposers =(2, 1, 3, 4、5、4、1,2,3,5,1、3、2,4,5,2,3,4,5];prefAcceptors =(1、3、2、4;3、4、1、2、4、2、3、1;3、2、1,4,1、3、2,4];stableMatch4 = flexibleGS (prefProposers prefAcceptors);

总结

你喜欢谜题和编码挑战吗?你觉得SMP有趣吗?你能想出应用SMP的有趣例子吗?我还在想一个食物的例子。日本有些餐馆拒绝第一次来的顾客，除非陪同你的是一位能证明你的味蕾配得上他们的美食的常客。那是SMP吗?分享你有趣的SMP想法在这里．

功能

galeShapley1

函数匹配= galeShapley1 (prefP prefA)%将所有提案人和接受人初始化为自由匹配= 0(大小(prefP, 1), 1);提出= false(大小(prefP, 1));% while there is a free proser |p|…而任何(匹配= = 0)找到一个匹配|p|[匹配,提出]= findMatch (prefP prefA,匹配,提出);终止匹配=[(1:尺寸(prefP, 1))的匹配);终止

findMatch

函数[matched,proposed] = findMatch(prefP,prefA,matched,proposed) p = find(matched == 0,1); / /匹配的结果还有受体要求婚的人接受者=prefP（p，~建议的（p，：）；对于2 = 1:长度(受体)%| a |是| p |排名最高的此类接受者，而| p |尚未对其进行接受者%提出a=接受方（ii）；提议的（p，prefP（p，：）==a）=true；%如果|a|是空闲的如果~any（匹配==a）%（p，a）订婚匹配（p）=a；打破其他的%其他一些对（p'，a）已经存在P_ = find(match == a);[rank，~] = find(prefA(a，:) == [p;p_]); / /排序% if |a| prefer |p| to |p'|如果排名（1）<排名（2）% |p'|变为空闲匹配(p_) = 0;%（p，a）订婚匹配（p）=a；打破其他的% else (p'， a)保持占位终止终止终止终止

galeShapley2

函数[匹配，varargout] = galeShapley2(prefP,prefA)匹配= 0 (size(prefP,1)，1);提出= false(大小(prefP, 1));而任何(匹配= = 0)%处理第1轮如果if (prefP(:，1) = 0); if (prefP(:，1) = 0);提出(:1)= true;[受体,~,idx] =独特(匹配);A = acceptors(accumarray(idx,1) > 1);对于ii=1:length（a）p=find（ismember（matched，a（ii））；匹配（p）=0；[排名，~]=find（prefA（a（ii），：）=p）；[~，idx]=min（排名）；匹配（p（idx））=a（ii）；终止其他的%第2轮及以后[匹配,提出]= findMatch (prefP prefA,匹配,提出);终止终止匹配=[(1:尺寸(prefP, 1))的匹配);%对匹配结果打分分数=零（大小（匹配））；对于i = 1:size(match,1) p = match (Ii,1);一个=匹配(2,2);scores(p,1) = find(prefP(p，:) == a);scores(a,2) = find(prefA(a，:) == p);终止varargout{1} =分数;终止

生成数据集

函数[prefP,prefA] = generateSMPdataset(N,M) prefP = 0 (N,M);prefA = 0 (M, N);对于ii = 1:N prefP(ii，:) = randperm(M);终止对于ii = 1:M prefA(ii，:) = randperm(N);终止终止

milongaMatch

函数tandas = 0 (size(prel,1)，t); / / if (prel,1) = 0, if (prel,1) = 0);对于ii=1:t tanda=0（大小（prefL，1），1）；建议值=假（尺寸（prefL，1））；%确保没有人和以前的舞伴跳舞如果tandas(:，1:i -1);对于jj=1：建议的规模（prefL，1）（jj，：）=ismember（prefL（jj，：），prev（jj，：）；终止终止而任何(tanda == 0) [tanda，被提议的]= findMatch(prel,prefF,tanda，被提议的);如果免费的求婚者没有接受求婚的对象，就停止求婚如果所有(所有(提议(tanda = = 0:), 2))打破终止终止tandas(:,(二)= tanda;终止终止

flexibleGS

函数match = flexibleGS(prefP,prefA) N = size(prefP,1);M =大小(prefA, 1);如果N < M匹配= 0 (M,1);其他的匹配= 0 (N, 1);终止建议=假（N，M）；%而我们还有免费的申请人…而任何(匹配(1:N) = = 0)%查找匹配项[匹配,提出]= findMatch (prefP prefA,匹配,提出);但如果没有合适的对象可以求婚，就停止求婚。如果(所有(提议(匹配(1:N) = = 0,:), 2))打破终止终止如果N < M matched(matched == 0) = setdiff(1:M,matched); / / N < M匹配= [[(1:N); 0],匹配);其他的匹配=[(1:尺寸(prefP, 1))的匹配);终止终止

获取MATLAB代码

发布与MATLAB®R2020a