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.
I’ve had the same issues. I follow the Kleinberg-Tardos book (which is great!) and I like to follow the textbook as many students like that. However, the inherent imbalance is not that nice. To try and correct the imbalance, I end up stating the algorithm as where the women do all the proposing, so the women end up getting their best possible match and the men end up getting their worst possible match. However, this is probably just as sexist and I should probably switch to a matching as you mention above. (I’d have to give up on the Firefly.) reference though.)
So good to know I’m not the only one.
I initially didn’t like it but I have more recently thought of it as educational in that it implies that the very traditional societal norms would still unfairly favor men. I also point out a suit by medical residents about 20 years ago which forced the hospitals to switch how they ran the algorithm from one that favored hospitals to one that favors residents.
To my mind the reason that the marriage analogy works less and less is that the marriage graph no longer need be bipartite!
I felt uncomfortable with this material the first time I taught it.
But, I decided that humor (and mockery) was the right way
to get through it. You can start by describing the situation of
“2n breeders”.
I think that the big advantage of using men and women is that
people intuitively understand the algorithm, if not its implications.
These lectures get a lot of students talking in the first week, and helps
sets an interactive tone for the rest of the semester.
As Paul points out, it is really a revelation when you explain the
implications of the algorithm. You barely need to hint at the
implications for society to get students excited about the material.
I find it helps draw in students from other majors.
Finally, the non-bipartite case is a wonderful source of
homework problems.
Maybe it’s time to switch to CLRS and try another problem to start! 😉
or you can simply reverse it, the fact is no one care about it, even if you define it the other way (women choose men, and women getting their best and so on)
What I hate is that every treatment of stable matching available online…
[slowly raises hand]
I usually reverse the sexes in that algorithm as well as in many other examples and exercises in class.
When I teach the algorithm, I usually choose the role of sexes uniformly at random by flipping a coin in class. I also explain the students that my goal is to avoid being accused of sexism.
Hmm … I have always thought the standard treatment of stable marriage as being mildly feminist as it points out that the stereotypical dating ritual is man optimal and woman pessimal; Thus, in principle, encouraging women to more proactive socially.
Pingback: Better Know A Theorem: Online Matching « QED and NOM
Pingback: Online Lunch « Stack Exchange Theoretical Computer Science Blog
I felt uncomfortable with this material the first time I taught it.
But, I decided that humor (and mockery) was the right way
to get through it.