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:
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.
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":
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.
The Gale–Shapley algorithm involves a number of "rounds":
- In the first round, first
- Each unengaged man proposes to the woman he prefers most, and then
- Each woman replies "maybe" to her suitor she most prefers and "no" to all other suitors.
- In each subsequent round, first
- Each unengaged man proposes to the most-preferred woman to whom he has not yet proposed (regardless of whether the woman is already engaged), and then
- Each woman replies "maybe" if she is currently not engaged or if she prefers this man over her current provisional partner (in this case, her current provisional partner becomes unengaged).
- This process is repeated until everyone is engaged.
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.
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:
- Wikipedia: https://en.wikipedia.org/wiki/Stable_marriage_problem
- Algorithms Class (CSE 421): https://homes.cs.washington.edu/~anuprao/pubs/CSE421Wi2020/01stable-matching.pdf
- University of California: https://medium.com/@UofCalifornia/how-a-matchmaking-algorithm-saved-lives-2a65ac448698
- New York Times: http://www.nytimes.com/2014/12/07/nyregion/how-game-theory-helped-improve-new-york-city-high-school-application-process.html
Tools and Assets:
- D3.js - visualization tool
- Avataaars - svg face generation tool
- manypixels - royalty-free illustrations