Stable Marriage Problem With Unequal Numbers
https://www.hindawi.com/journals/complexity/2018/7409397/
A common application of stable matchings is the stable marriage problem (SMP). This problem deals with finding stable matchings between equal numbers of males and females. The SMP, as proved by David Gale and Lloyd Shapley, shows that with any equal number of men and women, there exists a marriage matching where each matched pair does not prefer another person of the opposite gender over their current partner. This algorithm works by having the males first make a list ranking all of the women. Then, in the first round they propose to the highest ranked woman that is still unengaged. The woman accepts the proposal if the man is their more preferred man, and rejects them otherwise. Then, the process repeats, and the males propose to their second highest raked woman that is still unengaged. This process continues until all people are matched.
In the article linked above, a new strategy for matching couples is discussed. The SMP while useful, is not very practical because it is only able to predict stable matchings for even numbered groups of males and females. This is usually not the case in real life. In the paper, Shi aims to extend the SMP to unequal sized groups, through a simulation of stable marriage matching of groups of N + 1 men and N women. A man has no matching if they are rejected by everyone, meaning that they are ranked last by all women, and therefore would not be able to form a stable matching as there would always be a preferred partner for each woman. The new solution proposes the idea of energy, which represents the relationship between the rankings of the males to the rankings of the females in each matching. The paper finds that by increasing the difference between groups by even 1, the average energy of the active side becomes greatly disadvantageous. This shows that stable matching solutions are very sensitive to changes in the number of people.
I think that this application to unequal sets of nodes in perfect matching scenarios is very interesting, as it demonstrates the complications of modeling real world applications of network theory. The world and the interactions present are so dynamic that ever a change of one can offset the entire average energy and solution of a matching. However, we as complex humans a still so predictable that our behaviors are able to be mapped by models, which is a very intriguing concept.