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]);
Output
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.