Gale and Shapley's stable matching algorithm addresses the
problem of forming stable pairs in situations where individuals have preferences over one another.
The algorithm proceeds through a series of rounds, where each unengaged individual proposes to their most preferred
available partner, and each engaged individual holds on to the best proposal received. This process iterates until no further
improvements are possible. The resulting matchings are stable because, at the end,
no individual has an incentive to break their current pairing for an alternative one.
This algorithm has widespread applications, from matchmaking in dating platforms to solving complex scenarios like
job placements, where maintaining stability and fairness in partnerships is crucial.
Demo
Set A (this is the first set for the SM problem)
| Caleb's preferences: |
['Daniel', 'May', 'Ryan', 'Sadab'] |
| Mark's preferences: |
['May', 'Ryan', 'Sadab', 'Daniel'] |
| Song's preferences: |
['Sadab', 'Ryan', 'May', 'Daniel'] |
| Marcos's preferences: |
['Daniel', 'Ryan', 'Sadab', 'May'] |
Set B (this is the second set for the SM problem)
| Sadab's preferences: |
['Song', 'Mark', 'Caleb', 'Marcos'] |
| Ryan's preferences: |
['Mark', 'Song', 'Caleb', 'Marcos'] |
| Daniel's preferences: |
['Marcos', 'Mark', 'Caleb', 'Song'] |
| May's preferences: |
['Mark', 'Caleb', 'Song', 'Marcos'] |
Results
| Caleb matched with Ryan |
| Mark matched with May |
| Song matched with Sadab |
| Marcos matched with Daniel |
Try it yourself!
[*] Gale, D., and L. S. Shapley. “College Admissions and the Stability of Marriage.” The American Mathematical Monthly, vol. 69, no. 1, 1962, pp. 9–15. JSTOR, https://doi.org/10.2307/2312726.