Back in my undergraduate days, I studied theoretical computer science…you know, algorithms and such. I have to admit that I don’t use most of what I learned, and much of it is in fact very fuzzy by now. That said, there are random concepts that come forth as still being relevant. For example, market design has become an increasingly popular topic in economics, and what better market to study than the dating market? Consider the following algorithm:
First, a definition…a stable match is an assignment where there are no rogue couples, i.e. that no individual has another person that they like better than their current mate that also likes them better than the person they are with. Intuitively, we could say that there isn’t going to be any adultery or something like that.
Now, the process:
1. Each male and female comes up with a rank ordering of all of the members of the opposite sex. (This matching becomes more complicated if we consider same sex couples.)
2. Each day, the girls go out and stand on the balconies of their apartments. Each guy goes and stands beneath the balcony of the girl that he likes best that hasn’t rejected him yet. (In other words, the guys work progressively down their lists until they don’t get rejected any more.)
3. The girls take a look at the guys below their balconies, and each picks the highest ranked one and tells him to come back the next day (which by construction he will). She rejects all of the other guys.
4. This process repeats. If there are an equal number of men and women, the process will repeat until each girl has exactly one guy at her balcony, and she will marry that guy.
This process results in a stable matching of partners. Now, this seems great for the girls, right? Not quite…
Another definiton: a person’s realm of possibility is the set of people that the person could be paired with in a stable matching.
Not surprisingly, each guy gets matched with the highest ranked girl in his realm of possibility, since he just works his way down the list in order. In technical terms, the resulting matching is optimal for guys. However, the matching is also pessimal for girls! Furthermore, girls (but not guys) could do better by lying about their preferences. So the algorithm is also not strategy-proof for the girls.
Clearly, the context of this algorithm could be extended to college admissions, medical resident matches, etc. Nevertheless, it is an important less to you ladies out there to not just sit there and wait for guys to come to your balcony!
For a more rigorous treatment, see here.
I find it interesting that this algorithm assumes that men and women have perfect information about all the members of the opposite sex and that their preferences don’t change over time. What would happen if these assumptions were relaxed? Stay tuned, perhaps…