Gale Shapley algorithm

Gale Shapley algorithm is used to solve the stable matching problem. It is also known as the Deferred Acceptance algorithm.

Stable Matching Problem

Stable Matching Problem (also known as Stable Marriage Problem) is the problem to find stable matching between two equally sized sets. The matching is based on the given order of preferences. A matching from one set to the other set is a bijection. Every element in one set is paired with an element in the other set.

Let (A, B) be two matched pairs. A belongs to the first set and B belongs to the second set. (A, B) is an not stable match if

  1. There is an element X in the first set that prefers B more than A prefers B and
  2. B also prefers X more than it prefers A.

OR

  1. There is an element Y in the second set that prefers A more than B prefers A and
  2. A also prefers Y more than it prefers B.

Gale Shapley algorithm forms matching between elements of the two set such that every matched pair is stable.

To make things simpler, we will define the Stable Matching Problem as a problem to engage N men and N women. We define the problem as

Given N men and N women with their preferences of members of the opposite sex. We need to match each man with a woman such that all matched pairs are stable.

Steps

  1. Each unengaged man proposes to the woman he prefers the most to whom he has not proposed yet.
  2. If a man proposes to an unengaged woman then both the man and woman are engaged to each other.
  3. If a man proposes to a woman who is already engaged, then the woman checks who she prefers more. If the woman prefers the new man over her currently engaged man, then the woman breaks her engagement with the currently engaged man and is now engaged to the new man. The man to whom the woman was previously engaged becomes unengaged.
  4. The above steps are repeated until everyone is engaged.

Prove that everyone is engaged at the end of algorithm

At the end of the algorithm, all men and women will be engaged. This is because each woman will eventually be proposed by atleast one man, thus every woman will be engaged to someone.

Prove all matching pairs are Stable

We will show that all pairs formed by Gale Shapley algorithm are stable. Refer to the previous section to understand what a stable pair is.

Let (John, Lucy) and (Tim, Lia) be two matched pairs obtained on completion of the Gale Shapley algorithm. It is not possible for John and Lia to prefer each other over their current partner. If John prefers Lia over Lucy, then John would have proposed to Lia before Lucy. John and Lia not being married indicate that Lia dumbed John over someone she prefers more, that is Tim. Similarly, if you assume Lia prefers John more than Tim. John and Lia not being engaged mean John never proposed to Lia. That means John is already engaged to a girl who he prefers more than he prefers Lia. Thus, we conclude that all matched pairs are stable.

Program to Implement Gale Shapley algorithm

In this section, we will discuss how to implement Gale Shapley algorithm.

Input

The input consists of two N X N matrices – manPref and womanPref. Each row of manPref is a list of preferences of women. Similarly, each row of womenPref is a list of preferences of men. The men/women that appear first in the list are preferred over those that appear last.

For example,

\\*Man = \{m_1,m_2,m_3 \} \newline \\*Woman = \{w_1,w_2,w_3 \} \newline \\*manPref = \begin {bmatrix}3 \; 2 \; 1 \\*1 \; 3 \; 2 \\*1 \; 2 \; 3 \\*\end {bmatrix}\newline \\*The\; preference\; list\; for\; man:\newline \\*m_1: w_3 > w_2 > w_1\newline \\*m_2: w_1 > w_3 > w_2\newline \\*m_3: w_1 > w_2 > w_3\newline \\*womanPref = \begin {bmatrix}1 \; 2 \; 3 \\*2 \; 1 \; 3 \\*3 \; 1 \; 2 \\*\end {bmatrix}\newline \\*The\; preference\; list\; for\; woman:\newline \\*w_1: m_1 > m_2 > m_3\newline \\*w_2: m_2 > m_1 > m_3\newline \\*w_3: m_3 > m_1 > m_2

The program is well commented. If you still face any problem, feel free to comment.

#include <iostream>
#include <iomanip>
using namespace std;

int manPref[1000][1000];	// 2d array to store preference list of each man
							// ith row gives stores the preference list of ith man
							// the woman who appears first in the preference list
							// are prefered over woman that appears in last

int womanPref[1000][1000]; 	// 2d array to store preference list of each woman
							// ith row gives us the preference list of ith woman
							// the man who appears first in the preference list
							// are prefered over the man that appears in last

int prefer[1000][1000]; 	// Stores preference between the all pairs of man and woman
							// prefer[i][j] tells us how much jth woman prefers ith man
							// lower value means a high preference

int engaged[1000];			// If engaged[i] is 1 then it means that ith man is engaged to someone
							// If engaged[i] is 0 then it means ith man is currently not engaged to anyone
							// Intially engaged is set to 0

int current[1000];			// It store which woman is engaged to which man
							// current[j]: it means that the jth woman is engaged to current[j] man

