# Instability in Stable Marriage Problem: Matching Unequally Numbered Men and Women

Authors: Gui-Yuan Shi; Yi-Xiu Kong; Bo-Lun Chen; Guang-Hui Yuan; Rui-Jie Wu
Journal: Complexity
 (2018)

---

## Abstract

The goal of the stable marriage problem is to match by pair two sets composed by the same number of elements. Due to its widespread applications in the real world, especially the unique importance to the centralized matchmaker, a very large number of questions have been extensively studied in this field. This article considers a generalized form of the stable marriage problem, where different numbers of men and women need to be matched pairwise and the emergence of single men or women is inevitable. Theoretical analysis and numerical simulations confirm that even a small deviation on the number of men and women from the equality condition can have a large impact on the matching solution of the Gale-Shapley algorithm. These results provide insights to many of the real-world applications when matching two sides with an unequal number.


---

## Body

## 1. Introduction

The stable marriage problem (SMP) consists in matching men and women by pairs. By extension, this problem can consist in the matching of two groups composed of different elements. For instance, there are extensive applications in college admissions [1], labor markets [2], and many other social systems [3]. The recent advances in Internet technology have introduced the SMP into new applications: assigning a large number of users to internet server [4], matching peers in a P2P network according to preference [5], the resource allocation in 5G networks [6], or the matching mechanism of real-world dating website [7].Many researchers studied the algorithms and properties on this fascinating and practical problem. The study of the SMP started in 1962 with the Gale-Shapley (G-S) algorithm [1]. This algorithm matches men and women with the guarantee that there is always a stable match for an equal number of men and women [8]. In 2012, the Nobel Prize in Economics was awarded to Lloyd S. Shapley and Alvin E. Roth for “the theory of stable allocations and the practice of market design.” In this algorithm, each man ranks women separately, from his favorite to his least favorite. Then, each man who is still single issues a proposal to the highest woman in his list who has not rejected him yet. The woman then decides to accept or reject him, by retaining only the man who is the most desirable to her. This solution is proved to be one of the stable men-optimal solutions.Besides mathematicians and computer scientists, statistical physicists are also interested in this issue [9, 10]. Indeed, statistical physics is used to treat the problem with a large number of particles, which is also well-suited to treat the SMP. The mean field theory was applied to calculate satisfaction of both men and women in the stable marriage problem, and it was found that men, who are the active side, were far happier than women [11]. This method can also be used to estimate the number of stable solutions [12, 13]. The replica method used in spin glass was applied to study the global optimal solution in bipartite matching, although this is not a stable solution [14–17]. In addition, some interesting varied variations have been studied, such as the impact of matching on the matching of partial information [18, 19], spatial distribution, intrinsic fitness [20], and acceptance threshold [13].So far, mainstream research has been focusing on the matching of the equal number of the two sides. In fact, however, real-world matching problems are seldom a match of a precisely equal size of two sides. We have seen many examples in daily life, the student admission, job market, the recent “one to one poverty alleviation program” policy promoted by the Chinese government, or even the real application of SMP: the marriage matching on dating website [7]. These problems are mostly matching between different numbers of elements on both sides. We are curious to know whether the original stable solution of the Gale-Shapley algorithm can be applied to these unequal size-matching problems and, if not, how would the stable solution of matching be changed? What is the overall happiness of all agents in the stable solution? Here, in this paper, we extend the stable marriage problem to a generalized stable marriage problem (GSMP), which represents a matching between any given sizes of the two sides. Dzierzawa and Oméro [13] implemented the numerical simulation to test the matching result of N+1 men and N women, and their simulation shows that in this case, women are far happier than men according to the Gale-Shapley algorithm. This is hugely different from what the original SMP stable solution suggests. This is crucial because it reveals that the Gale-Shapley solution is very sensitive to even the smallest variation in the number of people and actually cannot be directly used to analyze many unequal size-matching problems. We further thoroughly study the stable solution in GSMP, a matching between any number of men and women. We carry out a theoretical analysis of the stable solution for GSMP and obtain the average happiness for men and women for any given population, and the result is in perfect match with the numerical simulations.


