This challenge is the classic stable marriage problem: given n men and n women, where each person has ranked every member of the opposite sex in order of preference, pair everyone up so that there’s no man and woman who would both rather have each other than their current partners. A pairing with no such pair is called stable.
Example preferences:
How men rank women (1 = most preferred):
| Alice | Barbara | Claire | Doris | Elsie | |
|---|---|---|---|---|---|
| Adam | 5 | 1 | 2 | 4 | 3 |
| Bob | 4 | 1 | 3 | 2 | 5 |
| Charlie | 5 | 3 | 2 | 4 | 1 |
| Dave | 1 | 5 | 4 | 3 | 2 |
| Edgar | 4 | 3 | 2 | 1 | 5 |
How women rank men (1 = most preferred):
| Adam | Bob | Charlie | Dave | Edgar | |
|---|---|---|---|---|---|
| Alice | 1 | 2 | 4 | 3 | 5 |
| Barbara | 3 | 5 | 1 | 2 | 4 |
| Claire | 5 | 4 | 2 | 1 | 3 |
| Doris | 1 | 4 | 3 | 2 | 5 |
| Elsie | 4 | 2 | 3 | 5 | 1 |
Find a stable pairing for this example, and build a decision model general enough to handle any such preference table.
Send your solutions to DecisionManagementCommunity@gmail.com, or open a pull request to add yours here.