Problem Statement
Suppose there are two sides (for example, men and women) to be matched, where everyone has a complete preferences over the opposite side. The goal is to find valid partners of the opposite side such that the final matching is stable, meaning that no two participants would prefer to breakout of their matching!
Algorithm Solution
Suppose men propose to women:
1. First unengaged man proposes to the woman he prefers most.
2. When the woman receives one proposal, she replies immediately. She can hold only one proposal and reject another one that is less preferable than her current proposal. If there is no other proposal, then she must receive that proposal.
3. If a proposal is rejected, that man will continue proposing to his next most-preferred woman.
4. Once a man is engaged to a woman, the process will repeat until everyone is engaged.
Try it out
Men
| Name | Preferences | |
|---|---|---|
|
||
|
|
||
|
|
||
|
|
Women
| Name | Preferences | |
|---|---|---|
|
||
|
|
||
|
|
||
|
|
Introduction
This problem is traditionally known as the stable marriage problem. The goal is to find valid partners of the opposite gender in such a way that the final matching is stable, meaning that no two participants would prefer to breakout of their ‘marriage’ and elope!
It can also be applied to other cases in our daily life. For example, you want to match research students to potential advisors or students. Each student ranks all potential advisors and each advisor also ranks students based on preferences. How can we ensure that no student-advisor pair who are not matched to each other exist that both prefer to be with one another?
Properties
Our solution guarantees the following properties:
- Stability: No two participants would rather break up with their partners and elope!
- Efficiency: The solution is always the best (among stable solutions) for the proposing side. Unfortunately, this is not true for the proposed side.
- Truthfulness: It is always better for those on the proposing side to be honest about their preference ordering.
Algorithm Overview
We use the Deferred Acceptance algorithm (DA) pioneered by Gale and Shapley to guarantee stable matchings. We assume all agents have strict preferences (ranking) over the opposite set of agents. In the Deferred Acceptance (DA) algorithm, those in the proposing side (traditionally men) propose to their top choice from the proposed side. Those in the proposed side accept the proposals if the proposal is coming from a more preferred option, and reject their previous match. A stable solution is guaranteed to exist and we can easily find it through the DA algorithm.
DA guarantees stability and optimality for proposing side. It also incentivizes truthful behavior among participants in the proposing side. DA does not guarantee truthfulness from the proposed side, meaning that participants in the proposed side (traditionally women) can benefit from manipulation by misreporting their ranking order.
College admissions and the stability of marriage
By: David Gale and Lloyd Shapley