Skip to content

The Stable Matching or the Stable Marriage algorithm is a mathematical algorithm that finds stable matches between two equally sized sets of elements, the proposers and the acceptors. This project uses basic Python data structures to implement the algorithm.

Notifications You must be signed in to change notification settings

shubh11220/The-Stable-Matching-Algorithm

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

10 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

The Stable Matching Algorithm

The Stable Matching or the Stable Marriage algorithm is a mathematical algorithm that finds stable matches between two equally sized sets of elements, the proposers and the acceptors. The algorithm works off two independent preference-frames for each set which allows preference based matching to occur.

alt text

After the initialization a proposal is made by the proposers to the acceptors and the matching algorithm begins

alt text

The solution to the Stable-Matching Problem was first given by David Gale & Lloyd Shapley. The algorithm won Shapley along with Alvin Roth, the 2012 Nobel Memorial Prize in Economic Sciences

The Gale-Shapley algorithm has a wide variety of uses it is used to pair doctors with hospitals, kidneys with patients, employers with trainees, urban students with magnet schools etc.

References :

https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm
https://www.geeksforgeeks.org/stable-marriage-problem/
https://www.inc.com/burt-helm/gale-shapley-algorithm-innovation-nobel-prize.html#:~:text=The%20winners%20of%20the%202012,urban%20students%20with%20magnet%20schools.
https://towardsdatascience.com/gale-shapley-algorithm-simply-explained-caa344e643c2

About

The Stable Matching or the Stable Marriage algorithm is a mathematical algorithm that finds stable matches between two equally sized sets of elements, the proposers and the acceptors. This project uses basic Python data structures to implement the algorithm.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages