{"id":146,"date":"2022-02-14T09:00:00","date_gmt":"2022-02-14T09:00:00","guid":{"rendered":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/?p=146"},"modified":"2024-03-10T16:46:04","modified_gmt":"2024-03-10T16:46:04","slug":"a-new-reality-tv-show-idea-the-stable-marriage-algorithm","status":"publish","type":"post","link":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/2022\/02\/14\/a-new-reality-tv-show-idea-the-stable-marriage-algorithm\/","title":{"rendered":"A new reality TV show idea: the Stable Marriage algorithm"},"content":{"rendered":"<span class=\"span-reading-time rt-reading-time\" style=\"display: block;\"><span class=\"rt-label rt-prefix\">Reading Time: <\/span> <span class=\"rt-time\"> 3<\/span> <span class=\"rt-label rt-postfix\">minutes<\/span><\/span>\n<p class=\"wp-block-paragraph\">As a hopeful romantic, a believer in the principle of marriage and a lover of dating reality TV, I was immediately intrigued by this problem and solution. So to celebrate Valentine&#8217;s Day I thought it would be fitting to look at the stable marriage problem.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"1-the-premise\">1. The Premise<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Consider two disjoint sets with the same number of elements (for example a group of <em>n<\/em> men and a group of <em>n <\/em>women). A <strong>matching<\/strong> is a one-to-one mapping from one set onto the other (a set of <em>n<\/em> monogamous marriages between the men and women). Each man has an order of preference for the women and each woman an order of preference for the men.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">A matching is <strong>unstable<\/strong> if there exists a possible pairing of a man and a woman (not currently married) that both prefer each other to their spouses. For example, Johnny is married to Bao but prefers Myrla and Myrla is married to Gil but prefers Johnny (IYKYK). Whereas this would making for entertaining TV, the stable marriage problem is to find a matching that avoids this situation.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"2-the-pitch\">2. The Pitch<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Firstly, it is always possible to find a stable matching in this situation. One possible way to find a solution is the Gale-Shapley algorithm:<\/p>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-8f761849 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<p class=\"wp-block-paragraph\"><strong>First Round<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Each man proposes to the woman he prefers the most.<\/li><li>Each woman (if she received any proposals) tentatively accepts her favourite proposal and rejects all the others.<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Subsequent Rounds<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Each <strong>unengaged<\/strong> man proposes to the next woman he prefers the most who has not yet rejected him, regardless of whether she is currently engaged (<em>scandalous!<\/em>)<\/li><li>Each <strong>unengaged <\/strong>woman tentatively accepts her favourite proposal and rejects all the others. <\/li><li>Each <strong>engaged<\/strong> woman considers any new proposals and leaves her current partner if she prefers one of the new proposals. She tentatively accepts that better proposal and rejects all the others.<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">The subsequent rounds are repeated until everyone is engaged. <\/p>\n<\/div>\n\n\n\n<div class=\"wp-block-column is-vertically-aligned-center is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:40%\">\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"861\" height=\"706\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-content\/uploads\/sites\/38\/2022\/02\/Gale-Shapley.gif\" alt=\"\" class=\"wp-image-183\" \/><figcaption>Example of the Gale-Shapley algorithm (from <a href=\"https:\/\/en.wikipedia.org\/wiki\/Gale%E2%80%93Shapley_algorithm\">Wikipedia<\/a>)<\/figcaption><\/figure><\/div>\n<\/div>\n<\/div>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"3-a-problem\">3. A Problem<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Important for this algorithm is who makes the proposals &#8211; if the men propose, the overall outcome is better for them than for the women. If we score each marriage in the stable matching from both the male and female perspectives based on each person&#8217;s preferences and take total score for each gender, you can see a clear difference in the distribution of the scores. The difference is more drastic as the set size is increased.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"290\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-content\/uploads\/sites\/38\/2022\/02\/stable-marriage-1024x290.png\" alt=\"\" class=\"wp-image-187\" srcset=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-content\/uploads\/sites\/38\/2022\/02\/stable-marriage-1024x290.png 1024w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-content\/uploads\/sites\/38\/2022\/02\/stable-marriage-300x85.png 300w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-content\/uploads\/sites\/38\/2022\/02\/stable-marriage-768x218.png 768w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-content\/uploads\/sites\/38\/2022\/02\/stable-marriage.png 1175w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><figcaption>Distribution of scores for stable matchings when males make proposal using randomly generated preference tables (female scores red, male scores blue)<\/figcaption><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"4-in-practice\">4. In Practice<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">While I&#8217;ve introduced this problem as a pitch for a dramatic (even if biased) match-making show, Shapley and Roth won a <a href=\"https:\/\/www.nobelprize.org\/uploads\/2018\/06\/popular-economicsciences2012.pdf\" target=\"_blank\" rel=\"noreferrer noopener\">Nobel prize<\/a> for their applications of this problem and someone did his whole <a href=\"http:\/\/dcs.gla.ac.uk\/~gregg\/papers\/2007omalleyphd.pdf\" target=\"_blank\" rel=\"noreferrer noopener\">PhD thesis<\/a> extending some of the ideas. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Here are some interesting situations that this algorithm or some variation of it have been used for in practice:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/web.stanford.edu\/~alroth\/papers\/rothperansonaer.PDF\" data-type=\"URL\" data-id=\"https:\/\/web.stanford.edu\/~alroth\/papers\/rothperansonaer.PDF\" target=\"_blank\" rel=\"noreferrer noopener\">Placing new doctors at hospitals<\/a><\/li><li><a href=\"https:\/\/economics.mit.edu\/files\/3024\" data-type=\"URL\" data-id=\"https:\/\/economics.mit.edu\/files\/3024\" target=\"_blank\" rel=\"noreferrer noopener\">Matching students to high schools<\/a><\/li><li><a href=\"https:\/\/www.bbc.co.uk\/news\/business-50632630\" data-type=\"URL\" data-id=\"https:\/\/www.bbc.co.uk\/news\/business-50632630\" target=\"_blank\" rel=\"noreferrer noopener\">Matching organs<\/a> to transplant patients<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"learn-more\">Learn more<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li>Gale, D., &amp; Shapley, L. S. (1962). <a href=\"https:\/\/www.jstor.org\/stable\/2312726\" target=\"_blank\" rel=\"noreferrer noopener\">College Admissions and the Stability of Marriage<\/a>.&nbsp;<em>The American Mathematical Monthly<\/em>,&nbsp;<em>69<\/em>(1), 9\u201315.<\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p><span class=\"span-reading-time rt-reading-time\" style=\"display: block;\"><span class=\"rt-label rt-prefix\">Reading Time: <\/span> <span class=\"rt-time\"> 3<\/span> <span class=\"rt-label rt-postfix\">minutes<\/span><\/span>As a hopeful romantic, a believer in the principle of marriage and a lover of dating reality TV, I was immediately intrigued by this problem and solution. So to celebrate Valentine&#8217;s Day I thought it would be fitting to look at the stable marriage problem.<\/p>\n","protected":false},"author":41,"featured_media":247,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[13],"tags":[11,16],"class_list":["post-146","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-a-few-of-my-favourite-things","tag-matching-theory","tag-operations-research","post-with-thumbnail","post-with-thumbnail-large"],"_links":{"self":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-json\/wp\/v2\/posts\/146","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-json\/wp\/v2\/users\/41"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-json\/wp\/v2\/comments?post=146"}],"version-history":[{"count":16,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-json\/wp\/v2\/posts\/146\/revisions"}],"predecessor-version":[{"id":296,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-json\/wp\/v2\/posts\/146\/revisions\/296"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-json\/wp\/v2\/media\/247"}],"wp:attachment":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-json\/wp\/v2\/media?parent=146"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-json\/wp\/v2\/categories?post=146"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/danielle-notice\/wp-json\/wp\/v2\/tags?post=146"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}