Stable Marriage Problem Solution

The Stable Marriage Problem is a problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. It has applications in mathematics, economics and computer science.
Let’s discuss the problem, provide an algorithm to solve it, and implement the solution in C++.

Problem

Find a stable matching between two equally sized sets of elements, traditionally referred to as ‘men’ and ‘women’. Each man and woman have preferences for members of the other set, and the goal is to pair them up such that there are no pairs who would both prefer to be with each other rather than their current partners.

Greedy Approach – Gale–Shapley algorithm

We could solve this problem using Gale–Shapley algorithm. Gale–Shapley algorithm, also known as the deferred acceptance algorithm, is a greedy algorithm for finding a solution to the stable matching problem. It is named for David Gale and Lloyd Shapley, who published it in 1962. Shapley and Alvin E. Roth won the 2012 Nobel Prize in Economics for work including this algorithm.

The algorithm works as follows:

1. Each man proposes to his most preferred woman who hasn’t rejected him yet.
2. Each woman considers all her suitors and chooses the one she prefers the most, rejecting all others.
3. Rejections and proposals continue until each man is either rejected by all women or engaged to one woman.
4. The resulting pairings are stable if there are no pairs (m, w) and (m’, w’) such that m prefers w’ to w and w’ prefers m to m’.

Pseudocode

stableMarriage (manPrefs, womanPrefs):
    
    while there exists an unengaged or free man m:
        woman w = m's highest ranked woman to whom he hasn’t proposed yet

        if w is not engaged:
            pair m and w
        else if w prefers m to her current partner m’:
            pair m and w, 
            reject the current partner m’,
            m‘ becomes free
        else:
            nothing happens

Code Implementation

//
//  main.cpp
//  Stable Matching Problem (Gale-Shapley algorithm)
//
//  Created on 19/03/24.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;


vector<int> stableMarriage(const vector<vector<int>>& manPrefs, const vector<vector<int>>& womanPrefs) {
    int n = (int) manPrefs.size();
    
    vector<int> match(n, -1); // Stores the matched man for each woman, -1 means unengaged
    vector<bool> engaged(n, false); // Indicates whether a man is engaged
    
    // Queue to store the list of free men
    queue<int> freeMen;
    for (int i = 0; i < n; i++) freeMen.push(i);
    
    while (!freeMen.empty()) {
        
        int man = freeMen.front(); // Index of the unengaged man
        freeMen.pop();
        
        // Find the best woman based on the man's preference list who has not rejected him
        for (int i = 0; i < n && !engaged[man]; i++) {
            
            int woman = manPrefs[man][i]; // man's most preferred woman
            
            // if the man's current preferred woman is unengaged
            if (match[woman] == -1) {
                match[woman] = man; // Engage the man to the woman
                engaged[man] = true;
            } else {
                int prevMatchedMan = match[woman];
                
                //if woman prefer current "man" over previously matched man
                if (find(womanPrefs[woman].begin(), womanPrefs[woman].end(), man) <
                 find(womanPrefs[woman].begin(), womanPrefs[woman].end(), prevMatchedMan)) {

                    match[woman] = man; // Engage the current man to the woman
                    engaged[man] = true;
                    
                    engaged[prevMatchedMan] = false; // Break the engagement with previous man
                    freeMen.push(prevMatchedMan);
                }
            }
        }
    }
    
    return match;
}

int main() {
    
    vector<vector<int>> menPrefs = {
        {1, 0, 2, 3},
        {3, 1, 0, 2},
        {0, 2, 1, 3},
        {1, 3, 2, 0}
    };
    vector<vector<int>> womenPrefs = {
        {0, 1, 2, 3},
        {1, 2, 3, 0},
        {2, 3, 0, 1},
        {3, 0, 1, 2}
    };
    
    vector<int> pairs = stableMarriage(menPrefs, womenPrefs);
    
    cout << "Stable pairings:" << endl;
    for (int i = 0; i < pairs.size(); i++) {
        cout << "Woman " << i << " is paired with Man " << pairs[i] << endl;
    }
    
    return 0;
}

Output

Stable pairings:
Woman 0 is paired with Man 0
Woman 1 is paired with Man 3
Woman 2 is paired with Man 2
Woman 3 is paired with Man 1

Time complexity: O(n²), n is the number of men or women
Auxiliary Space: O(n)

Explanation

The time complexity of the Gale-Shapley algorithm for the Stable Marriage Problem is O(n²). This is because in the worst case, each man may propose to each woman once, resulting in O(n²) proposals.

The space complexity of the solution is O(n). This is because we use additional arrays of size n to store information about engagements and matched proposals.

Here’s a step by step code run: Stable Marriage Problem