The Gale-Shapely Algorithm

The most interesting class that I didn't sleep through in my Computer Science major was my Introduction to Algorithms course, which was a junior year course (back then everything had the "Introduction to" prefix in front of it, so they wouldn't scare people off unintentionally (the intentional scaring happened within the class)). The first thing that we talked about in that class was a dystopian scenario where two distinct identically-sized groups of people were forced to form pairs, or even marriages, one from each group. I guess bipartite graphs where each vertex has degree 1 were all the rage in the late 90s. 

At any rate, we were given an algorithm that told us that, as long as the people involved gave us extra information, like a ranking of the people in the other group in terms of who they'd want to be with, their mother's maiden name, and their credit card information, we could find a way to set them up so that they'd be unable to do any better! We could even call it being content with their lot in (this) life (though stable would be better)! 

Referred to as the Gale-Shapley algorithm, we made significant improvements over the old randomly arranged marriage system by arranging their marriages for them: one group would look at their preference lists and would ask people in the other group to pair up. The people that were asked (the responders) would automatically be forced into a pairing unless already paired, in which case they had the chance to choose between who they were with currently and who was asking them. It was amazingly simple once we ignored 80% of the data! 

We even proved that under these conditions, everyone would end up in a marriage that they couldn't improve (without a lot of self-help books). Looking around, you can see how successful that's been! I mean, it's used to fill residencies in hospitals and for college admissions too, almost as though it's commonly used when there's one side that really can't do anything about the outcome (hello to all the responders out there). 

To me, though, the most interesting part of it was how the responders, the ones who seemed as though they had power by virtue of getting to have a choice, were only getting to make choices when being asked to do so, which meant they always ended up with their worst possible partner. Wow, they really should have been an asker and shouldn't have waited to get asked! That was my takeaway, at least. Better to be an asker about that quiz next Thursday than just agreeing to having one, right? Also, the quiz is on Thursday.