couple
Gale–Shapley
Algorithm

The Problem

Perfect Matching:

A perfect matching is a matching of men and women in which everyone is matched monogamously. Each man gets exactly one woman, and each woman gets exactly one man.

Unstable Pairs:

In a matching A, an unmatched pair M-W is unstable if man M and woman W prefer each other to their current partners.
For example, consider the following matching with the pairs Jim-Angela and Dwight-Pam:
The green lines above represent the current pairs in the matching A.
Suppose:
1) Jim prefers Pam over Angela and
2) Pam prefers Jim over Dwight
Then, the pair Jim-Pam (represented by the red line above) is an unstable pair because both Jim and Pam prefer each other over their current partners.

Identify Unstable Pairs:

Does the above matching contain any unstable pairs?


Stable Matching:

A perfect matching with no unstable pairs is called a stable matching.

Stable Matching Problem:

Given the preference lists of n men and n women, find a stable matching if one exists.

The Solution

Algorithm:

In 1962, David Gale and Lloyd Shapley proved that, for any equal number of men and women, it is always possible to make all marriages stable.

The Gale–Shapley algorithm involves a number of "rounds": This algorithm is guaranteed to produce a stable marriage for all participants in time \(O(n^2)\) where \(n\) is the number of men or women.
Among all possible different stable matchings, it always yields the one that is best for all men among all stable matchings, and worst for all women. No man can get a better matching for himself by misrepresenting his preferences. However, each woman may be able to misrepresent her preferences and get a better match.

Algorithm Pseudocode

algorithm stable_matching:
		Initialize all men and women to free (unengaged)
		while there exists a free man m who still has a woman w to propose to:
			set w to first woman on m's list to whom m has not yet proposed
			if w is free:
				(m, w) become engaged
			else:
				let m' be w's current fiance
				if w prefers m to m':
					m' becomes free
					(m, w) become engaged
				else:
					(m', w) remain engaged
Click next step to walk through the solution. Click circles to edit their preference lists.
Play Speed:

Try It Yourself

Pair up men and women by clicking on them. Check your work when you're finished!


Further Reading

Applications:

Algorithms for finding solutions to the stable marriage problem have applications in a variety of real-world situations, perhaps the best known of these being in the assignment of graduating medical students to their first hospital appointments. Many applications for the Gale-Shapley algorithm were the work of Harvard economist Alvin Roth. In the 1980s, he applied the algorithm to the National Residency Match Program (NRMP), a program that paired new doctors to hospitals around the country. Roth also applied the Gale-Shapley algorithm to public schooling. In New York City, students are able to select their school via a ranking system. However, the process was broken, with around 30,000 students being left unmatched each year. The new system was implemented in 2004, and the number of unmatched students plummeted from 30,000 to 3,000. Also in 2004, Roth used the algorithm to help transplant patients find donors. His system helped incompatible donor-recepient pairs find others in the same situation, and trade places with them. This has allowed thousands of people to receive a kidney transplant when it was previously impossible. This breakthrough won both Roth and Shapley the Nobel Prize in economics in 2012.

Another important and large-scale application of stable marriage is in the problem of assigning users to web servers. of users access web pages, videos, and other services on the Internet, requiring each user to be matched to one of potentially hundreds of thousands of servers around the world. A user prefers servers that are closer to them, resulting in a (partial) preferential ordering of the servers for each user. Each server prefers to serve users that it can with a lower cost, resulting in a (partial) preferential ordering of users for each server. Content delivery networks that distribute much of the world's content and services solve this large and complex stable marriage problem between users and servers every several seconds to enable billions of users to be matched up with their respective servers.

Sources:

Tools and Assets: