Stable Marriage Problem

The Stable Marriage Problem involves pairing N men and N women, each having ranked all members of the opposite sex by preference. The goal is to form marriages where no two individuals would prefer each other over their assigned partners. If no such pair exists, the marriages are considered stable

Grasping the Concept

Consider two men, m1 and m2, and two women, w1 and w2. Their preference lists are as follows:

• m1 prefers w1 over w2, and m2 prefers w1 over w2.
• w1 prefers m1 over m2, and w2 prefers m1 over m2.

The matching {(m1, w2), (m2, w1)} is not stable because m1 and w1 prefer each other over their assigned partners. In contrast, the matching {(m1, w1), (m2, w2)} is stable, as no two individuals would rather be with each other than their assigned partners.

Examples

Input: A (2N)×N matrix prefer where, N is the number of men or women. Rows 0 to N−1 contain men's preference lists. Rows N to 2N−1 contain women's preference lists. Men are numbered from 0 to N-1 and women are from N to 2N - 1.
Output: A list of married pairs.

Input: prefer = [[3, 4, 5], [4, 3, 5], [3, 5, 4], [1, 0, 2], [2, 1, 0], [0, 1, 2]]
Output: Women Men
3 0
4 1
5 2
Explanation: Man 0 and Woman 3 mutually prefer each other, forming a stable pair. Similarly, Man 1 pairs with Woman 4, and Man 2 is matched with Woman 5, ensuring a stable arrangement.

Input: prefer = [[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]]
Output: Women Men
4 2
5 1
6 3
7 0
Explanation: Each man and woman are paired based on mutual preference. Man 2 is matched with Woman 4, Man 1 with Woman 5, Man 3 with Woman 6, and Man 0 with Woman 7, ensuring a stable pairing.

It is always possible to form stable marriages from lists of preferences. Gale–Shapley algorithm to find a stable matching: 
The idea is to iterating through all free men until none remain. Each man proposes to women in his preference order. If a woman is free, they get engaged. If she is already engaged, she chooses between her current partner and the new proposer based on her preferences. Engagements can be broken if a better match appears. This process guarantees a stable matching, and its time complexity is O(n²).

Finding the Perfect Match