## 2. Methods

We start with the classical scenario withN male and M females to match pairwise. Here, we assume that everyone knows all people from the opposite gender and that there is a wish list for each person which represents the ranking of all persons from the other gender to her/his preference. Following previous research models [11, 13, 17], a reasonable and simple assumption is that all wish lists are randomly established and irrelevant. We define an energy function for each person, which is equal to the ranking of their eventual partner in their wish list. The lower energy one has, the happier the person is. When N=M, it is the conventional SMP. Here, we extend the SMP to groups with different sizes. When N≠M, obviously, there will be some people who will remain single. For these persons, their energy is defined as one worse than the bottom of the wish list; that is to say, the energy is M+1 for single men and N+1 for women. Since the number of single persons is obvious, the result of the calculation can be simply converted for other definitions. Here, we use Greek letters to represent men and Latin letters to represent women. Their energy is denoted as em and ew for men and women, respectively.The G-S algorithm runs as follows: unengaged men will continue to send proposals to women, and women keep the one she prefers between the suitor and her provisional partner. The process stops when no man issues proposal again, either all men are engaged or the unengaged men are rejected by everyone. ForN≤M, this means that all men are engaged. For the case of N>M, M men are engaged and the remaining N−M men are still single.


## 3. Result and Discussion

The stable marriage problem of the equal size of the two sides has been thoroughly studied by many previous researches. ForM=N, several studies have proved that in the stable solution of G-S the algorithm, the average energy of men is ϵm¯=logN, and the average energy of women is ϵw¯=N/logN.


### 3.1. Matching forM>N

#### 3.1.1. The Average Energy of Men

First, let us consider the situation that the number of womenM is larger than the number of men N. During the process of men proposing to women, we notice the following: (1) the total energy of men is equal to the number of proposals men have already sent. (2) Once a woman is engaged, she will remain engaged (perhaps with different men) forever; that is to say, the number of partners will never decrease.Now, we focus on the number of matched pairs in the proposing process; when it reaches toN, every man has already been assigned to a partner and the proposal process stops. When the number of matched pairs is K, there are M−K women who remain unengaged. If one proposal is sent to an engaged woman, no matter the suitor or the woman’s current provisional partner wins, the number of matched pairs will not change. If a proposal is sent to an unengaged woman, which has a probability of M−K/M, the number of matched pairs will increase to K+1. It is easy to deduce that on average M/M−K, proposals have to be sent to match one more pair.Thus, in order to increase the number of matched pairs from0 to N, the expected total number of proposals men have to send is
(1)LN,M=∑K=0N−1MM−K=M∑i=1M1i−∑j=1M−N1j.Hence, the average energy of men whenM>N is
(2)ϵm¯=LN,MN=MNlnMM−N.


#### 3.1.2. The Average Energy of Women

To obtain the average energy of womenϵ¯w, let us consider the final stable solution, in which everyone’s partner has been determined. Let us assume a chosen woman who was finally paired with the man ranked β in her list, so men who ranked higher than β in her list did not issue a proposal to her. According to the ranking of the men in the women’s list, let us denote the men’s energy as follows: ϵ¯mα,α∈1,2,⋯,N. The men who ranked in the top β−1 in the woman’s list must have a better partner than the woman, which means the energy of the woman is higher than that of the assigned partners of these men. This is because if the rank of the lady in a certain men’s list is less than the energy value of the man, then he must have already issued a proposal to the woman according to the G-S Algorithm, thus causing a conflict. We can compute the probability of a woman matched with the man ranked β in her list:
(3)Pβ=∐α=1β−11−ϵmαM∗ϵmβM.The energy of the single women is equal toN+1. They did not receive any proposal; the probability is:
(4)PN+1=∏α=1N1−ϵmαM.Similarly, we useϵm¯ to replace ϵmα; then we have
(5)Pβ=1−ϵm¯Mβ−1∗ϵm¯M,PN+1=1−ϵm¯MN.Considerϵw¯=∑β∗pβ; we can estimate the average energy of women:
(6)ϵw¯=ϵm¯M∑i=1Ni∗1−ϵm¯Mi−1+N+1∗1−ϵm¯MN.The summation of the series gives(7)ϵw=ϵm¯M1−1−ϵm¯/MNϵm¯/M2+1−ϵm¯MN.Since we haveϵm¯=M/NlnM/M−N, 1−ϵm¯/MN approximately is equal to M−N/M.
(8)ϵw¯=Nϵm¯+M−NM,and also we can see
(9)ϵw¯∗ϵm¯≃N.


