I like to start my grad algorithms course with stable matching.  It is a beautiful, clean, practical algorithm.  It can be covered relatively quickly and give an overview of the basics of algorithm design and analysis.  I love it.

What I hate is that every treatment of stable matching available online and in the textbooks in my office is presented as the stable marriage problem with men getting matched to women and men getting their best possible match and women getting their worst possible match.  Seriously?  This 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’ve been told)?  We need to teach this algorithm as an exercise in heternormative, sexist coupling?

If half our field were women, do you think women would be repeatedly getting the shaft in this lesson plan?  If we didn’t need It Gets Better in our society, would we be proscribing to man meets woman, man proposes to woman, man marries woman?  If we lived in a dreamy society that didn’t spend one-third of Africa’s debt each year in the wedding industry, would we be using this metaphor?

So, here you go: very basic, stripped-down lecture notes on the Gale-Shapely algorithm that matches jobs to candidates.  (Written quickly, corrections welcome.)

If someone could change the wikipedia page on the problem from stable marriage to stable matching, I would be much appreciative.  (My wikipedia skills are no match.)

Update 9/22: To clarify, it is the United States that spends (on the wedding industry) an amount equivalent to one-third of Africa’s debt.

Update 9/25: Jeff Erickson presents stable matching using doctors and hospitals.

Update March 2015: Motherboard picks up the story.