{"id":720,"date":"2011-09-22T10:02:16","date_gmt":"2011-09-22T17:02:16","guid":{"rendered":"http:\/\/www.glencora.org\/?p=720"},"modified":"2015-05-26T13:55:33","modified_gmt":"2015-05-26T13:55:33","slug":"inoffensive-stable-matching","status":"publish","type":"post","link":"https:\/\/blogs.oregonstate.edu\/glencora\/2011\/09\/22\/inoffensive-stable-matching\/","title":{"rendered":"Inoffensive stable matching"},"content":{"rendered":"<p>I like to start my <a href=\"http:\/\/teach.glencora.org\/index.php?title=CS515,_Fall_2011\">grad algorithms course<\/a> with stable matching. \u00a0It is a beautiful, clean, practical algorithm. \u00a0It can be covered relatively quickly and give an overview of the basics of algorithm design and analysis. \u00a0I love it.<\/p>\n<p>What I hate is that every treatment of stable matching available online and in the textbooks in my office is presented as the stable <em>marriage<\/em> problem with <em>men<\/em> getting matched to <em>women<\/em> and men getting their <em>best<\/em> possible match and women getting their <em>worst<\/em> possible match. \u00a0Seriously? \u00a0This algorithm that is used to match children to schools and medical students to residency programs and dental and medical specialists to hospitals and students to universities and lawyers to law firms and rabbis to congregations (or so I&#8217;ve been told)? \u00a0We need to teach this algorithm as an exercise in heternormative, sexist coupling?<\/p>\n<p>If half our field were women, do you think women would be repeatedly getting the shaft in this lesson plan? \u00a0If we didn&#8217;t need <a href=\"http:\/\/www.itgetsbetter.org\/\">It Gets Better<\/a> in our society, would we be proscribing to man meets woman, man proposes to woman, man marries woman? \u00a0If we lived in a dreamy society that didn&#8217;t spend one-third of Africa&#8217;s debt <em>each year<\/em> in the wedding industry, would we be using this metaphor?<\/p>\n<p>So, here you go: <a href=\"http:\/\/teach.glencora.org\/index.php?title=Stable_matching:_A_first_algorithm\">very basic, stripped-down lecture notes on the Gale-Shapely algorithm<\/a> that matches jobs to candidates. \u00a0(Written quickly, corrections welcome.)<\/p>\n<p>If someone could change the wikipedia page on the problem from stable marriage to stable matching, I would be much appreciative. \u00a0(My wikipedia skills are no match.)<\/p>\n<p><em>Update 9\/22: <\/em>To clarify, it is the United States that spends (on the wedding industry) an amount equivalent to one-third of Africa&#8217;s debt.<\/p>\n<p><em>Update 9\/25:<\/em> Jeff Erickson presents stable matching using <a href=\"http:\/\/theory.cs.uiuc.edu\/~jeffe\/teaching\/algorithms\/notes\/00-intro.pdf\">doctors and hospitals<\/a>.<\/p>\n<p><em>Update March 2015: <\/em><a href=\"http:\/\/motherboard.vice.com\/en_uk\/read\/when-algorithms-are-sexist\">Motherboard picks up the story<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I like to start my grad algorithms course with stable matching. \u00a0It is a beautiful, clean, practical algorithm. \u00a0It can be covered relatively quickly and give an overview of the basics of algorithm design and analysis. \u00a0I love it. What I hate is that every treatment of stable matching available online and in the textbooks [&hellip;]<\/p>\n","protected":false},"author":3747,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[106166,106168,106186,106190],"class_list":["post-720","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-grad-algorithms","tag-heteronormativity","tag-sexism","tag-tcs"],"_links":{"self":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/720","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/users\/3747"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/comments?post=720"}],"version-history":[{"count":2,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/720\/revisions"}],"predecessor-version":[{"id":1174,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/720\/revisions\/1174"}],"wp:attachment":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/media?parent=720"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/categories?post=720"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/tags?post=720"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}