### 3.2. Matching forM<N

#### 3.2.1. The Average Energy of Women

WhileM<N, let us denote the energy of each woman as ϵi, and the average of ϵi is denoted by ϵw¯.In the final matching state, all the women are matched butN−M men are left single. The probability of a man being single is ∏i=1M1−ϵi/N; i.e., he is ranked lower than any of the current partner in women’s lists. In total, we have N−M men who are single, which means the probability of being single is N−M/N, so we have
(10)∏i=1M1−ϵiN=N−MN.Approximately, we useϵw¯ to replace ϵi,
(11)1−ϵw¯NM=N−MN,by taking the logarithm of both sides; we have
(12)ϵw¯=NMlnNN−M.


#### 3.2.2. The Average Energy of Men

Let us consider the final stable state of matching which we know the exact matching result of everyone. For any chosen man, we denote the energy of women in his list asϵwj,j∈1,2,…,M. Then we have the probability that he was accepted by the woman ranked ith in his list:
(13)Qi=∏j=1i−11−ϵwjNϵwiN.And the probability that he was rejected by all women is (we assume the energy of each single men isM+1)
(14)QM+1=∏j=1M1−ϵwjN.We can approximateϵwj with the mean value ϵw¯, when N is large. By averaging over i, we obtain:
(15)ϵm¯=∑i=1Mi1−ϵw¯Ni−1ϵw¯N+M+11−ϵw¯NM,ϵm¯=ϵw¯N1−1−ϵw¯/NMϵw¯/N2+1−ϵw¯NM,since 1−ϵw¯/NM=N−M/N; we have
(16)ϵw¯ϵm¯−N−MM=M.


### 3.3. Numerical Simulations

The simulation result is shown in Figure1. Without the loss of generality, we fix the number of men equal to 1000 and vary the number of women M from 1 to 2000. Under our definition of single’s energy, as our theoretical result predicted, the average energy of men increases in the beginning and almost saturate when M reaches around 700. The energy plateau is mainly caused by the fact that we set the energy of single men at M+1. Although other definitions may apply, we choose this definition out of many reasonable ones to make the theoretical analysis easier. It is notable that the average energy is low when M is close to 1. It is instructive to many social phenomena. When there are too few women (M close to 1), most men end up single in the matching. But the feeling of happiness, as written by sociologist Ruut Veenhoven [21], “results from comparison” may come from the relative comparison among surroundings, so that the overall happiness which is low may not be a surprising outcome.Figure 1
The average energy ofN men and M women versus the number of women M, where N is set to 1000. The result is obtained by averaging over 100 realizations. The dots and their error bars represent the simulations results and the standard deviation, respectively. The solid lines represent our theoretical predictions.The energies of both men and women have dramatic changes whenM approaches 1000. The energy of men has a sharp drop in this region while the energy of women experiences a big rise. The energies of the active side and passive side exchange their positions. As M increases, the energy of men continues to decrease; at the meantime, the energy of women keeps growing which is natural for the situation that more women compete for a certain number of men. In total, our simulation result verified our previous theoretical analysis.For many of the actual matching problems, the change in the number of people’s happiness is not as sensitive to the theoretical predictions. This may be due to some intrinsic factors: appearance, test scores, university rankings, work ability, salary level, and so on, which will cause the wish list to become relevant. One of our studies recently [22] reveals that the correlation of the people’s wish lists can significantly reduce the inherent instability of the G-S algorithm in the generalized group size case.


