Stable Matching and its Discrepancies
Stable Matching and its Discrepancies
Written by: Aryan Mansingh
There are many topics in game theory, but one of the most basic yet fundamental is the idea of a stable matching. This can be used in a variety of fields from economics to 5G networks, yet is often left hidden just below the surface of what’s known about their use. The basics of this topic, as well as another fundamental game theory topic will be covered in this article.
The marriage problem is one that has been acknowledged for centuries, albeit not directly. The method of pairing two groups of people based on their preferences such that each member pair is no better off with any other person than with their match. It hadn’t even been known if it was possible to get such a matchup, let alone a way to achieve it without failure. However, before understanding how such a solution was found, a simpler concept has to be understood: Nash equilibria.
Every economist knows the concept of Nash equilibria. It’s one of the fundamental ways to predict the actions of set of characters/players by analyzing what the most desirable outcomes are for those players. This concept is commonly displayed by the prisoners dilemma, although it’s applicable in practically any situation where the actions and consequences of those actions are known for any two players. In the prisoners dilemma, there are two prisoners, each of whom can either remain silent or confess about a joint crime. These prisoners are both “logical,” meaning that they will prefer less jail time to more. If both prisoners remain silent, they both are given two years of time. If one prisoner remains silent while the other confesses, then the prisoner that remains silent gets 8 years of time while the one that confesses gets a year in prison. However, if both prisoners confess, then they both get 5 years in prison. Here’s a visual of the problem (Figure 1):
Figure 1
2X2 payoff matrix for the prisoner’s dilemma
Courtesy of: Aryan Mansingh
Looking at the diagram, it seems obvious that both prisoners should remain silent to receive the least possible punishment, right? However, the concept of Nash equilibria proves this wrong. Lets consider this question from prisoner A’s perspective, responding to prisoner B’s choices. if prisoner B decides to remain silent, the prisoner A is better off confessing, since they recieve a year less time. If prisoner B decides to confess, the prisoner A is better off confessing, since they get 3 years less time. So, in either scenario, it’s more beneficial for prisoner A to confess. Because this scenario is symmetrical (prisoner B has the same choices and repercussions as prisoner A), prisoner B will also find it more beneficial to confess. This also leads to the combined jail time between the prisoners. So, even though both prisoners confessing is the least optimal in terms of jail time, they are forced to make that choice, leading to the Nash equilibria. The prisoners simply have no better choice to make.
A stable matching requires a similar idea. Instead of having different characters and analyzing their possible actions, a stable matching is based off the preferences of individuals and pair them accordingly. Here is one possible arrangement of preferences (Figure 2):
Figure 2
Preference layout with w and m representing women and men accordingly
Here, there are three men and three women, with each of them having a preference profile P and their preferences of the opposite gender in order. For example, man 1 (m1) prefers woman 2 (w2) to woman 1 (w1) to woman 3 (w3). Using these preference profiles, a stable matching has to be determined such that there’s no way for any two pairs to switch their pairings to better satisfy their preference profiles. While it may seem difficult to figure out such a matching, David Gale and Lloyd Shapley created an algorithm in 1962 to solve this particular question. While there are many ways to understand how this algorithm works, a flowchart demonstrates it quite simply (Figure 3):
Figure 3
Flow diagram of the Gale-Shapley algorithm
This relatively simple algorithm achieves a stable matching, and applying this algorithm on the proposed scenario gives us this matching:
To show that this works, we can look at each individual case. m1 is matched to w1, even though w1 is his second choice. Why is this? This is because his first choice, w2, prefers m3 over m1, and since there are other conflicts between m3’s more preferred choices, he is matched with w2. This can be can be demonstrated for any given pair, there’s always another one that’s preventing both players from switching. This algorithm was quite useful when it was made, as it was used to connect students to medical schools in a similar fashion. However, there’s something to note. The women get much better preferences than the men do, and this is no accident. The men get their 2nd, 3rd, and 2nd choices, while the women get their 1st, 1st, and 2nd choices respectively; this is far better than what the men got. This is because there can be multiple stable matchings for the same preference profiles. The man favorable stable matching is as follows:
If tested, this is also a stable matching. However, the men here get their 1st, 3rd, and 1st choices while the women get their 3rd, 2nd, and 2nd choices respectively. While this may not seem like too large of a problem, in practical application, it made a huge difference. When this algorithm was originally used to match medical students with potential schools, the different stable matchings were never acknowledged, often being favorable to schools rather than the students. This was eventually addressed by Alvin Roth in 1996, who made developments to the Gale-Shapley algorithm and proposed a solution while addressing the matching process as a labor market. Only then was the matching process fixed.
Yet, this only covers one discrepancy in the Gale-Shapley algorithm, and there are several more that exist. Alvin Roth has done the difficult work, though, and compiled various properties and their applications in his paper “Deferred Acceptance Algorithms: History, Theory, Practice and Open Questions.” While this article covers just the surface of stable matching and Nash equilibria, game theory is a vast field that goes far deeper into the analysis of player interactions, a field that still remains under-appreciated to this day.
Sources
Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9–15. https://doi.org/10.1080/00029890.1962.11989827
Osborne, M. (2004). An introduction to game theory. New York: Oxford University Press.
Rostom, M., Abd El-Malek, A., Abo-Zahhad, M., & Elsabrouty, M. (2022). A two-stage matching game and repeated auctions for users admission and channels allocation in 5G HetNets. IEEE Access, P