Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
📜Introduction
2.
📜Description
3.
💡Example
3.1.
Men’s Preferences Matrix 
3.2.
Women’s Preferences List
3.3.
Ranking Matrix
4.
🤔Gale-Shapley Algorithm
4.1.
⏳Input and Output Type
5.
🧑‍💻Code
5.1.
C++
5.2.
Python
5.3.
📚Output
6.
Frequently Asked Questions
6.1.
Which problem is related to the stable marriage problem?
6.2.
What makes stable matching problems unstable?
6.3.
Does a stable matching always exist?
6.4.
What type of graph is used to model the stable marriage problem?
6.5.
Can there be multiple stable matching?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

The Stable Marriage Problem

Author Mayank Goyal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

📜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

output

 

That's it; you have learned one of the most conceptual topics.

Read this, Fibonacci Series in Python

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

Which problem is related to the stable marriage problem?

A stable marriage problem uses the Gale-Shapley algorithm.

What makes stable matching problems unstable?

If a man and a woman in matching M prefer one another to their current companions, the unmatched pair m-w is unstable. An unstable couple m-w might both benefit from getting engaged. Perfect matching with no unstable combinations is known as stable matching.

Does a stable matching always exist?

A stable matching always exists, and the algorithmic problem solved by the Gale–Shapley algorithm is to find one.

What type of graph is used to model the stable marriage problem?

This problem can be easily modelled as a bipartite graph.

Can there be multiple stable matching?

Yes, there can be multiple stable matches. The Gale-Shapley algorithm finds the optimal matching for all elements in the "left set": All elements in the left set will get the best possible partner among all stable matchings.

Conclusion

In this article, we learned about the stable marriage problem in depth with the help of an example. Later, we learned one of the most important algorithms Gale-Shapley algorithm, with the help of the code. 
If you want to learn more, check out our articles on Construct the Full K-ary Tree from its Preorder TraversalRegular and Bipartite graphsWhat Is Web2Py?Why To Use Web2py?Postbacks and Internationalization in web2pyThird Party Modules In Web2pyTasks In Web2py, and  XML in Web2py.

Happy Coding! 

Previous article
Travelling Salesman Problem | Part 2
Next article
Jumping Numbers Smaller Than or Equal to a Given Value
Live masterclass