## 3.1. Matching forM>N

### 3.1.1. The Average Energy of Men

First, let us consider the situation that the number of womenM is larger than the number of men N. During the process of men proposing to women, we notice the following: (1) the total energy of men is equal to the number of proposals men have already sent. (2) Once a woman is engaged, she will remain engaged (perhaps with different men) forever; that is to say, the number of partners will never decrease.Now, we focus on the number of matched pairs in the proposing process; when it reaches toN, every man has already been assigned to a partner and the proposal process stops. When the number of matched pairs is K, there are M−K women who remain unengaged. If one proposal is sent to an engaged woman, no matter the suitor or the woman’s current provisional partner wins, the number of matched pairs will not change. If a proposal is sent to an unengaged woman, which has a probability of M−K/M, the number of matched pairs will increase to K+1. It is easy to deduce that on average M/M−K, proposals have to be sent to match one more pair.Thus, in order to increase the number of matched pairs from0 to N, the expected total number of proposals men have to send is
(1)LN,M=∑K=0N−1MM−K=M∑i=1M1i−∑j=1M−N1j.Hence, the average energy of men whenM>N is
(2)ϵm¯=LN,MN=MNlnMM−N.


### 3.1.2. The Average Energy of Women

To obtain the average energy of womenϵ¯w, let us consider the final stable solution, in which everyone’s partner has been determined. Let us assume a chosen woman who was finally paired with the man ranked β in her list, so men who ranked higher than β in her list did not issue a proposal to her. According to the ranking of the men in the women’s list, let us denote the men’s energy as follows: ϵ¯mα,α∈1,2,⋯,N. The men who ranked in the top β−1 in the woman’s list must have a better partner than the woman, which means the energy of the woman is higher than that of the assigned partners of these men. This is because if the rank of the lady in a certain men’s list is less than the energy value of the man, then he must have already issued a proposal to the woman according to the G-S Algorithm, thus causing a conflict. We can compute the probability of a woman matched with the man ranked β in her list:
(3)Pβ=∐α=1β−11−ϵmαM∗ϵmβM.The energy of the single women is equal toN+1. They did not receive any proposal; the probability is:
(4)PN+1=∏α=1N1−ϵmαM.Similarly, we useϵm¯ to replace ϵmα; then we have
(5)Pβ=1−ϵm¯Mβ−1∗ϵm¯M,PN+1=1−ϵm¯MN.Considerϵw¯=∑β∗pβ; we can estimate the average energy of women:
(6)ϵw¯=ϵm¯M∑i=1Ni∗1−ϵm¯Mi−1+N+1∗1−ϵm¯MN.The summation of the series gives(7)ϵw=ϵm¯M1−1−ϵm¯/MNϵm¯/M2+1−ϵm¯MN.Since we haveϵm¯=M/NlnM/M−N, 1−ϵm¯/MN approximately is equal to M−N/M.
(8)ϵw¯=Nϵm¯+M−NM,and also we can see
(9)ϵw¯∗ϵm¯≃N.


## 3.1.1. The Average Energy of Men

First, let us consider the situation that the number of womenM is larger than the number of men N. During the process of men proposing to women, we notice the following: (1) the total energy of men is equal to the number of proposals men have already sent. (2) Once a woman is engaged, she will remain engaged (perhaps with different men) forever; that is to say, the number of partners will never decrease.Now, we focus on the number of matched pairs in the proposing process; when it reaches toN, every man has already been assigned to a partner and the proposal process stops. When the number of matched pairs is K, there are M−K women who remain unengaged. If one proposal is sent to an engaged woman, no matter the suitor or the woman’s current provisional partner wins, the number of matched pairs will not change. If a proposal is sent to an unengaged woman, which has a probability of M−K/M, the number of matched pairs will increase to K+1. It is easy to deduce that on average M/M−K, proposals have to be sent to match one more pair.Thus, in order to increase the number of matched pairs from0 to N, the expected total number of proposals men have to send is
(1)LN,M=∑K=0N−1MM−K=M∑i=1M1i−∑j=1M−N1j.Hence, the average energy of men whenM>N is
(2)ϵm¯=LN,MN=MNlnMM−N.


