📜Introduction
In this article, we look at stable marriage, an interesting variation of bipartite matching. According to the Stable Marriage Problem, given N men and N women, marry the men and women so that there are never any two persons of the opposite sex who would prefer to have each other over their existing relationships. Each person(male or female) has ranked all members of the opposite sex in order of preference. If none of these exists, all marriages are deemed to be "stable."
📜Description
Consider the below example.
Let us consider there are two men, M1 and M2, and two women, W1 and W2.
Let M1's list of preference is {W1, W2}
Let m2's list of preference is{W1, W2}
Let w1's list of preference is {M1, M2}
Let w2's list of preference is{M1, M2}
The matching { {M1, W2}, {W1, M2} } isn’t stable because M1 and W1 prefers each other over their current assigned partners.
The matches {M1, W1} and {M2, W2} are stable because no two people of the opposite sex would prefer each other over their assigned partners.
💡Example
Consider a set:
M = {m1, m2, . . . , mn} of n men and,
W = {w1, w2, . . . , wn } of n women.
Each man has a preference list of the women as their preferable marriage partners with no ties allowed. Similarly, each woman has a potential list of men with no ties. Examples of these two sets of lists are given below. An n × n ranking matrix can also present the same information.
The rows and columns of the matrix represent the men and women. A cell in row m and column w contains two rankings: the first is the ranking of w in the m's preference list, while the second is the ranking of m in the w's preference list. For example, it is easier to specify a match of the set elements using the ranking matrix. In contrast, preference lists might be a more efficient data structure for implementing a matching algorithm.
Men’s Preferences Matrix
Order Men |
P1 | P2 | P3 |
m1 | w2 | w1 | w3 |
m2 | w2 | w3 | w1 |
m3 | w3 | w2 | w1 |
Women’s Preferences List
Order Women |
P1 | P2 | P3 |
w1 | m2 | m3 | m1 |
w2 | m3 | m1 | m2 |
w3 | m3 | m2 | m1 |
Ranking Matrix
Women Men |
w1 | w2 | w3 |
m1 | 2,3 | 1,2 | 3,3 |
m2 | 3,1 | 1,3 | 2,1 |
m3 | 3,2 | 2,1 | 1,2 |
A marriage matching M is a collection of n (m, w) pairs, each of whose members is chosen in a one-to-one manner from separate n-element sets Y and X. Each man in Y is paired with precisely one woman in X, and vice versa.
A pair (m, w) is a blocking pair for a marriage matching M if man m and woman w are not matched in M, but they prefer each other to their mates in M. For example, (m1, w2) is a blocking pair for the marriage matching M = {(m1, w1), (m2, w3), (m3, w2)} because they are not matched in M while m1 prefers w2 to w1 and w2 prefers m1 to m2. A marriage matching M is called stable if there is no blocking pair; otherwise, M is called unstable.
Finding a stable marriage that matches the preferences of men and women is difficulty with stable marriages. We have an algorithm to solve this problem i.e., the Gale-Shapley Algorithm.
🤔Gale-Shapley Algorithm
The goal is to cycle through every available free man. Every free man visits every woman on his preference list in the order they are listed. He asks each lady he approaches if she is available, and if she is, they become engaged. If the woman is not free, she can reject him or break off her engagement with the man, depending on her preference. Therefore, a previously established engagement may be broken if a woman has a better option.
⏳Input and Output Type
A 2D matrix of size (2*N)*N is the input, with N being the number of women or men. Men's preference lists are shown in rows from 0 to N-1, and women's preference lists are shown in rows from N to 2*N - 1. Consequently, women are numbered from N to 2*N - 1, while men are numbered from 0 to N-1. The list of married couples is the output.
🧑💻Code
C++
#include <bits/stdc++.h>
using namespace std;
#define N 4
/* This function returns true if woman 'w' prefers man' m1' over man' m' */
bool womenPrefersM1OverM(int prefer[2*N][N], int w, int m, int m1)
{
for (int i = 0; i < N; i++)
{
/* If m1 comes before m in the list of w, then w prefers her
current engagement, don't do anything.*/
if (prefer[w][i] == m1)
return true;
/* If m comes before m1 in w's list, then free her current
engagement and engage her with m.*/
if (prefer[w][i] == m)
return false;
}
return true;
}
void findstableMarriage(int prefer[2*N][N])
{
int women_partner[N];
/* If men_free[i] is false, then man 'i' is free, otherwise engaged. */
bool men_free[N];
/* Initialize all men and women as free */
memset(women_partner, -1, sizeof(women_partner));
memset(men_free, false, sizeof(men_free));
int free_cnt = N;
/* While there are free men */
while (free_cnt > 0)
{
/* Pick the first free man (we could pick any) */
int m;
for (m = 0; m < N; m++)
if (men_free[m] == false)
break;
/* One by one, go to all women according to m's preferences.
Here m is the picked free man.*/
for (int i = 0; i < N && men_free[m] == false; i++)
{
int w = prefer[m][i];
if (women_partner[w-N] == -1)
{
women_partner[w-N] = m;
men_free[m] = true;
free_cnt--;
}
else
{
/* Find current engagement of w */
int m1 = women_partner[w-N];
/* If w prefers m over her current engagement m1,
then break the engagement between w and m1 and
engage m with w.*/
if (womenPrefersM1OverM(prefer, w, m, m1) == false)
{
women_partner[w-N] = m;
men_free[m] = true;
men_free[m1] = false;
}
}
}
}
/* Print the solution */
cout << "Woman Man" << endl;
for (int i = 0; i < N; i++)
cout << " " << i+N << "\t" << women_partner[i] << endl;
}
int main()
{
int ranking[2*N][N] = { {7, 5, 6, 4},
{5, 4, 6, 7},
{4, 5, 6, 7},
{4, 5, 6, 7},
{0, 1, 2, 3},
{0, 1, 2, 3},
{0, 1, 2, 3},
{0, 1, 2, 3},
};
findstableMarriage(ranking);
return 0;
}
Python
N = 4
def womenPrefersM1OverM(prefer, w, m, m1):
for i in range(N):
if (prefer[w][i] == m1):
return True
if (prefer[w][i] == m):
return False
def stableMarriage(prefer):
wPartner = [-1 for i in range(N)]
mFree = [False for i in range(N)]
freeCount = N
# While there are free men
while (freeCount > 0):
# Pick the first free man (we could pick any)
m = 0
while (m < N):
if (mFree[m] == False):
break
m += 1
i = 0
while i < N and mFree[m] == False:
w = prefer[m][i]
if (wPartner[w - N] == -1):
wPartner[w - N] = m
mFree[m] = True
freeCount -= 1
else:
m1 = wPartner[w - N]
if (womenPrefersM1OverM(prefer, w, m, m1) == False):
wPartner[w - N] = m
mFree[m] = True
mFree[m1] = False
i += 1
print("Woman ", " Man")
for i in range(N):
print(i + N, "\t", wPartner[i])
# Driver Code
choice = [[7, 5, 6, 4],
[5, 4, 6, 7],
[4, 5, 6, 7],
[4, 5, 6, 7],
[0, 1, 2, 3],
[0, 1, 2, 3],
[0, 1, 2, 3],
[0, 1, 2, 3]]
stableMarriage(choice)
📚Output

That's it; you have learned one of the most conceptual topics.
Read this, Fibonacci Series in Python