{"id":3643,"date":"2020-04-23T07:46:13","date_gmt":"2020-04-23T12:46:13","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/?p=3643"},"modified":"2020-05-12T11:49:22","modified_gmt":"2020-05-12T15:49:22","slug":"stable-matching-problem-and-the-algorithm-that-won-a-novel-prize","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2020\/04\/23\/stable-matching-problem-and-the-algorithm-that-won-a-novel-prize\/","title":{"rendered":"Stable Matching Problem and the Algorithm that Won a Nobel Prize"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>Many here in Massachusetts started social distancing about a month ago and we have no end in sight yet. If you live alone, maybe you are ready to match up with someone after you get through this hardship. Today's guest blogger, <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/profile\/authors\/951521\">Toshi Takeuchi<\/a>, has a perfect algorithm for you.  I love that this was inspired by a problem that, at first glance, doesn't seem very technical or relevant.  But it is!<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2020\/tango.png\" alt=\"\"> <\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#bc2ee831-a5a8-4ad2-94f7-a64dfacf6d53\">It Began with a Facebook Post<\/a><\/li><li><a href=\"#05218e0f-d92e-4ebf-9946-aa4333abb69c\">Problem Definition<\/a><\/li><li><a href=\"#311d17cf-a03c-4b32-afcb-dce12500fe9c\">Gale Shapley Algorithm<\/a><\/li><li><a href=\"#033d3e4f-7528-4497-95b1-c783e7157573\">Improved Implementation<\/a><\/li><li><a href=\"#1c541b05-730e-47af-8702-d2b09a885e6a\">How Happy Are They?<\/a><\/li><li><a href=\"#9e13339c-264b-461b-9d59-954c81dc43b4\">Reversing the Roles<\/a><\/li><li><a href=\"#2c2a192b-8ec3-422c-ad1a-c2fad75fe450\">Simulations Over 100 Trials<\/a><\/li><li><a href=\"#ba3fc96a-fc9c-48d6-8c4a-0695e1d01e45\">It's Better to Be Proposers Than Acceptors<\/a><\/li><li><a href=\"#c3336e20-9044-4938-8c1c-4cacb0194422\">Back to the Original Challenge<\/a><\/li><li><a href=\"#ee1b91fd-1c68-44d5-ad73-7741c34cf157\">Summary<\/a><\/li><li><a href=\"#3d3ce8bf-e8b8-4d27-a674-e8eef8551c3e\">Functions<\/a><\/li><\/ul><\/div><h4>It Began with a Facebook Post<a name=\"bc2ee831-a5a8-4ad2-94f7-a64dfacf6d53\"><\/a><\/h4><p>One day I came across <a href=\"https:\/\/www.facebook.com\/groups\/208267570251577\/permalink\/214654102946257\/\">a Facebook post<\/a> in one of those groups that had sprung up to help people cope with social distancing. It began:<\/p><p><b>\"A coding challenge and a puzzle to solve! The Nobel prize for Economics (my subject) was recently awarded for work on matching markets, where you care not just about demand and supply in general but about precisely who gets what. Sound familiar? Well that&#8217;s a milonga, right?\"<\/b> (a milonga is an Argentine Tango dance event)<\/p><p>That's how I learned about the Stable Matching Problem (SMP). The original poster wanted people to apply the SMP to solve the problem of matching people for a partner dance. That sounded trivial, but the actual problem had many consequential applications.<\/p><div><ul><li><a href=\"http:\/\/www.nrmp.org\/\">National Resident Matching Program (NRMP)<\/a> matches tens of thousands medical students to residency programs<\/li><li><a title=\"https:\/\/blogs.cornell.edu\/info4220\/2015\/03\/10\/stable-matching-incorporated-in-new-york-citys-high-school-application-process\/ (link no longer works)\">New York City's High School Choice program<\/a> matches tens of thousands of students to public high schools<\/li><li>Doctors needs to match individual donors to recipients for kidney transplants<\/li><li>Tens of thousands of edge servers must be matched to billions of web requests per hour<\/li><\/ul><\/div><p>And indeed the algorithm that is 100% guaranteed to find solutions to the SMP won <a href=\"https:\/\/www.nobelprize.org\/prizes\/economic-sciences\/2012\/press-release\/\">the 2012 Nobel Prize in Economics<\/a>.<\/p><h4>Problem Definition<a name=\"05218e0f-d92e-4ebf-9946-aa4333abb69c\"><\/a><\/h4><p>Given two sets of participants of equal size to match, such as medical students and residency programs, and with their fixed preferences, such as:<\/p><pre>S1 = {R1 R2 R3}  R1 = {S1 S3 S2}\r\nS2 = {R3 R1 R2}  R2 = {S1 S2 S3}\r\nS3 = {R1 R3 R2}  R3 = {S3 S1 S2}<\/pre><p>Can we find stable matches? Stability in this case means:<\/p><div><ul><li>no one is left unmatched, and<\/li><li>no one can find a better match who is willing to switch<\/li><\/ul><\/div><p>A solution may look like this:<\/p><pre>(S1, R1), (S2, R2), (S3, R3)<\/pre><p>This is stable because:<\/p><div><ul><li><tt>S1<\/tt> is matched to <tt>R1<\/tt>, and they are the first choices for each other. Yay!<\/li><li><tt>S2<\/tt> prefers <tt>R3<\/tt> to <tt>R2<\/tt>, but <tt>R3<\/tt> is matched to <tt>S3<\/tt>, its first choice, and therefore <tt>R3<\/tt> is not willing to switch<\/li><li><tt>S3<\/tt> prefers <tt>R1<\/tt> to <tt>R3<\/tt>, but <tt>R1<\/tt> is matched to <tt>S1<\/tt>, its first choice, and therefore <tt>R1<\/tt> is not willing to switch<\/li><\/ul><\/div><p>Now what is this algorithm that is guaranteed to generate solutions to the SMP?<\/p><h4>Gale Shapley Algorithm<a name=\"311d17cf-a03c-4b32-afcb-dce12500fe9c\"><\/a><\/h4><p>This remarkable algorithm is called the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Gale%E2%80%93Shapley_algorithm\">Gale-Shapley algorithm<\/a> and it is surprisingly straight-forward.<\/p><div><ul><li>One set of participants always proposes their matches to the other set of participants<\/li><li>Those who propose (proposers) list their most to least favorite<\/li><li>Those who get proposed to (acceptors) always accept the most favorable proposal if not currently matched<\/li><li>Matched acceptors can switch to a new suitor if the new suitor is preferable<\/li><li>The algorithm terminates when everyone is matched<\/li><\/ul><\/div><p>The pseudocode from the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Gale%E2%80%93Shapley_algorithm\">Wikipedia page<\/a> is as follows:<\/p><pre class=\"language-matlab\">algorithm <span class=\"string\">stable_matching<\/span> <span class=\"string\">is<\/span>\r\n    Initialize <span class=\"string\">all<\/span> <span class=\"string\">m<\/span> <span class=\"string\">&#8712;<\/span> <span class=\"string\">M<\/span> <span class=\"string\">and<\/span> <span class=\"string\">w<\/span> <span class=\"string\">&#8712;<\/span> <span class=\"string\">W<\/span> <span class=\"string\">to<\/span> <span class=\"string\">free<\/span>\r\n    <span class=\"keyword\">while<\/span> &#8707; free <span class=\"string\">man<\/span> <span class=\"string\">m<\/span> <span class=\"string\">who<\/span> <span class=\"string\">still<\/span> <span class=\"string\">has<\/span> <span class=\"string\">a<\/span> <span class=\"string\">woman<\/span> <span class=\"string\">w<\/span> <span class=\"string\">to<\/span> <span class=\"string\">propose<\/span> <span class=\"string\">to<\/span> <span class=\"string\">do<\/span>\r\n        w <span class=\"string\">:=<\/span> <span class=\"string\">first<\/span> <span class=\"string\">woman<\/span> <span class=\"string\">on<\/span> <span class=\"untermstring\">m's list to whom m has not yet proposed<\/span>\r\n        <span class=\"keyword\">if<\/span> w is <span class=\"string\">free<\/span> <span class=\"string\">then<\/span>\r\n            (m, w) become <span class=\"string\">engaged<\/span>\r\n        <span class=\"keyword\">else<\/span> some <span class=\"string\">pair<\/span> <span class=\"string\">(m', w)<\/span> <span class=\"string\">already<\/span> <span class=\"string\">exists<\/span>\r\n            <span class=\"keyword\">if<\/span> w prefers <span class=\"string\">m<\/span> <span class=\"string\">to<\/span> <span class=\"untermstring\">m' then<\/span>\r\n                m' becomes <span class=\"string\">free<\/span>\r\n                (m, w) become <span class=\"string\">engaged<\/span>\r\n            <span class=\"keyword\">else<\/span>\r\n                (m', w) remain <span class=\"string\">engaged<\/span>\r\n            <span class=\"keyword\">end<\/span> <span class=\"keyword\">if<\/span>\r\n        <span class=\"keyword\">end<\/span> <span class=\"keyword\">if<\/span>\r\n    repeat\r\n<\/pre><p>Here is the sample data from the Wikipedia page. There are 4 proposers and 4 acceptors. Rows represent either proposers or acceptors depending on the table, and columns their ranked preferences, where numbers are indices to their preferred matches.<\/p><pre class=\"codeinput\">prefProposers = [2,1,3,4;4,1,2,3;1,3,2,4;2,3,1,4]\r\nprefAcceptors = [1,3,2,4;3,4,1,2;4,2,3,1;3,2,1,4]\r\nwikiSolution = [1,1;2,4;3,3;4,2];\r\n<\/pre><pre class=\"codeoutput\">prefProposers =\r\n     2     1     3     4\r\n     4     1     2     3\r\n     1     3     2     4\r\n     2     3     1     4\r\nprefAcceptors =\r\n     1     3     2     4\r\n     3     4     1     2\r\n     4     2     3     1\r\n     3     2     1     4\r\n<\/pre><p>Unfortunately, it is not very intuitive to use numbers to walk through this example. To avoid a clich&eacute;, I tried to come up with a non-gender-based example, but I couldn't come up with a compelling one. For example, Loren asked me to apply the SMP to matching people to their favorite food, but I can't imagine pizza or sushi rejecting me (not sure if I can handle that).<\/p><p>This is not very original but at least I can reverse the traditional gender roles in our little Jane Austen drama, and let girls ask out boys.<\/p><pre class=\"codeinput\">proposers = [<span class=\"string\">\"Charlotte\"<\/span>,<span class=\"string\">\"Jane\"<\/span>,<span class=\"string\">\"Lizzy\"<\/span>,<span class=\"string\">\"Lydia\"<\/span>];\r\nacceptors = [<span class=\"string\">\"Bingley\"<\/span>,<span class=\"string\">\"Collins\"<\/span>,<span class=\"string\">\"Darcy\"<\/span>,<span class=\"string\">\"Wickham\"<\/span>];\r\n<\/pre><p>The first row of <tt>prefProposers<\/tt> represents Charlottes' preferences, and her first choice is 2, or Collins. Her second is choice 1, or Bingley, etc.<\/p><pre class=\"codeinput\">prefCharlotte = prefProposers(proposers == <span class=\"string\">\"Charlotte\"<\/span>,:)\r\n<\/pre><pre class=\"codeoutput\">prefCharlotte =\r\n     2     1     3     4\r\n<\/pre><p>The pseudocode is implemented literally as the function <tt>galeShapley1<\/tt> (see the <a href=\"#3d3ce8bf-e8b8-4d27-a674-e8eef8551c3e\">Functions<\/a> section at the bottom), which sequentially iterates over proposers to find their matches. The routine inside the while loop is in the subfunction <tt>findMatch<\/tt>.<\/p><p>It uses the vector <tt>matched<\/tt> to keep track of engagements, which is initially all zeros. Rows 1 to 4 map to respective proposers. If all elements are zeros, you know all proposers are free.<\/p><pre class=\"codeinput\">matched = [0;0;0;0]\r\n<\/pre><pre class=\"codeoutput\">matched =\r\n     0\r\n     0\r\n     0\r\n     0\r\n<\/pre><p>When Charlotte proposes to Collins and he accepts, the first element is replaced with 2, which maps to Collins. Now they are engaged. We continue this way until Lydia proposes to Collins, who is already engaged to Charlotte.<\/p><pre class=\"codeinput\">matched = [2;4;1;0]\r\n<\/pre><pre class=\"codeoutput\">matched =\r\n     2\r\n     4\r\n     1\r\n     0\r\n<\/pre><p>Because Collins prefers Lydia to Charlotte, he switches, and Charlotte becomes free. We know this because the first element is zero.<\/p><pre class=\"codeinput\">matched = [0;4;1;2]\r\n<\/pre><pre class=\"codeoutput\">matched =\r\n     0\r\n     4\r\n     1\r\n     2\r\n<\/pre><p>Now we tried to find a match for Charlotte. Since she was already rejected by her first choice, we go with her second, Bingley, who is engaged to Lizzy. Bingley likes Charlotte better. Now Lizzy becomes free.<\/p><pre class=\"codeinput\">matched = [1;4;0;2]\r\n<\/pre><pre class=\"codeoutput\">matched =\r\n     1\r\n     4\r\n     0\r\n     2\r\n<\/pre><p>Lizzy's second choice is Darcy, and Darcy is free. Now they are engaged.<\/p><pre class=\"codeinput\">matched = [1;4;3;2]\r\n<\/pre><pre class=\"codeoutput\">matched =\r\n     1\r\n     4\r\n     3\r\n     2\r\n<\/pre><p>Now everyone is engaged, and the algorithm terminates.<\/p><p>Let's run the MATLAB code.<\/p><pre class=\"codeinput\">stableMatch1 = galeShapley1(prefProposers,prefAcceptors);\r\n<\/pre><p>And here is the outcome.<\/p><pre class=\"codeinput\">namedMatch = strings(size(stableMatch1,1),1);\r\nnamedMatch(:,1) = proposers';\r\n<span class=\"keyword\">for<\/span> ii = 1:length(acceptors)\r\n    namedMatch(stableMatch1(:,2) == ii,2) = acceptors(ii);\r\n<span class=\"keyword\">end<\/span>\r\nnamedMatch\r\n<\/pre><pre class=\"codeoutput\">namedMatch = \r\n  4&times;2 string array\r\n    \"Charlotte\"    \"Bingley\"\r\n    \"Jane\"         \"Wickham\"\r\n    \"Lizzy\"        \"Darcy\"  \r\n    \"Lydia\"        \"Collins\"\r\n<\/pre><p>And here is the result in numbers, which matches to <a href=\"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/5\/52\/Gale-Shapley.gif\">the solution in the GIF animation<\/a> from the Wikipedia page.<\/p><pre class=\"codeinput\">doesMatch = isequal(wikiSolution,stableMatch1)\r\n<\/pre><pre class=\"codeoutput\">doesMatch =\r\n  logical\r\n   1\r\n<\/pre><h4>Improved Implementation<a name=\"033d3e4f-7528-4497-95b1-c783e7157573\"><\/a><\/h4><p>We know that the sequential approach is not very efficient. In the first round, no one is rejected or matched yet. The acceptors are supposed to accept any first proposals. Therefore, we don't have to iterate over each proposer in this round. We could just copy their first choices.<\/p><pre class=\"codeinput\">matched = [2;4;1;2]\r\n<\/pre><pre class=\"codeoutput\">matched =\r\n     2\r\n     4\r\n     1\r\n     2\r\n<\/pre><p>Then we need to check if any acceptors have received multiple proposals, such as 2 (Collins) in this example, and deal with them.<\/p><p>Function <tt>galeShapley2<\/tt> implements this idea. From the second round on, we use the original routine. We can do this because in the Gale-Shapley algorithm, the order of execution doesn't affect the outcome, as you can see from the output below.<\/p><pre class=\"codeinput\">[stableMatch2,scores] = galeShapley2(prefProposers,prefAcceptors);\r\n<\/pre><p>The output matches the previous result.<\/p><pre class=\"codeinput\">doesMatch = isequal(stableMatch1,stableMatch2)\r\n<\/pre><pre class=\"codeoutput\">doesMatch =\r\n  logical\r\n   1\r\n<\/pre><h4>How Happy Are They?<a name=\"1c541b05-730e-47af-8702-d2b09a885e6a\"><\/a><\/h4><p>With <tt>galeShapley2<\/tt>, the second return variable <tt>scores<\/tt> shows how satisfied the participants are with the matches. It contains the rankings of their final matches. The first column is for proposers and the second column acceptors.<\/p><pre class=\"codeinput\">scores\r\n<\/pre><pre class=\"codeoutput\">scores =\r\n     2     1\r\n     1     2\r\n     2     3\r\n     1     2\r\n<\/pre><div><ul><li>Charlotte is matched to her #2 choice, Jane her #1, Lizzy her #2, and Lydia her #1.<\/li><li>Bingley his #1, Collins his #2, Darcy his #3, and Wickham his #2.<\/li><\/ul><\/div><p>We can sum the rankings to see who did better. The smaller the score the better.<\/p><pre class=\"codeinput\">totalScores = sum(scores)\r\n<\/pre><pre class=\"codeoutput\">totalScores =\r\n     6     8\r\n<\/pre><p>It appears that the proposers got better matches than acceptors.<\/p><h4>Reversing the Roles<a name=\"9e13339c-264b-461b-9d59-954c81dc43b4\"><\/a><\/h4><p>Let's see what happens if we switch the proposers and acceptors.<\/p><pre class=\"codeinput\">[stableMatch3,scores] = galeShapley2(prefAcceptors,prefProposers);\r\n<\/pre><p>And here is the outcome. You see that the outcome is not the same as before.<\/p><pre class=\"codeinput\">stableMatch3\r\n<\/pre><pre class=\"codeoutput\">stableMatch3 =\r\n     1     1\r\n     2     3\r\n     3     4\r\n     4     2\r\n<\/pre><p>And here are the scores.<\/p><pre class=\"codeinput\">scores\r\n<\/pre><pre class=\"codeoutput\">scores =\r\n     1     2\r\n     1     1\r\n     1     3\r\n     2     2\r\n<\/pre><div><ul><li>Bingley is matched to his #1 choice, Collins his #1, Darcy his #1, and Wickham his #2.<\/li><li>Charlotte her #2, Jane her #1, Lizzy her #3, and Lydia her #2.<\/li><\/ul><\/div><pre class=\"codeinput\">totalScores = sum(scores)\r\n<\/pre><pre class=\"codeoutput\">totalScores =\r\n     5     8\r\n<\/pre><p>Again, those who proposed got better matches than those who accepted.<\/p><h4>Simulations Over 100 Trials<a name=\"2c2a192b-8ec3-422c-ad1a-c2fad75fe450\"><\/a><\/h4><p>Under the Gale-Shapley algorithm, proposers generally do better than acceptors.<\/p><div><ul><li>Proposers start out with their first choices and they can only go down from there<\/li><li>Acceptors can only improve the match through rejection, and they don't have control over how many proposals they get<\/li><\/ul><\/div><p>Let's generate a dataset randomly using the function <tt>generateSMPdataset<\/tt> and plot the scores of proposers and acceptors. You can see that the scores of proposers are generally lower than those of acceptors and therefore they are getting the better matches.<\/p><pre class=\"codeinput\">iter = 100;\r\ntotalScores = zeros(iter,2);\r\n<span class=\"keyword\">for<\/span> ii = 1:iter\r\n    [prefProposers,prefAcceptors] = generateSMPdataset(4,4);\r\n    [~, scores] = galeShapley2(prefProposers,prefAcceptors);\r\n    totalScores(ii,:) = sum(scores);\r\n<span class=\"keyword\">end<\/span>\r\nfigure\r\nplot(1:iter,totalScores(:,1))\r\nhold <span class=\"string\">on<\/span>\r\nplot(1:iter,totalScores(:,2))\r\nhold <span class=\"string\">off<\/span>\r\nxlabel(<span class=\"string\">\"Trials\"<\/span>)\r\nylabel(<span class=\"string\">\"Scores - the Lower the Better\"<\/span>)\r\ntitle([<span class=\"string\">\"Gale-Shapley Algorithm - Scores by Role\"<\/span>;<span class=\"string\">\"The Lower the Score, the Better\"<\/span>])\r\nlegend(<span class=\"string\">\"Proposers\"<\/span>,<span class=\"string\">\"Acceptors\"<\/span>,<span class=\"string\">\"Location\"<\/span>,<span class=\"string\">\"best\"<\/span>)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2020\/StableMatchingProblem_01.png\" alt=\"\"> <h4>It's Better to Be Proposers Than Acceptors<a name=\"ba3fc96a-fc9c-48d6-8c4a-0695e1d01e45\"><\/a><\/h4><p>Naively, it looks better to be acceptors because they can say no and don't have to face humiliating rejections. But, in exchange for the pain of rejection, proposers get better choices and that leads to the better outcomes. It is also known that if acceptors reject more by lying about their preferences, then they can game the system in their favor.<\/p><p><b>Let this be your life lesson: initiate and risk rejections because that gives you better choices.<\/b><\/p><p>It is also very important to consider who will be the proposers when we design a system that affects who the system benefits the most.<\/p><div><ul><li>In the case of NRMP, the medical students are the proposers. The system favors the medical students over the residency programs<\/li><li>NYC High School Choice program, the students are the proposers. The system favors the students over the high schools they are applying for<\/li><li>The edge servers are the proposers. The system favors the edge servers over the web requests<\/li><\/ul><\/div><p>The system doesn't have to be set up this way, but they are what they are because they are designed to benefit one type of participants over the other.<\/p><h4>Back to the Original Challenge<a name=\"c3336e20-9044-4938-8c1c-4cacb0194422\"><\/a><\/h4><p>Now that we are familiar with the basic formulation of the SMP and the Gale-Shapley algorithm, let's go back to the challenge the original poster gave us.<\/p><p>In a milonga (dance event), we have 4 followers and 4 leaders.<\/p><pre class=\"codeinput\">namesF = [<span class=\"string\">\"Anna\"<\/span>,<span class=\"string\">\"Brigitte\"<\/span>,<span class=\"string\">\"Caroline\"<\/span>,<span class=\"string\">\"Dominique\"<\/span>];\r\nnamesL = [<span class=\"string\">\"Oliver\"<\/span>,<span class=\"string\">\"Thomas\"<\/span>,<span class=\"string\">\"Henri\"<\/span>,<span class=\"string\">\"Frank\"<\/span>];\r\n<\/pre><p>Their rankings are as follows:<\/p><pre class=\"codeinput\">prefF = [1,2,3,4;1,3,2,4;2,4,1,3;3,1,4,2]\r\nprefL = [4,3,2,1;3,4,1,2;2,3,4,1;3,1,4,2]\r\n<\/pre><pre class=\"codeoutput\">prefF =\r\n     1     2     3     4\r\n     1     3     2     4\r\n     2     4     1     3\r\n     3     1     4     2\r\nprefL =\r\n     4     3     2     1\r\n     3     4     1     2\r\n     2     3     4     1\r\n     3     1     4     2\r\n<\/pre><div><ul><li>Only leaders can invite followers and followers cannot reject a leader if they are free<\/li><li>There is only time for 3 tandas during the milonga<\/li><li>A tanda is a set of 3 or 4 songs and you dance with the same partner during a tanda<\/li><li>In a new tanda, however, no one can dance with a previous partner<\/li><\/ul><\/div><p>The puzzle<\/p><div><ol><li>Who does leader 1 (Oliver) dance with on the third tanda?<\/li><li>Which dancers don't get to dance with their first choices during the milonga?<\/li><\/ol><\/div><p>The Coding Challenge<\/p><div><ol><li>Write a program in your favorite language to find the GS outcome for a single tanda (Done: <tt>galeShapley2<\/tt>)<\/li><li>Extend the program to find the solution for a milonga of <tt>t<\/tt> tandas. Use your program to obtain the solution to the puzzle above.<\/li><\/ol><\/div><p>Here is the function <tt>milongaMatch<\/tt> to meet the coding challenge. The only new rule we need to deal with is that people are not allowed to dance with the same person again. Please note that this variant no longer 100% guarantees that everyone gets a partner (dancers, take notice). It stops when free proposers run out of acceptors to propose to.<\/p><pre class=\"codeinput\">tandas = milongaMatch(prefL,prefF,3);\r\n<\/pre><p>Let's assign names to the output.<\/p><pre class=\"codeinput\">solution = strings(size(tandas));\r\n<span class=\"keyword\">for<\/span> ii = 1:length(namesF)\r\n    solution(tandas == ii) = namesF(ii);\r\n<span class=\"keyword\">end<\/span>\r\nsolution = array2table(solution,<span class=\"string\">\"RowNames\"<\/span>,namesL, <span class=\"keyword\">...<\/span>\r\n    <span class=\"string\">\"VariableNames\"<\/span>,<span class=\"string\">\"Tanda\"<\/span> + (1:size(tandas,2)))\r\n<\/pre><pre class=\"codeoutput\">solution =\r\n  4&times;3 table\r\n                Tanda1         Tanda2         Tanda3   \r\n              ___________    ___________    ___________\r\n    Oliver    \"Dominique\"    \"Brigitte\"     \"Caroline\" \r\n    Thomas    \"Caroline\"     \"Anna\"         \"Brigitte\" \r\n    Henri     \"Brigitte\"     \"Dominique\"    \"Anna\"     \r\n    Frank     \"Anna\"         \"Caroline\"     \"Dominique\"\r\n<\/pre><p>The answer to the puzzle<\/p><div><ol><li>Oliver (row 1) dances with Caroline (3) in the third tanda (column 3)<\/li><li>Anna (1) doesn't get to dance with her first choice Oliver (row 1), but everyone else dances with their respective first choice at some point<\/li><\/ol><\/div><p>One complaint I have with Gale-Shapley is that it requires the two types of participants be in equal numbers. When it comes to social dancing, that never happens - usually we get more followers than leaders. I came up with a variant <tt>flexibleGS<\/tt> that can handle when proposers and acceptors are not equal in numbers. Give it a try!<\/p><pre class=\"codeinput\">prefProposers = [2,1,3,4,5;4,1,2,3,5;1,3,2,4,5;2,3,1,4,5];\r\nprefAcceptors = [1,3,2,4;3,4,1,2;4,2,3,1;3,2,1,4;1,3,2,4];\r\nstableMatch4 = flexibleGS(prefProposers,prefAcceptors);\r\n<\/pre><h4>Summary<a name=\"ee1b91fd-1c68-44d5-ad73-7741c34cf157\"><\/a><\/h4><p>Do you like puzzles and coding challenges? Did you find the SMP interesting? Can you think of fun examples to apply the SMP to? I am still thinking of a food example. <a href=\"https:\/\/www.en-kyoto.yumeyakata.com\/post\/20180322\">There are restaurants in Japan that reject first time customers<\/a>, unless accompanied by a regular who can vouch for you that your taste buds are worthy of their cuisine. Is that a SMP though? Share your fun SMP ideas <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=3643#respond\">here<\/a>.<\/p><h4>Functions<a name=\"3d3ce8bf-e8b8-4d27-a674-e8eef8551c3e\"><\/a><\/h4><p><b>galeShapley1<\/b><\/p><pre class=\"codeinput\"><span class=\"keyword\">function<\/span> matched = galeShapley1(prefP,prefA)\r\n    <span class=\"comment\">% Initialize all proposers and acceptors to free<\/span>\r\n    matched = zeros(size(prefP,1),1);\r\n    proposed = false(size(prefP,1));\r\n\r\n    <span class=\"comment\">% while there exist a free proposer |p| ...<\/span>\r\n    <span class=\"keyword\">while<\/span> any(matched == 0)\r\n        <span class=\"comment\">% find a match for |p|<\/span>\r\n        [matched,proposed] = findMatch(prefP,prefA,matched,proposed);\r\n    <span class=\"keyword\">end<\/span>\r\n    matched = [(1:size(prefP,1))',matched];\r\n<span class=\"keyword\">end<\/span>\r\n<\/pre><p><b>findMatch<\/b><\/p><pre class=\"codeinput\"><span class=\"keyword\">function<\/span> [matched,proposed] = findMatch(prefP,prefA,matched,proposed)\r\n    p = find(matched == 0,1);\r\n    <span class=\"comment\">% with |p| who still has acceptors to propose to<\/span>\r\n    acceptors = prefP(p,~proposed(p,:));\r\n\r\n    <span class=\"keyword\">for<\/span> ii = 1:length(acceptors)\r\n        <span class=\"comment\">% |a| is |p|'s highest ranked such acceptor to whom |p| has not yet<\/span>\r\n        <span class=\"comment\">% proposed<\/span>\r\n        a = acceptors(ii);\r\n        proposed(p,prefP(p,:) == a) = true;\r\n\r\n        <span class=\"comment\">% if |a| is free<\/span>\r\n        <span class=\"keyword\">if<\/span> ~any(matched == a)\r\n            <span class=\"comment\">% (p, a) become engaged<\/span>\r\n            matched(p) = a;\r\n            <span class=\"keyword\">break<\/span>\r\n        <span class=\"keyword\">else<\/span>\r\n            <span class=\"comment\">% else some pair (p', a) already exists<\/span>\r\n            p_ = find(matched == a);\r\n            [ranking,~] = find(prefA(a,:) == [p;p_]);\r\n\r\n            <span class=\"comment\">% if |a| prefers |p| to |p'|<\/span>\r\n            <span class=\"keyword\">if<\/span>  ranking(1) &lt; ranking(2)\r\n                <span class=\"comment\">% |p'| becomes free<\/span>\r\n                matched(p_) = 0;\r\n                <span class=\"comment\">% (p, a) become engaged<\/span>\r\n                matched(p) = a;\r\n                <span class=\"keyword\">break<\/span>\r\n            <span class=\"keyword\">else<\/span>\r\n                <span class=\"comment\">% else (p', a) remain engaged<\/span>\r\n            <span class=\"keyword\">end<\/span>\r\n        <span class=\"keyword\">end<\/span>\r\n    <span class=\"keyword\">end<\/span>\r\n<span class=\"keyword\">end<\/span>\r\n<\/pre><p><b>galeShapley2<\/b><\/p><pre class=\"codeinput\"><span class=\"keyword\">function<\/span> [matched,varargout] = galeShapley2(prefP,prefA)\r\n    matched = zeros(size(prefP,1),1);\r\n    proposed = false(size(prefP,1));\r\n\r\n    <span class=\"keyword\">while<\/span> any(matched == 0)\r\n        <span class=\"comment\">% This handles round 1<\/span>\r\n        <span class=\"keyword\">if<\/span> all(matched == 0)\r\n            matched = prefP(:,1);\r\n            proposed(:,1) = true;\r\n            [acceptors,~,idx] = unique(matched);\r\n            a = acceptors(accumarray(idx,1) &gt; 1);\r\n            <span class=\"keyword\">for<\/span> ii = 1:length(a)\r\n                p = find(ismember(matched,a(ii)));\r\n                matched(p) = 0;\r\n                [ranking,~] = find(prefA(a(ii),:) == p);\r\n                [~,idx] = min(ranking);\r\n                matched(p(idx)) = a(ii);\r\n            <span class=\"keyword\">end<\/span>\r\n        <span class=\"keyword\">else<\/span>\r\n            <span class=\"comment\">% round 2 and onwards<\/span>\r\n            [matched,proposed] = findMatch(prefP,prefA,matched,proposed);\r\n        <span class=\"keyword\">end<\/span>\r\n    <span class=\"keyword\">end<\/span>\r\n    matched = [(1:size(prefP,1))',matched];\r\n\r\n    <span class=\"comment\">% scoring the matching result<\/span>\r\n    scores = zeros(size(matched));\r\n    <span class=\"keyword\">for<\/span> ii = 1:size(matched,1)\r\n        p = matched(ii,1);\r\n        a = matched(ii,2);\r\n        scores(p,1) = find(prefP(p,:) == a);\r\n        scores(a,2) = find(prefA(a,:) == p);\r\n    <span class=\"keyword\">end<\/span>\r\n    varargout{1} = scores;\r\n<span class=\"keyword\">end<\/span>\r\n<\/pre><p><b>generateSMPdataset<\/b><\/p><pre class=\"codeinput\"><span class=\"keyword\">function<\/span> [prefP,prefA] = generateSMPdataset(N,M)\r\n    prefP = zeros(N,M);\r\n    prefA = zeros(M,N);\r\n    <span class=\"keyword\">for<\/span> ii = 1:N\r\n        prefP(ii,:) = randperm(M);\r\n    <span class=\"keyword\">end<\/span>\r\n    <span class=\"keyword\">for<\/span> ii = 1:M\r\n        prefA(ii,:) = randperm(N);\r\n    <span class=\"keyword\">end<\/span>\r\n<span class=\"keyword\">end<\/span>\r\n<\/pre><p><b>milongaMatch<\/b><\/p><pre class=\"codeinput\"><span class=\"keyword\">function<\/span> tandas = milongaMatch(prefL,prefF,t)\r\n    tandas = zeros(size(prefL,1),t);\r\n    <span class=\"keyword\">for<\/span> ii = 1:t\r\n        tanda = zeros(size(prefL,1),1);\r\n        proposed = false(size(prefL,1));\r\n\r\n        <span class=\"comment\">% make sure no one dances with a previous partner<\/span>\r\n        <span class=\"keyword\">if<\/span> ii &gt; 1\r\n            prev = tandas(:,1:ii-1);\r\n            <span class=\"keyword\">for<\/span> jj = 1:size(prefL,1)\r\n                proposed(jj,:) = ismember(prefL(jj,:),prev(jj,:));\r\n            <span class=\"keyword\">end<\/span>\r\n        <span class=\"keyword\">end<\/span>\r\n\r\n        <span class=\"keyword\">while<\/span> any(tanda == 0)\r\n            [tanda,proposed] = findMatch(prefL,prefF,tanda,proposed);\r\n            <span class=\"comment\">% stop if free proposers run out of acceptors to propose to<\/span>\r\n            <span class=\"keyword\">if<\/span> all(all(proposed(tanda == 0,:),2))\r\n                <span class=\"keyword\">break<\/span>\r\n            <span class=\"keyword\">end<\/span>\r\n        <span class=\"keyword\">end<\/span>\r\n        tandas(:,ii) = tanda;\r\n    <span class=\"keyword\">end<\/span>\r\n<span class=\"keyword\">end<\/span>\r\n<\/pre><p><b>flexibleGS<\/b><\/p><pre class=\"codeinput\"><span class=\"keyword\">function<\/span> matched = flexibleGS(prefP,prefA)\r\n\r\n    N = size(prefP,1);\r\n    M = size(prefA,1);\r\n    <span class=\"keyword\">if<\/span> N &lt; M\r\n        matched = zeros(M,1);\r\n    <span class=\"keyword\">else<\/span>\r\n        matched = zeros(N,1);\r\n    <span class=\"keyword\">end<\/span>\r\n    proposed = false(N,M);\r\n\r\n    <span class=\"comment\">% while we still have free proposers ...<\/span>\r\n    <span class=\"keyword\">while<\/span> any(matched(1:N) == 0)\r\n        <span class=\"comment\">% find them matches<\/span>\r\n        [matched,proposed] = findMatch(prefP,prefA,matched,proposed);\r\n        <span class=\"comment\">% but stop if they run out of acceptors to propose to<\/span>\r\n        <span class=\"keyword\">if<\/span> all(all(proposed(matched(1:N) == 0,:),2))\r\n            <span class=\"keyword\">break<\/span>\r\n        <span class=\"keyword\">end<\/span>\r\n    <span class=\"keyword\">end<\/span>\r\n    <span class=\"keyword\">if<\/span> N &lt; M\r\n        matched(matched == 0) = setdiff(1:M,matched);\r\n        matched = [[(1:N)';0],matched];\r\n    <span class=\"keyword\">else<\/span>\r\n        matched = [(1:size(prefP,1))',matched];\r\n    <span class=\"keyword\">end<\/span>\r\n<span class=\"keyword\">end<\/span>\r\n<\/pre><script language=\"JavaScript\"> <!-- \r\n    function grabCode_f3cdc70273bc4f1a92ce1a0dfaa6783b() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='f3cdc70273bc4f1a92ce1a0dfaa6783b ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' f3cdc70273bc4f1a92ce1a0dfaa6783b';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2020 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_f3cdc70273bc4f1a92ce1a0dfaa6783b()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2020a<br><\/p><\/div><!--\r\nf3cdc70273bc4f1a92ce1a0dfaa6783b ##### SOURCE BEGIN #####\r\n%% Stable Matching Problem and the Algorithm that Won a Novel Prize\r\n% Many here in Massachusetts started social distancing about a month ago\r\n% and we have no end in sight yet. If you live alone, maybe you are ready\r\n% to match up with someone after you get through this hardship. Today's\r\n% guest blogger,\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/profile\/authors\/951521 Toshi\r\n% Takeuchi>, has a perfect algorithm for you.  I love that this was\r\n% inspired by a problem that, at first glance, doesn't seem very technical\r\n% or relevant.  But it is!\r\n% \r\n% <<tango.png>>\r\n%\r\n%% It Began with a Facebook Post\r\n% One day I came across\r\n% <https:\/\/www.facebook.com\/groups\/208267570251577\/permalink\/214654102946257\/\r\n% a Facebook post> in one of those groups that had sprung up to help people\r\n% cope with social distancing. It began:\r\n% \r\n% *\"A coding challenge and a puzzle to solve! The Nobel prize for Economics\r\n% (my subject) was recently awarded for work on matching markets, where you\r\n% care not just about demand and supply in general but about precisely who\r\n% gets what. Sound familiar? Well that\u2019s a milonga, right?\"* (a milonga is\r\n% an Argentine Tango dance event)\r\n% \r\n% That's how I learned about the Stable Matching Problem (SMP). The\r\n% original poster wanted people to apply the SMP to solve the problem of\r\n% matching people for a partner dance. That sounded trivial, but the actual\r\n% problem had many consequential applications.\r\n%\r\n% * <http:\/\/www.nrmp.org\/ National Resident Matching Program (NRMP)>\r\n% matches tens of thousands medical students to residency programs\r\n% * <https:\/\/blogs.cornell.edu\/info4220\/2015\/03\/10\/stable-matching-incorporated-in-new-york-citys-high-school-application-process\/\r\n% New York City's High School Choice program> matches tens of thousands of\r\n% students to public high schools\r\n% * Doctors needs to match individual donors to recipients for kidney\r\n% transplants\r\n% * Tens of thousands of edge servers must be matched to billions of web\r\n% requests per hour\r\n%\r\n% And indeed the algorithm that is 100% guaranteed to find solutions to the\r\n% SMP won\r\n% <https:\/\/www.nobelprize.org\/prizes\/economic-sciences\/2012\/press-release\/\r\n% the 2012 Nobel Prize in Economics>.\r\n%% Problem Definition\r\n% Given two sets of participants of equal size to match, such as medical\r\n% students and residency programs, and with their fixed preferences, such\r\n% as:\r\n% \r\n%  S1 = {R1 R2 R3}  R1 = {S1 S3 S2}\r\n%  S2 = {R3 R1 R2}  R2 = {S1 S2 S3}\r\n%  S3 = {R1 R3 R2}  R3 = {S3 S1 S2}\r\n% \r\n% Can we find stable matches? Stability in this case means:\r\n%\r\n% * no one is left unmatched, and\r\n% * no one can find a better match who is willing to switch\r\n%\r\n% A solution may look like this:\r\n% \r\n%  (S1, R1), (S2, R2), (S3, R3) \r\n% \r\n% This is stable because:\r\n%\r\n% * |S1| is matched to |R1|, and they are the first choices for each other.\r\n% Yay!\r\n% * |S2| prefers |R3| to |R2|, but |R3| is matched to |S3|, its first\r\n% choice, and therefore |R3| is not willing to switch\r\n% * |S3| prefers |R1| to |R3|, but |R1| is matched to |S1|, its first\r\n% choice, and therefore |R1| is not willing to switch\r\n%\r\n% Now what is this algorithm that is guaranteed to generate solutions to\r\n% the SMP?\r\n%\r\n%% Gale Shapley Algorithm\r\n% This remarkable algorithm is called the\r\n% <https:\/\/en.wikipedia.org\/wiki\/Gale%E2%80%93Shapley_algorithm\r\n% Gale-Shapley algorithm> and it is surprisingly straight-forward.\r\n%\r\n% * One set of participants always proposes their matches to the other set\r\n% of participants\r\n% * Those who propose (proposers) list their most to least favorite\r\n% * Those who get proposed to (acceptors) always accept the most favorable\r\n% proposal if not currently matched\r\n% * Matched acceptors can switch to a new suitor if the new suitor is\r\n% preferable\r\n% * The algorithm terminates when everyone is matched\r\n%\r\n% The pseudocode from the\r\n% <https:\/\/en.wikipedia.org\/wiki\/Gale%E2%80%93Shapley_algorithm Wikipedia\r\n% page> is as follows:\r\n% \r\n%   algorithm stable_matching is\r\n%       Initialize all m \u2208 M and w \u2208 W to free\r\n%       while \u2203 free man m who still has a woman w to propose to do\r\n%           w := first woman on m's list to whom m has not yet proposed\r\n%           if w is free then\r\n%               (m, w) become engaged\r\n%           else some pair (m', w) already exists\r\n%               if w prefers m to m' then\r\n%                   m' becomes free\r\n%                   (m, w) become engaged \r\n%               else\r\n%                   (m', w) remain engaged\r\n%               end if\r\n%           end if\r\n%       repeat\r\n%\r\n% Here is the sample data from the Wikipedia page. There are 4 proposers\r\n% and 4 acceptors. Rows represent either proposers or acceptors depending\r\n% on the table, and columns their ranked preferences, where numbers are\r\n% indices to their preferred matches.\r\n\r\nprefProposers = [2,1,3,4;4,1,2,3;1,3,2,4;2,3,1,4]\r\nprefAcceptors = [1,3,2,4;3,4,1,2;4,2,3,1;3,2,1,4]\r\nwikiSolution = [1,1;2,4;3,3;4,2];\r\n\r\n%% \r\n% Unfortunately, it is not very intuitive to use numbers to walk through\r\n% this example. To avoid a clich\u00e9, I tried to come up with a\r\n% non-gender-based example, but I couldn't come up with a compelling one.\r\n% For example, Loren asked me to apply the SMP to matching people to their\r\n% favorite food, but I can't imagine pizza or sushi rejecting me (not sure\r\n% if I can handle that).\r\n% \r\n% This is not very original but at least I can reverse the traditional\r\n% gender roles in our little Jane Austen drama, and let girls ask out boys.\r\n\r\nproposers = [\"Charlotte\",\"Jane\",\"Lizzy\",\"Lydia\"];\r\nacceptors = [\"Bingley\",\"Collins\",\"Darcy\",\"Wickham\"];\r\n\r\n%% \r\n% The first row of |prefProposers| represents Charlottes' preferences, and\r\n% her first choice is 2, or Collins. Her second is choice 1, or Bingley,\r\n% etc.\r\n\r\nprefCharlotte = prefProposers(proposers == \"Charlotte\",:)\r\n\r\n%% \r\n% The pseudocode is implemented literally as the function |galeShapley1|\r\n% (see the <#33 Functions> section at the bottom), which sequentially\r\n% iterates over proposers to find their matches. The routine inside the\r\n% while loop is in the subfunction |findMatch|.\r\n% \r\n% It uses the vector |matched| to keep track of engagements, which is\r\n% initially all zeros. Rows 1 to 4 map to respective proposers. If all\r\n% elements are zeros, you know all proposers are free.\r\n\r\nmatched = [0;0;0;0]\r\n\r\n%% \r\n% When Charlotte proposes to Collins and he accepts, the first element is\r\n% replaced with 2, which maps to Collins. Now they are engaged. We continue\r\n% this way until Lydia proposes to Collins, who is already engaged to\r\n% Charlotte.\r\n\r\nmatched = [2;4;1;0]\r\n\r\n%% \r\n% Because Collins prefers Lydia to Charlotte, he switches, and Charlotte\r\n% becomes free. We know this because the first element is zero.\r\n\r\nmatched = [0;4;1;2]\r\n\r\n%% \r\n% Now we tried to find a match for Charlotte. Since she was already\r\n% rejected by her first choice, we go with her second, Bingley, who is\r\n% engaged to Lizzy. Bingley likes Charlotte better. Now Lizzy becomes free.\r\n\r\nmatched = [1;4;0;2]\r\n\r\n%% \r\n% Lizzy's second choice is Darcy, and Darcy is free. Now they are engaged. \r\n\r\nmatched = [1;4;3;2]\r\n\r\n%% \r\n% Now everyone is engaged, and the algorithm terminates.  \r\n% \r\n% Let's run the MATLAB code. \r\n\r\nstableMatch1 = galeShapley1(prefProposers,prefAcceptors);\r\n\r\n%%\r\n% And here is the outcome. \r\nnamedMatch = strings(size(stableMatch1,1),1);\r\nnamedMatch(:,1) = proposers';\r\nfor ii = 1:length(acceptors)\r\n    namedMatch(stableMatch1(:,2) == ii,2) = acceptors(ii);\r\nend\r\nnamedMatch\r\n\r\n%% \r\n% And here is the result in numbers, which matches to\r\n% <https:\/\/upload.wikimedia.org\/wikipedia\/commons\/5\/52\/Gale-Shapley.gif the\r\n% solution in the GIF animation> from the Wikipedia page.\r\n\r\ndoesMatch = isequal(wikiSolution,stableMatch1)\r\n\r\n%% Improved Implementation\r\n% We know that the sequential approach is not very efficient. In the first\r\n% round, no one is rejected or matched yet. The acceptors are supposed to\r\n% accept any first proposals. Therefore, we don't have to iterate over each\r\n% proposer in this round. We could just copy their first choices.\r\n\r\nmatched = [2;4;1;2]\r\n\r\n%% \r\n% Then we need to check if any acceptors have received multiple proposals,\r\n% such as 2 (Collins) in this example, and deal with them. \r\n%\r\n% Function |galeShapley2| implements this idea. From the second round on,\r\n% we use the original routine. We can do this because in the Gale-Shapley\r\n% algorithm, the order of execution doesn't affect the outcome, as you can\r\n% see from the output below.\r\n\r\n[stableMatch2,scores] = galeShapley2(prefProposers,prefAcceptors);\r\n\r\n%%\r\n% The output matches the previous result. \r\ndoesMatch = isequal(stableMatch1,stableMatch2)\r\n\r\n%% How Happy Are They?\r\n% With |galeShapley2|, the second return variable |scores| shows how\r\n% satisfied the participants are with the matches. It contains the rankings\r\n% of their final matches. The first column is for proposers and the second\r\n% column acceptors.\r\n\r\nscores\r\n\r\n%% \r\n% * Charlotte is matched to her #2 choice, Jane her #1, Lizzy her #2, and\r\n% Lydia her #1.\r\n% * Bingley his #1, Collins his #2, Darcy his #3, and Wickham his #2.\r\n%\r\n% We can sum the rankings to see who did better. The smaller the score the better. \r\n\r\ntotalScores = sum(scores)\r\n\r\n%% \r\n% It appears that the proposers got better matches than acceptors. \r\n%\r\n%% Reversing the Roles\r\n% Let's see what happens if we switch the proposers and acceptors. \r\n\r\n[stableMatch3,scores] = galeShapley2(prefAcceptors,prefProposers);\r\n\r\n%% \r\n% And here is the outcome. You see that the outcome is not the same as\r\n% before.\r\n\r\nstableMatch3\r\n\r\n%% \r\n% And here are the scores. \r\n\r\nscores\r\n\r\n%% \r\n% * Bingley is matched to his #1 choice, Collins his #1, Darcy his #1, and\r\n% Wickham his #2.\r\n% * Charlotte her #2, Jane her #1, Lizzy her #3, and Lydia her #2.\r\n\r\ntotalScores = sum(scores)\r\n\r\n%% \r\n% Again, those who proposed got better matches than those who accepted. \r\n%\r\n%% Simulations Over 100 Trials\r\n% Under the Gale-Shapley algorithm, proposers generally do better than\r\n% acceptors.\r\n%\r\n% * Proposers start out with their first choices and they can only go down\r\n% from there\r\n% * Acceptors can only improve the match through rejection, and they don't\r\n% have control over how many proposals they get\r\n%\r\n% Let's generate a dataset randomly using the function |generateSMPdataset|\r\n% and plot the scores of proposers and acceptors. You can see that the\r\n% scores of proposers are generally lower than those of acceptors and\r\n% therefore they are getting the better matches.\r\n\r\niter = 100;\r\ntotalScores = zeros(iter,2);\r\nfor ii = 1:iter\r\n    [prefProposers,prefAcceptors] = generateSMPdataset(4,4);\r\n    [~, scores] = galeShapley2(prefProposers,prefAcceptors);\r\n    totalScores(ii,:) = sum(scores);\r\nend\r\nfigure\r\nplot(1:iter,totalScores(:,1))\r\nhold on\r\nplot(1:iter,totalScores(:,2))\r\nhold off\r\nxlabel(\"Trials\")\r\nylabel(\"Scores - the Lower the Better\")\r\ntitle([\"Gale-Shapley Algorithm - Scores by Role\";\"The Lower the Score, the Better\"])\r\nlegend(\"Proposers\",\"Acceptors\",\"Location\",\"best\")\r\n\r\n%% It's Better to Be Proposers Than Acceptors\r\n% Naively, it looks better to be acceptors because they can say no and\r\n% don't have to face humiliating rejections. But, in exchange for the pain\r\n% of rejection, proposers get better choices and that leads to the better\r\n% outcomes. It is also known that if acceptors reject more by lying about\r\n% their preferences, then they can game the system in their favor.\r\n% \r\n% *Let this be your life lesson: initiate and risk rejections because\r\n% that gives you better choices.*\r\n% \r\n% It is also very important to consider who will be the proposers when we\r\n% design a system that affects who the system benefits the most.\r\n%\r\n% * In the case of NRMP, the medical students are the proposers. The system\r\n% favors the medical students over the residency programs\r\n% * NYC High School Choice program, the students are the proposers. The\r\n% system favors the students over the high schools they are applying for\r\n% * The edge servers are the proposers. The system favors the edge\r\n% servers over the web requests\r\n%\r\n% The system doesn't have to be set up this way, but they are what they are\r\n% because they are designed to benefit one type of participants over the\r\n% other.\r\n%\r\n%% Back to the Original Challenge\r\n% Now that we are familiar with the basic formulation of the SMP and the\r\n% Gale-Shapley algorithm, let's go back to the challenge the original\r\n% poster gave us.\r\n% \r\n% In a milonga (dance event), we have 4 followers and 4 leaders.\r\n\r\nnamesF = [\"Anna\",\"Brigitte\",\"Caroline\",\"Dominique\"];\r\nnamesL = [\"Oliver\",\"Thomas\",\"Henri\",\"Frank\"];\r\n\r\n%% \r\n% Their rankings are as follows:\r\n\r\nprefF = [1,2,3,4;1,3,2,4;2,4,1,3;3,1,4,2]\r\nprefL = [4,3,2,1;3,4,1,2;2,3,4,1;3,1,4,2]\r\n\r\n%% \r\n% * Only leaders can invite followers and followers cannot reject a leader\r\n% if they are free\r\n% * There is only time for 3 tandas during the milonga\r\n% * A tanda is a set of 3 or 4 songs and you dance with the same partner\r\n% during a tanda\r\n% * In a new tanda, however, no one can dance with a previous partner\r\n%\r\n% The puzzle\r\n%\r\n% # Who does leader 1 (Oliver) dance with on the third tanda?\r\n% # Which dancers don't get to dance with their first choices during the\r\n% milonga?\r\n%\r\n% The Coding Challenge\r\n%\r\n% # Write a program in your favorite language to find the GS outcome for a\r\n% single tanda (Done: |galeShapley2|)\r\n% # Extend the program to find the solution for a milonga of |t| tandas.\r\n% Use your program to obtain the solution to the puzzle above.\r\n%\r\n% Here is the function |milongaMatch| to meet the coding challenge. The\r\n% only new rule we need to deal with is that people are not allowed to\r\n% dance with the same person again. Please note that this variant no longer\r\n% 100% guarantees that everyone gets a partner (dancers, take notice).\r\n% It stops when free proposers run out of acceptors to propose to.\r\n\r\ntandas = milongaMatch(prefL,prefF,3);\r\n%%\r\n% Let's assign names to the output.\r\n\r\nsolution = strings(size(tandas));\r\nfor ii = 1:length(namesF)\r\n    solution(tandas == ii) = namesF(ii);\r\nend\r\nsolution = array2table(solution,\"RowNames\",namesL, ...\r\n    \"VariableNames\",\"Tanda\" + (1:size(tandas,2)))\r\n\r\n%% \r\n% The answer to the puzzle\r\n% \r\n% # Oliver (row 1) dances with Caroline (3) in the third tanda (column 3)\r\n% # Anna (1) doesn't get to dance with her first choice Oliver (row 1), but \r\n% everyone else dances with their respective first choice at some point\r\n%\r\n% One complaint I have with Gale-Shapley is that it requires the two types\r\n% of participants be in equal numbers. When it comes to social dancing,\r\n% that never happens - usually we get more followers than leaders. I came\r\n% up with a variant |flexibleGS| that can handle when proposers and\r\n% acceptors are not equal in numbers. Give it a try!\r\nprefProposers = [2,1,3,4,5;4,1,2,3,5;1,3,2,4,5;2,3,1,4,5];\r\nprefAcceptors = [1,3,2,4;3,4,1,2;4,2,3,1;3,2,1,4;1,3,2,4];\r\nstableMatch4 = flexibleGS(prefProposers,prefAcceptors);\r\n\r\n%% Summary\r\n% Do you like puzzles and coding challenges? Did you find the SMP\r\n% interesting? Can you think of fun examples to apply the SMP to? I am\r\n% still thinking of a food example.\r\n% <https:\/\/www.en-kyoto.yumeyakata.com\/post\/20180322 There are restaurants\r\n% in Japan that reject first time customers>, unless accompanied by a\r\n% regular who can vouch for you that your taste buds are worthy of their\r\n% cuisine. Is that a SMP though? Share your fun SMP ideas\r\n% <https:\/\/blogs.mathworks.com\/loren\/?p=3643#respond here>.\r\n%\r\n%% Functions\r\n% *galeShapley1*\r\n\r\nfunction matched = galeShapley1(prefP,prefA)\r\n    % Initialize all proposers and acceptors to free\r\n    matched = zeros(size(prefP,1),1);\r\n    proposed = false(size(prefP,1));\r\n    \r\n    % while there exist a free proposer |p| ...\r\n    while any(matched == 0)\r\n        % find a match for |p|\r\n        [matched,proposed] = findMatch(prefP,prefA,matched,proposed);\r\n    end\r\n    matched = [(1:size(prefP,1))',matched];    \r\nend\r\n\r\n%%\r\n% *findMatch*\r\n\r\nfunction [matched,proposed] = findMatch(prefP,prefA,matched,proposed)\r\n    p = find(matched == 0,1);\r\n    % with |p| who still has acceptors to propose to\r\n    acceptors = prefP(p,~proposed(p,:));\r\n\r\n    for ii = 1:length(acceptors)\r\n        % |a| is |p|'s highest ranked such acceptor to whom |p| has not yet\r\n        % proposed\r\n        a = acceptors(ii);\r\n        proposed(p,prefP(p,:) == a) = true;\r\n\r\n        % if |a| is free\r\n        if ~any(matched == a)\r\n            % (p, a) become engaged\r\n            matched(p) = a;\r\n            break\r\n        else\r\n            % else some pair (p', a) already exists\r\n            p_ = find(matched == a);\r\n            [ranking,~] = find(prefA(a,:) == [p;p_]);\r\n\r\n            % if |a| prefers |p| to |p'|\r\n            if  ranking(1) < ranking(2)\r\n                % |p'| becomes free\r\n                matched(p_) = 0;\r\n                % (p, a) become engaged\r\n                matched(p) = a;\r\n                break\r\n            else\r\n                % else (p', a) remain engaged\r\n            end\r\n        end\r\n    end\r\nend\r\n\r\n%%\r\n% *galeShapley2*\r\n\r\nfunction [matched,varargout] = galeShapley2(prefP,prefA)\r\n    matched = zeros(size(prefP,1),1);\r\n    proposed = false(size(prefP,1));\r\n    \r\n    while any(matched == 0)\r\n        % This handles round 1\r\n        if all(matched == 0)\r\n            matched = prefP(:,1);\r\n            proposed(:,1) = true;\r\n            [acceptors,~,idx] = unique(matched);\r\n            a = acceptors(accumarray(idx,1) > 1);\r\n            for ii = 1:length(a)\r\n                p = find(ismember(matched,a(ii)));\r\n                matched(p) = 0;\r\n                [ranking,~] = find(prefA(a(ii),:) == p);\r\n                [~,idx] = min(ranking);\r\n                matched(p(idx)) = a(ii);\r\n            end\r\n        else\r\n            % round 2 and onwards\r\n            [matched,proposed] = findMatch(prefP,prefA,matched,proposed);\r\n        end\r\n    end\r\n    matched = [(1:size(prefP,1))',matched];\r\n    \r\n    % scoring the matching result\r\n    scores = zeros(size(matched));\r\n    for ii = 1:size(matched,1)\r\n        p = matched(ii,1);\r\n        a = matched(ii,2);\r\n        scores(p,1) = find(prefP(p,:) == a);\r\n        scores(a,2) = find(prefA(a,:) == p);\r\n    end\r\n    varargout{1} = scores;\r\nend\r\n\r\n%% \r\n% *generateSMPdataset*\r\n\r\nfunction [prefP,prefA] = generateSMPdataset(N,M)\r\n    prefP = zeros(N,M);\r\n    prefA = zeros(M,N);\r\n    for ii = 1:N\r\n        prefP(ii,:) = randperm(M);\r\n    end\r\n    for ii = 1:M\r\n        prefA(ii,:) = randperm(N);\r\n    end\r\nend\r\n%% \r\n% *milongaMatch*\r\n\r\nfunction tandas = milongaMatch(prefL,prefF,t)\r\n    tandas = zeros(size(prefL,1),t);\r\n    for ii = 1:t\r\n        tanda = zeros(size(prefL,1),1);\r\n        proposed = false(size(prefL,1));\r\n        \r\n        % make sure no one dances with a previous partner\r\n        if ii > 1\r\n            prev = tandas(:,1:ii-1);\r\n            for jj = 1:size(prefL,1)\r\n                proposed(jj,:) = ismember(prefL(jj,:),prev(jj,:));\r\n            end\r\n        end\r\n        \r\n        while any(tanda == 0)\r\n            [tanda,proposed] = findMatch(prefL,prefF,tanda,proposed);\r\n            % stop if free proposers run out of acceptors to propose to\r\n            if all(all(proposed(tanda == 0,:),2))\r\n                break\r\n            end\r\n        end\r\n        tandas(:,ii) = tanda;\r\n    end\r\nend\r\n\r\n%% \r\n% *flexibleGS*\r\n\r\nfunction matched = flexibleGS(prefP,prefA)\r\n\r\n    N = size(prefP,1);\r\n    M = size(prefA,1);\r\n    if N < M\r\n        matched = zeros(M,1);\r\n    else\r\n        matched = zeros(N,1);\r\n    end\r\n    proposed = false(N,M);\r\n    \r\n    % while we still have free proposers ...\r\n    while any(matched(1:N) == 0)\r\n        % find them matches\r\n        [matched,proposed] = findMatch(prefP,prefA,matched,proposed);\r\n        % but stop if they run out of acceptors to propose to\r\n        if all(all(proposed(matched(1:N) == 0,:),2))\r\n            break\r\n        end\r\n    end\r\n    if N < M\r\n        matched(matched == 0) = setdiff(1:M,matched);\r\n        matched = [[(1:N)';0],matched];\r\n    else\r\n        matched = [(1:size(prefP,1))',matched];\r\n    end\r\nend\r\n##### SOURCE END ##### f3cdc70273bc4f1a92ce1a0dfaa6783b\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2020\/StableMatchingProblem_01.png\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction--><p>Many here in Massachusetts started social distancing about a month ago and we have no end in sight yet. If you live alone, maybe you are ready to match up with someone after you get through this hardship. Today's guest blogger, <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/profile\/authors\/951521\">Toshi Takeuchi<\/a>, has a perfect algorithm for you.  I love that this was inspired by a problem that, at first glance, doesn't seem very technical or relevant.  But it is!... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2020\/04\/23\/stable-matching-problem-and-the-algorithm-that-won-a-novel-prize\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[89,29,61],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/3643"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=3643"}],"version-history":[{"count":6,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/3643\/revisions"}],"predecessor-version":[{"id":3723,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/3643\/revisions\/3723"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=3643"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=3643"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=3643"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}