## 3.1.2. The Average Energy of Women

To obtain the average energy of womenϵ¯w, let us consider the final stable solution, in which everyone’s partner has been determined. Let us assume a chosen woman who was finally paired with the man ranked β in her list, so men who ranked higher than β in her list did not issue a proposal to her. According to the ranking of the men in the women’s list, let us denote the men’s energy as follows: ϵ¯mα,α∈1,2,⋯,N. The men who ranked in the top β−1 in the woman’s list must have a better partner than the woman, which means the energy of the woman is higher than that of the assigned partners of these men. This is because if the rank of the lady in a certain men’s list is less than the energy value of the man, then he must have already issued a proposal to the woman according to the G-S Algorithm, thus causing a conflict. We can compute the probability of a woman matched with the man ranked β in her list:
(3)Pβ=∐α=1β−11−ϵmαM∗ϵmβM.The energy of the single women is equal toN+1. They did not receive any proposal; the probability is:
(4)PN+1=∏α=1N1−ϵmαM.Similarly, we useϵm¯ to replace ϵmα; then we have
(5)Pβ=1−ϵm¯Mβ−1∗ϵm¯M,PN+1=1−ϵm¯MN.Considerϵw¯=∑β∗pβ; we can estimate the average energy of women:
(6)ϵw¯=ϵm¯M∑i=1Ni∗1−ϵm¯Mi−1+N+1∗1−ϵm¯MN.The summation of the series gives(7)ϵw=ϵm¯M1−1−ϵm¯/MNϵm¯/M2+1−ϵm¯MN.Since we haveϵm¯=M/NlnM/M−N, 1−ϵm¯/MN approximately is equal to M−N/M.
(8)ϵw¯=Nϵm¯+M−NM,and also we can see
(9)ϵw¯∗ϵm¯≃N.


## 3.2. Matching forM<N

### 3.2.1. The Average Energy of Women

WhileM<N, let us denote the energy of each woman as ϵi, and the average of ϵi is denoted by ϵw¯.In the final matching state, all the women are matched butN−M men are left single. The probability of a man being single is ∏i=1M1−ϵi/N; i.e., he is ranked lower than any of the current partner in women’s lists. In total, we have N−M men who are single, which means the probability of being single is N−M/N, so we have
(10)∏i=1M1−ϵiN=N−MN.Approximately, we useϵw¯ to replace ϵi,
(11)1−ϵw¯NM=N−MN,by taking the logarithm of both sides; we have
(12)ϵw¯=NMlnNN−M.


### 3.2.2. The Average Energy of Men

Let us consider the final stable state of matching which we know the exact matching result of everyone. For any chosen man, we denote the energy of women in his list asϵwj,j∈1,2,…,M. Then we have the probability that he was accepted by the woman ranked ith in his list:
(13)Qi=∏j=1i−11−ϵwjNϵwiN.And the probability that he was rejected by all women is (we assume the energy of each single men isM+1)
(14)QM+1=∏j=1M1−ϵwjN.We can approximateϵwj with the mean value ϵw¯, when N is large. By averaging over i, we obtain:
(15)ϵm¯=∑i=1Mi1−ϵw¯Ni−1ϵw¯N+M+11−ϵw¯NM,ϵm¯=ϵw¯N1−1−ϵw¯/NMϵw¯/N2+1−ϵw¯NM,since 1−ϵw¯/NM=N−M/N; we have
(16)ϵw¯ϵm¯−N−MM=M.


## 3.2.1. The Average Energy of Women