int lastWoman[1000];		// It is used to store the index of the last woman proposed by a man
							// lastWoman[i]: It means that ith man last proposed to manPref[i][lastWoman[i]] woman
							// It basically stores the index of the last woman to whom ith man proposed to 

int n;						// number of man and woman

void gale_shapley_algorithm() {

	int flag, i, j, m, w;

	// Calculating values of prefer[][]
	// prefer[i][j] tells us how much jth woman prefers ith man
	// lower value of prefer[i][j] means higher preference
	for (j = 0; j <= n; ++j) {
		for (i = 1; i <= n; ++i) {
			prefer[womanPref[j][i]][j] = i;
		}
	}

	// loop until everyone is engaged
	while (true) {

		flag = 1;
		for (int i = 1; i <= n; ++i) {
			// if ith man is not not engaged, set flag to 0 and break the loop
			if (!engaged[i]) {
				flag = 0;
				break;
			}

		}

		// if flag is still 1
		// then it means every man is engaged
		// break the while loop
		if (flag == 1)
			break;

		// the following runs for each man
		for (int i = 1; i <= n; ++i) {

			// checking if the ith man is engaged or not
			if (!engaged[i]) {

				// if the ith man is not engaged then
				// the ith man will propose to a woman

				m = i; // m stores the current man

				lastWoman[m] = lastWoman[m] + 1;	// lastWoman[m] is the index of last woman to whom m proposed
													// We increment lastWoman[m] to propose to the next women in the preference list

				w = manPref[m][lastWoman[m]];	// w stores the woman
												// to whom m is going to propose

				if (current[w] == 0) {

					// if current[w] is 0
					// then it means that women w is not engaged to anyone
					// we set current[w] to m to indicate that w is now engaged to m
					// we set engaged[m] = 1 since m is now engaged to someone

					current[w] = m;
					engaged[m] = 1;

				}

				// if current[w] is not 0
				// then it means that woman w is already engaged to someone
				// we check if woman w prefers her current man more than m
				// Note: lower value means higher preference
				else if (prefer[m][w] < prefer[current[w]][w]) {

					// if prefer[m][w] < prefer[current[w]][w]
					// then women w prefers m more than her current man
					// we break the engagement of w with her current man
					// current man of w is now not engaged to anyone
					// thus, we set engaged[current[w]] to 0
					// then we set current[w] to m since w is now engaged to m
					// we set engaged[m] to 1 since m is now engaged to someone

					engaged[current[w]] = 0;
					current[w] = m;
					engaged[m] = 1;

				}

			}
		}

	}

	cout << "Man" << setw(10) << "Woman" << endl;
	for (int i = 1; i <= n; ++i) {
		cout << current[i] << setw(10) << i << endl;
	}

}

int main() {

	cout << "Enter Number of Elements in One Set: ";
	cin >> n;

	// Enter preference matrix for man
	cout << "Enter Preference List for Man: " << endl;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			cin >> manPref[i][j];
		}
	}

	// Enter preference matrix for woman
	cout << "Enter Preference List for Woman: " << endl;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			cin >> womanPref[i][j];
		}
	}

	gale_shapley_algorithm();

}

Output

Enter Number of Elements in One Set: 4
Enter Preference List for Man:
2 1 3 4
4 1 2 3
1 3 2 4
2 3 1 4
Enter Preference List for Woman:
1 3 2 4
3 4 1 2
4 2 3 1
3 2 1 4

Stable Matchings
Man     Woman
1         1
4         2
3         3
2         4

Time Complexity

The time complexity of Gale Shapley algorithm is O(N^2). The total size of manPref matrix is N^2. We visit each index of manPref at-most once. Thus, the time complexity is O(N^2).

Existence of Multiple Matchings

Stable matchings are not unique. Man and women can be engaged in multiple ways.

In the Gale Shapley algorithm, if a man proposes to a woman, then man and woman are matched such that the woman chooses the best man out of all the man who proposed to her. Whereas if a woman proposes to a man, then the man chooses the best woman out of all the woman who proposed to him.

For example, let

\\*manPref = \begin {bmatrix}3 \; 2 \; 1 \\*1 \; 3 \; 2 \\*1 \; 2 \; 3 \\*\end {bmatrix}womanPref = \begin {bmatrix}1 \; 2 \; 3 \\*2 \; 1 \; 3 \\*3 \; 1 \; 2 \\*\end {bmatrix}

If a man proposes to a woman, then the stable matching is

\newline \\*\begin{matrix}Man & Woman \\*2 & 1\\*3 & 2\\*1 & 3\\*\end{matrix}

If a woman proposes to a man, then the stable matching is

\newline \\*\begin{matrix}Man & Woman \\*1 & 1\\*2 & 2\\*3 & 3\\*\end{matrix}

As you can see both the matchings are different.

Leave a Comment

Your email address will not be published. Required fields are marked *