马萨诸塞州的许多人大约一个月前开始保持社交距离，目前还看不到结束的迹象。如果你一个人住，也许你准备好了在你度过难关后和某人配对。今天的嘉宾博主，古原竹内，为你提供了完美的算法。我喜欢这个灵感来自一个问题，乍一看，似乎不是很专业或相关。但它是!

内容

事情始于Facebook上的一个帖子

有一天我偶然发现Facebook上的帖子其中一个组织涌现出来，帮助人们应对社交距离。它开始:

“一个编码挑战和一个谜题需要解决!诺贝尔经济学奖(我的课题)最近颁发给了在匹配市场方面的研究，在这种研究中，你不仅关心一般的需求和供应，而且确切地关心谁得到什么。听起来是不是很熟悉?那是米隆加，对吧?”(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算法

这个非凡的算法叫做Gale-Shapley算法而且它出人意料地简单。

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

算法stable_matching是初始化所有米∈米而且w∈W来免费的而∃免费男人。米谁仍然有一个女人w来提出来做w：=第一个女人在M尚未求婚对象的名单如果w是免费的然后(m, w)变成订婚了其他的一些一对(m ', w)已经存在如果w喜欢米来m的那么m "变成免费的(m, w)变成订婚了其他的(m'， w)保留订婚了结束如果结束如果重复

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

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];

prefProposers = 2 1 3 4 4 1 2 3 1 3 2 4 2 3 1 4 4 1 2 4 2 3 1 3 2 1 4

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

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

提议者= [“夏洛特”，“简”，“丽萃”，“莉迪亚”];Acceptors = [“彬格莱先生”，“柯林斯”，“达西”，“韦翰”];

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

prefCharlotte = prefProposers(提议者==“夏洛特”:)

prefCharlotte = 2 1 3 4

伪代码按字面意思实现为函数galeShapley1(见功能节)，它会依次遍历提议者以找到匹配的提议者。while循环中的例程位于子函数中findMatch．

它使用矢量匹配用来记录任务，一开始都是零。第1至4行映射到各自的提议者。如果所有元素都为0，则所有提议者都是自由的。

匹配= [0;0;0;0]

匹配= 0 0 0 0 0

当Charlotte向Collins求婚并且Collins接受时，第一个元素被替换为2，它映射到Collins。现在他们订婚了。直到Lydia向Collins求婚，而Collins已经和Charlotte订婚了。

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

匹配= 2 4 1 0

因为柯林斯更喜欢莉迪亚而不是夏洛特，所以他换了，夏洛特就自由了。因为第一个元素是0。

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

匹配= 0 4 1 2

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

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

匹配= 1 4 0 2

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

匹配= [1;4;3;2]

匹配= 1 4 3 2

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

让我们运行MATLAB代码。

stableMatch1 = galeShapley1(prefProposers,prefAcceptors);

这就是结果。

namedMatch = string (size(stableMatch1,1)，1);namedMatch(:，1) =提议者';为ii = 1:length(acceptors) namedMatch(stableMatch1(:，2) == ii,2) = acceptors(ii);结束namedMatch

namedMatch = 4×2字符串数组"Charlotte" "彬格莱" "Jane" "Wickham" "Lizzy" "Darcy" "Lydia" "Collins"

这是数字的结果，匹配到GIF动画中的解决方案来自维基百科页面。

doesMatch = isequal(wikiSolution,stableMatch1)

doesMatch = logical 1

改进的实现

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

匹配= [2;4;1;2]

匹配= 2 4 1

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

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

[stableMatch2,scores] = galeShapley2(prefProposers,prefAcceptors);

输出与前面的结果匹配。

doesMatch = isequal(stableMatch1,stableMatch2)

doesMatch = logical 1

他们有多快乐?

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

分数

分数= 2 1 1 2 2 3 1 2

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

totalScores = sum(scores)

totalScores = 6

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

角色互换

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

[stableMatch3,scores] = galeShapley2(prefAcceptors,prefProposers);

这就是结果。你会发现结果和以前不一样了。

stableMatch3

stableMatch3 = 1 1 2 3 3 4 4

这是分数。

分数

分数= 1 2 1 1 1 3 2 2

totalScores = sum(scores)

totalScores = 5

同样，求婚的人比接受的人得到了更好的匹配。

超过100次试验的模拟

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

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