WhileM<N, let us denote the energy of each woman as ϵi, and the average of ϵi is denoted by ϵw¯.In the final matching state, all the women are matched butN−M men are left single. The probability of a man being single is ∏i=1M1−ϵi/N; i.e., he is ranked lower than any of the current partner in women’s lists. In total, we have N−M men who are single, which means the probability of being single is N−M/N, so we have
(10)∏i=1M1−ϵiN=N−MN.Approximately, we useϵw¯ to replace ϵi,
(11)1−ϵw¯NM=N−MN,by taking the logarithm of both sides; we have
(12)ϵw¯=NMlnNN−M.


## 3.2.2. The Average Energy of Men

Let us consider the final stable state of matching which we know the exact matching result of everyone. For any chosen man, we denote the energy of women in his list asϵwj,j∈1,2,…,M. Then we have the probability that he was accepted by the woman ranked ith in his list:
(13)Qi=∏j=1i−11−ϵwjNϵwiN.And the probability that he was rejected by all women is (we assume the energy of each single men isM+1)
(14)QM+1=∏j=1M1−ϵwjN.We can approximateϵwj with the mean value ϵw¯, when N is large. By averaging over i, we obtain:
(15)ϵm¯=∑i=1Mi1−ϵw¯Ni−1ϵw¯N+M+11−ϵw¯NM,ϵm¯=ϵw¯N1−1−ϵw¯/NMϵw¯/N2+1−ϵw¯NM,since 1−ϵw¯/NM=N−M/N; we have
(16)ϵw¯ϵm¯−N−MM=M.


## 3.3. Numerical Simulations

The simulation result is shown in Figure1. Without the loss of generality, we fix the number of men equal to 1000 and vary the number of women M from 1 to 2000. Under our definition of single’s energy, as our theoretical result predicted, the average energy of men increases in the beginning and almost saturate when M reaches around 700. The energy plateau is mainly caused by the fact that we set the energy of single men at M+1. Although other definitions may apply, we choose this definition out of many reasonable ones to make the theoretical analysis easier. It is notable that the average energy is low when M is close to 1. It is instructive to many social phenomena. When there are too few women (M close to 1), most men end up single in the matching. But the feeling of happiness, as written by sociologist Ruut Veenhoven [21], “results from comparison” may come from the relative comparison among surroundings, so that the overall happiness which is low may not be a surprising outcome.Figure 1
The average energy ofN men and M women versus the number of women M, where N is set to 1000. The result is obtained by averaging over 100 realizations. The dots and their error bars represent the simulations results and the standard deviation, respectively. The solid lines represent our theoretical predictions.The energies of both men and women have dramatic changes whenM approaches 1000. The energy of men has a sharp drop in this region while the energy of women experiences a big rise. The energies of the active side and passive side exchange their positions. As M increases, the energy of men continues to decrease; at the meantime, the energy of women keeps growing which is natural for the situation that more women compete for a certain number of men. In total, our simulation result verified our previous theoretical analysis.For many of the actual matching problems, the change in the number of people’s happiness is not as sensitive to the theoretical predictions. This may be due to some intrinsic factors: appearance, test scores, university rankings, work ability, salary level, and so on, which will cause the wish list to become relevant. One of our studies recently [22] reveals that the correlation of the people’s wish lists can significantly reduce the inherent instability of the G-S algorithm in the generalized group size case.


## 4. Conclusion

In summary, we extend the study of the conventional stable marriage problem to groups with different numbers of persons. This study has a realistic impact because the numbers of matching parties are often different in many scenarios in the real world and the losers of the competition are widespread. For the traditionalN men-M women matching problem, it is widely accepted that the Gale-Shapley algorithm leads to a matching result in which the active side occupies a huge advantage. However, we find that even by reducing only one woman, the men of the active side become obviously disadvantageous, which means that original stable matching solution is super sensitive to changes in the number of matching members.In this paper, we thoroughly study the matching solution of unequally sized stable marriage problem and provide both a theoretical solution and numerical simulations. These findings help to further understand the structure and properties of the SMP solution; it also sheds a light on the matching process of matchmakers or resource allocators who deal with many of the real bipartite matching problems with scarcity of one side.



---

*Source: 7409397-2018-09-05.xml*