Initialize all men and women to free
while there exist a free man m who still has a woman w to propose to
{
w = m's highest ranked such woman to whom he has not yet proposed
if w is free
(m, w) become engaged
else some pair (m', w) already exists
if w prefers m to m'
(m, w) become engaged
m' becomes free
else
(m', w) remain engaged
}.  

Approach: Using Gale–Shapley algorithm - O(N^2) Time and O(N^2) Space

#include <bits/stdc++.h> using namespace std; // Checks if woman 'w' prefers 'm1' over 'm' bool wPrefersM1OverM(vector<vector<int>> &prefer, int w, int m, int m1) {  int N = prefer[0].size();  for (int i = 0; i < N; i++)  {  // If m1 comes before m, w prefers  // her current engagement  if (prefer[w][i] == m1)  return true;  // If m comes before m1, w prefers m  if (prefer[w][i] == m)  return false;  } } // Implements the stable marriage algorithm vector<int> stableMarriage(vector<vector<int>> &prefer) {  int N = prefer[0].size();  // Stores women's partners  vector<int> wPartner(N, -1);  // Tracks free men  vector<bool> mFree(N, false);  int freeCount = N;  while (freeCount > 0)  {  int m;  for (m = 0; m < N; m++)  if (!mFree[m])  break;  // Process each woman in m's preference list  for (int i = 0; i < N && !mFree[m]; i++)  {  int w = prefer[m][i];  if (wPartner[w - N] == -1)  {  // Engage m and w if w is free  wPartner[w - N] = m;  mFree[m] = true;  freeCount--;  }  else  {  int m1 = wPartner[w - N];  // If w prefers m over her current partner, reassign  if (!wPrefersM1OverM(prefer, w, m, m1))  {  wPartner[w - N] = m;  mFree[m] = true;  mFree[m1] = false;  }  }  }  }  return wPartner; } int main() {  vector<vector<int>> prefer = {  {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},  };  vector<int> wPartner = stableMarriage(prefer);  cout << "Woman Man" << endl;  int N = prefer[0].size();  for (int i = 0; i < N; i++)  cout << " " << i + N << "\t\t" << wPartner[i] << endl;  return 0; } 

import java.util.*; class GfG {  // Checks if woman 'w' prefers 'm1' over 'm'  static boolean wPrefersM1OverM(int prefer[][], int w,  int m, int m1)  {  int N = prefer[0].length;  for (int i = 0; i < N; i++) {  if (prefer[w][i] == m1)  return true;  if (prefer[w][i] == m)  return false;  }  return false;  }  // Implements the stable marriage algorithm  static int[] stableMarriage(int prefer[][])  {  int N = prefer[0].length;  // Stores women's partners  int wPartner[] = new int[N];  // Tracks free men  boolean mFree[] = new boolean[N];  Arrays.fill(wPartner, -1);  int freeCount = N;  while (freeCount > 0) {  int m;  for (m = 0; m < N; m++)  if (!mFree[m])  break;  for (int i = 0; i < N && !mFree[m]; i++) {  int w = prefer[m][i];  if (wPartner[w - N] == -1) {  wPartner[w - N] = m;  mFree[m] = true;  freeCount--;  }  else {  int m1 = wPartner[w - N];  if (!wPrefersM1OverM(prefer, w, m,  m1)) {  wPartner[w - N] = m;  mFree[m] = true;  mFree[m1] = false;  }  }  }  }  return wPartner;  }  public static void main(String[] args)  {  int prefer[][] = { { 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 } };  int N = prefer[0].length;  int[] wPartner = stableMarriage(prefer);  System.out.println("Woman Man");  for (int i = 0; i < N; i++) {  System.out.println(" " + (i + N) + "\t\t"  + wPartner[i]);  }  } } 

def wPrefersM1OverM(prefer, w, m, m1): N = len(prefer[0]) for i in range(N): if prefer[w][i] == m1: return True if prefer[w][i] == m: return False return False # Implements the stable marriage algorithm def stableMarriage(prefer): N = len(prefer[0]) wPartner = [-1] * N # Stores women's partners mFree = [False] * N # Tracks free men freeCount = N while freeCount > 0: m = next(i for i in range(N) if not mFree[i]) for i in range(N): if mFree[m]: break w = prefer[m][i] if wPartner[w - N] == -1: wPartner[w - N] = m mFree[m] = True freeCount -= 1 else: m1 = wPartner[w - N] if not wPrefersM1OverM(prefer, w, m, m1): wPartner[w - N] = m mFree[m] = True mFree[m1] = False return wPartner prefer = [[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]] N = len(prefer[0]) wPartner = stableMarriage(prefer) print("Woman", "Man") for i in range(N): print(i + N, "\t", wPartner[i]) 

using System; class GfG {  // Checks if woman 'w' prefers 'm1' over 'm'  static bool wPrefersM1OverM(int[, ] prefer, int w,  int m, int m1)  {  int N = prefer.GetLength(1);  for (int i = 0; i < N; i++) {  if (prefer[w, i] == m1)  return true;  if (prefer[w, i] == m)  return false;  }  return false;  }  // Implements the stable marriage algorithm  static int[] stableMarriage(int[, ] prefer)  {  int N = prefer.GetLength(1);  int[] wPartner  = new int[N]; // Stores women's partners  bool[] mFree  = new bool[N]; // Tracks availability of men  Array.Fill(wPartner, -1);  int freeCount = N;  while (freeCount > 0) {  int m;  for (m = 0; m < N; m++)  if (!mFree[m])  break;  for (int i = 0; i < N && !mFree[m]; i++) {  int w = prefer[m, i];  if (wPartner[w - N] == -1) {  wPartner[w - N] = m;  mFree[m] = true;  freeCount--;  }  else {  int m1 = wPartner[w - N];  if (!wPrefersM1OverM(prefer, w, m,  m1)) {  wPartner[w - N] = m;  mFree[m] = true;  mFree[m1] = false;  }  }  }  }  return wPartner;  }  public static void Main()  {  int[, ] prefer = { { 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 } };  int N = prefer.GetLength(1);  int[] wPartner = stableMarriage(prefer);  Console.WriteLine("Woman Man");  for (int i = 0; i < N; i++)  Console.WriteLine(  $ " {i + N} {wPartner[i]}");  } } 

// This function returns true if woman 'w' prefers man 'm1' // over man 'm' function wPrefersM1OverM(prefer, w, m, m1) {  let N = prefer[0].length;  // Check if w prefers m over her current engagement m1  for (var i = 0; i < N; i++) {  // If m1 comes before m in 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;  } } // Prints stable matching for N boys and N girls. Boys are // numbered as 0 to N-1. Girls are numbered as N to 2N-1. function stableMarriage(prefer) {  let N = prefer[0].length;  // Stores partner of women. This is our output array  // that stores passing information. The value of  // wPartner[i] indicates the partner assigned to woman  // N+i. Note that the woman numbers between N and  // 2*N-1. The value -1 indicates that (N+i)'th woman is  // free  var wPartner = new Array(N);  // An array to store availability of men. If mFree[i]  // is false, then man 'i' is free, otherwise engaged.  mFree = new Array(N);  // Initialize all men and women as free  wPartner.fill(-1);  mFree.fill(false);  var freeCount = N;  // While there are free men  while (freeCount > 0) {  // Pick the first free man (we could pick any)  var m;  for (m = 0; m < N; m++)  if (mFree[m] == false)  break;  // One by one go to all women according to m's  // preferences. Here m is the picked free man  for (var i = 0; i < N && mFree[m] == false; i++) {  var w = prefer[m][i];  // The woman of preference is free, w and m  // become partners (Note that the partnership  // maybe changed later). So we can say they are  // engaged not married  if (wPartner[w - N] == -1) {  wPartner[w - N] = m;  mFree[m] = true;  freeCount--;  }  else // If w is not free  {  // Find current engagement of w  var m1 = wPartner[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 (wPrefersM1OverM(prefer, w, m, m1)  == false) {  wPartner[w - N] = m;  mFree[m] = true;  mFree[m1] = false;  }  } // End of Else  } // End of the for loop that goes to all women in  // m's list  } // End of main while loop  return wPartner; } var prefer = [  [ 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 ], ]; let N = prefer[0].length; let wPartner = stableMarriage(prefer); console.log("Woman Man"); for (var i = 0; i < N; i++)  console.log(" " + (i + N) + " " + wPartner[i]); 

Woman Man 4	2 5	1 6	3 7	0 

Interesting Facts About the Gale–Shapley Algorithm:

• Originally designed to find the optimal matching between employers and employees based on their preferences.
• The algorithm yields two extreme stable matchings: one favoring women when traversing from the beginning and another favoring men when traversing from the end.
• Often explained using the analogy of marriage proposals, where one group proposes, and the other accepts or rejects based on preference.