Iter = 100;totalScores = 0 (iter,2);为ii = 1:iter [prefProposers,prefAcceptors] = generateSMPdataset(4,4);[~， scores] = galeShapley2(prefProposers,prefAcceptors);totalScores(ii，:) = sum(scores);结束图绘图(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 2 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

这个难题

编码挑战

这是函数milongaMatch为了迎接编码的挑战。我们唯一需要处理的新规则是，人们不允许再和同一个人跳舞。请注意，这个变种不再100%保证每个人都有一个搭档(舞者，注意)。当自由提议者找不到接受提议的对象时，它就会停止。

tandas = milongmatch (prefL,prefF,3);

让我们为输出分配名称。

解决方案=字符串(大小(tandas));为ii = 1:长度(namesF)解(tandas == ii) = namesF(ii);结束解= array2table(解，“RowNames”namesL,.．.“VariableNames”，“Tanda”+(1:尺寸(tandas, 2)))

解决方案= 4×3 table Tanda1 Tanda2 Tanda3 ___________ ___________ ___________奥利弗“多米尼克”“布丽吉特”“卡罗琳”托马斯“卡罗琳”“安娜”“布丽吉特”“亨利”“布丽吉特”“多米尼克”“安娜”弗兰克“安娜”“安娜”“卡罗琳”“多米尼克”

谜题的答案

我对Gale-Shapley的一个抱怨是，它要求两种类型的参与者人数相等。说到交际舞，这从来没有发生过——通常我们的追随者比领导者多。我想出了一个变种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 = flexblegs (prefProposers,prefAcceptors);

总结

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

功能

galeShapley1

函数match = galeShapley1(prefP,prefA)初始化所有提议者和接受者以释放匹配= 0 (size(prefP,1)，1);proposal = false(size(prefP,1));%当存在一个自由提议者|p|…而Any (matched == 0)找到一个匹配|p|[matched,proposed] = findMatch(prefP,prefA,matched,proposed);结束matched = [(1:size(prefP,1))'，matched];结束

findMatch

函数[matched,proposed] = findMatch(prefP,prefA,matched,proposed) p = find(matched == 0,1);% |p|的人仍然有接受者可以求婚acceptors = prefP(p，~ proposal (p，:));为Ii = 1:长度(受体)% |a|是|p|的最高级别的受体，|p|还没有%提出A =受体(ii);proposal (p,prefP(p，:) == a) = true;% if |a|是空闲的如果~any(matched == a)% (p, a)参与匹配(p) = a;打破其他的%否则某个对(p'， a)已经存在P_ = find(matched == a);[ranking，~] = find(prefA(a，:) == [p;p_]);%如果|a|喜欢|p|而不是|p'|如果Ranking (1) < Ranking (2)% |p'|变为空闲匹配(p_) = 0;% (p, a)参与匹配(p) = a;打破其他的% else (p'， a)保持参与结束结束结束结束

galeShapley2

函数[matched,varargout] = galeShapley2(prefP,prefA) matched = 0 (size(prefP,1)，1);proposal = false(size(prefP,1));而Any (matched == 0)处理第1轮如果all(matched == 0) matched = prefP(:，1);proposal (:，1) = true;[acceptors，~，idx] = unique(matched);A = acceptors(accumarray(idx,1) > 1);为Ii = 1:长度(a) p = find(ismember(matched,a(Ii)));匹配(p) = 0;[ranking，~] = find(prefA(a(ii)，:) == p);[~，idx] = min(ranking);匹配(p(idx)) = a(ii);结束其他的%第2轮及以后[matched,proposed] = findMatch(prefP,prefA,matched,proposed);结束结束matched = [(1:size(prefP,1))'，matched];%对匹配结果进行评分分数=零(大小(匹配));为Ii = 1:size(matched,1) p = matched(Ii,1);A =匹配(ii,2);scores(p,1) = find(prefP(p，:) == a);scores(a,2) = find(prefA(a，:) == p);结束Varargout{1} =分数;结束

generateSMPdataset

函数[prefP,prefA] = generateSMPdataset(N,M) prefP = 0 (N,M);prefA = 0 (M,N);为ii = 1:N prefP(ii，:) = randperm(M);结束为2:M prefA(2，:) = randperm(N);结束结束

milongaMatch

函数tandas = milongmatch (prefL,prefF,t) tandas = 0 (size(prefL,1)，t);为ii = 1:t tanda = 0 (size(prefL,1)，1);建议= false(大小(prefL,1));确保没有人和以前的舞伴跳舞。如果Ii > 1 prev = tandas(:，1: Ii -1);为jj = 1:尺寸(prefL, 1)提出(jj:) = ismember (prefL (jj,:),上一页(jj,:));结束结束而any(tanda == 0) [tanda,proposed] = findMatch(prefL,prefF,tanda,proposed);%停止，如果自由提议者没有接受的提议如果所有(所有(建议(tanda == 0，:)，2)))打破结束结束Tandas (:，ii) = tanda;结束结束

flexibleGS

函数matched = flexibleGS(prefP,prefA) N = size(prefP,1);M = size(prefA,1);如果N < M matched = 0 (M,1);其他的匹配= 0 (N,1);结束建议= false(N,M);趁我们还有免费的提议者…而any(匹配(1:N) == 0)%找到匹配的[matched,proposed] = findMatch(prefP,prefA,matched,proposed);但是如果他们找不到可以求婚的对象就打住。如果所有(所有(建议(匹配(1:N) == 0，:)，2))打破结束结束如果N < M matched(matched == 0) = setdiff(1:M,matched);matched = [[(1:N)';0]，matched];其他的matched = [(1:size(prefP,1))'，matched];结束结束

获取MATLAB代码

发布与MATLAB®R2020a