Soulmates and the Gale-Shapley Algorithm

A few years ago, I read Roth and Sotomayor's Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. The book was very influential on me, my thinking, and ultimately my research and research interests. One of things that I was fascinated to learn about was the Gale-Shapley algorithm, which is a mathematical solution to a problem referring to the "optimal" allocation of men and women paired in marriage. While it has that particular application to marriage, it's been more generally applied to problems in labor economics (employees and employers matched), including the matching of medical residents to hospitals, and college students to their dormitory roommates. Two-sided matching problems are everywhere, so this has general application beyond family and marriage.

The solution goes like this. Assume two types of people who want to be together. Put all of one type into a set called M, with each element being m1, m2, and so on. Put all of the other type into a set called F, with each element of that F set called f1, f2, and so on. Each element, in this example, is a person of gender m (male) or f (female), and they are assumed for simplicity to be heterosexual preferring only to match with elements of the cross-gender set (ie, mf and not mm or ff). Each male has preferences over the females in the F set. Assume there are no ties (ie, he's not indifferent between any two girls - if there are ties, ties are broken by flipping a coin), matches have to be monogamous, and each person completely ranks the other side, and people can end up unmatched. There may be some additional assumptions I'm missing, as it's been several years. The question is: what final allocation will be stable? Stability means that no person in a match will want to and be able to successfully form a new match. So, for instance, assume Archie prefers Betty to Veronica, but is matched with Veronica. Furthermore, assume Betty prefers Archie to Reginald, but is matched with Reginals. This is unstable since Archie prefers Betty and Betty prefers Archie. Therefore, they would dissolve their matches and form a new match, leaving Reginald and Veronoica unmatched for the time being. The solution of this problem should derive a pairing profile of {m,f} matches that is considered "stable" in this sense.

Gale-Shapley devised a simple algorithm. Individuals from one set will ask individuals from the other set to marry them. The receiving party accepts the more preferred offer and rejects the less preferred offer (assuming they receive two) and agrees to an engagement. All rejected individuals then ask their second preferred person for marriage. Individuals receiving new offers then compare their current new offer with their previous old offer, and accept the more preferred offer. All rejected parties ask again in a third round, and this continues until stability is reached. What Gale-Shapley showed is that under some basic assumptions, like the aforementioned ones (but I may be missing some others), the final allocation will be stable. There exists for every marriage matching a stable solution, and it can be reached via the Gale-Shapley algorithm, or what is also called the "deferred acceptance procedure" (Roth and Sotomayor 1992, pp. 27-28).

This, in and of itself, is interesting. But that's not mainly what also interested me. What interested me was that there were multiple stable matches. That is, the allocation that emerged was not unique. It depended, interestingly enough, on whether men did the proposing or women did the proposing. The marriages that emerged when females did the proposing were usually different than when the males did the proposing. So, assume there are two marriage pairing profiles {m,f}_1 and {m,f}_2, where {m,f}_1 is the Gale-Shapley solution when men go first, and {m,f}_2 is the Gale-Shapley solution when females go first. These two expressions define a profile of pairings of each element of M either to another element of F, or goes unmatched (remember, you can end up single in this problem, just like in real life). Each person in the set of M can be shown to weakly prefer {m,f}_1 to the pairings in {m,f}_2. I won't work through that proof, but what it means basically is that he is either going to be with the same person in {m,f}_2, or he is going to end up with someone he prefers worse to the women he is with in {m,f}_1. Good news for the guys. But it's also true for the girls. Women in {m,f}_1 will weakly prefer the profile {m,f}_2. Either they are matched with the same guy in both, or {m,f}_2 will put them with someone they prefer to the man they're matched to in {m,f}_1. Abstractly, that is not surprising when you think about the fact that people have preferences over one another, and they make offers to their more preferred, and defer offers to accept the more preferred ones. Some women never get the offers from their more preferred partner under {m,f}_1 because those men had their offers accepted by women ranked higher than themselves. But had women been given the chance to go first, those men would've received offers, and secondly, some women's offers would've been accepted before the men got to receive the new offers in the subsequent rounds from the women that they prefer.

All this to say. Am I married to the woman who I would've been married to under {m,f}_2? This counterfactual is not possible to answer without information on every single man's preference ordering and every single female's preference ordering. But, it's entirely plausible that had society structured the process of matching differently whereby women asked men on dates, and ultimately asked men to marry them, that I would've ended up with someone else, assuming that I am not my current wife's number one pick. She swears I am, but I'm not sure she can really answer the question herself. Preferences are revealed by actions when a person is faced with a real problem involving decisions. It is not, itself, easy to reveal preferences otherwise. Some would argue that revealed preferences are the only way we can infer preferences at all. So it's not that my wife is lying when she tells me she preferred me to all other men. It's simply that she may not be able to answer the question. Without those competing offers deferred and accepted years leading up to the moment we even met, she may not be able to say one way or another. But it is something I, the economist, think about. It reminds me of complaints of patriarchical sexism that is structured into the fabric of society, for instance, made often by feminists. In the game theoretic sense, we have no way to choose between the M-stable and F-stable pairings. They are both "stable", and stability only means that no one will want to and be able to form a new match because if they could, then the current matching wouldn't be stable. But we have no way to judge which of these better. We could just flip a coin. So why does society dictate men go first? All we can say about this is that we know whoever goes first is generally going to get the better pairing, and therefore whoever is on the receiving end is going to end up paired with people they weakly prefer less to the stable arrangement that emerges had females gone first.