Understanding Gale-Shapley (Stable Matching ) Algorithm and its Time Complexity
Hey Readers,
Hope you are doing great progress and wish you to learn more. Let’s get started, I see many people are confused with understanding the Gale-Shapley Algorithm (also known Stable Matching Algorithm) and its time complexity. Hope this Article helps you understand it in better way with examples.
What is Gale-Shapley Algorithm?
The Gale-Shapley Algorithm is a well-known algorithm in the field of matching theory and game theory. It is used to find the stable matching between two sets of elements, where no two elements prefer each other over their current match. This algorithm is widely used in applications such as college admissions, job markets, and resource allocation. The concept was first described by David Gale and Lloyd Shaprow in 1962.
A stable matching is defined as a pairing of elements such that there are no two elements who would both prefer each other over their current match. For example, in a college admission scenario, a stable matching would be a pairing of students with colleges such that no student would prefer another college over their current match, and no college would prefer another student over their current match.
How it finds Stable Matching?
The Gale-Shapley algorithm works by having one set of elements, called proposers, make proposals to the other set of elements, called receivers. The proposers have a preference list of the receivers, and the receivers have a preference list of the proposers. The algorithm starts by having each proposer make a proposal to their first choice receiver. If a receiver receives multiple proposals, they choose the proposer they prefer the most, and reject the others. The rejected proposers then move on to their next choice and make a proposal. This process continues until all elements are matched.
Here is a step-by-step explanation of How the Gale-Shapley algorithm works:
- Each proposer has a preference list of receivers.
- The algorithm starts with each proposer proposing to their first choice receiver.
- If a receiver receives multiple proposals, they choose the proposer they prefer the most, and reject the others.
- The rejected proposers move on to their next choice and make a proposal.
- The process continues until all elements are matched.
What is Good about this Algorithm?
One of the important properties of the Gale-Shapley algorithm is that it is guaranteed to find a stable matching. Furthermore, the matching found by the algorithm is guaranteed to be the unique stable matching, known as the “deferred acceptance” stable matching.
Lets Understand the Time to find Stable Matching?
The time to compute the solution for the Gale-Shapley algorithm is O(n²), where n is the number of elements in each set. This means that the running time of the algorithm grows quadratically with the number of elements. This makes the algorithm inefficient for large inputs. However, for small inputs, the algorithm is fast and easy to implement.
In Worst case scenario, lets see Number of Days and Number of Proposals, the algorithm will take to Find Stable Matching.
Logic: consider N-men and N-women
Total Proposals = Total Rejected + Accepted
In worst case, Each men will be rejected at most (n-1) times by the women, and the last one of the males will do his nth proposal, then for every female there will be only one male so that it will be a stable matching.
Total proposals till (n-1)th day will = (Total Men) * (Total proposal by each men) = n * (n-1)
Total No. of proposals = n*(n−1) + 1= (n^2) − n + 1
Now, on the first day, n proposals are made, and thereafter each day only one male is getting rejected so, one proposal per day.
No. of days = No. of proposals − n + 1
No. of Days = [n*(n−1) + 1 ]− n + 1 = (n^2) − 2*n + 2
In conclusion, the Gale-Shapley algorithm is a well-known and widely used algorithm for finding stable matchings between two sets of elements. Despite its inefficient time complexity, the algorithm is still widely used in various applications due to its simplicity and guarantee of finding a unique stable matching.
If you find it helpful, please share it and feel free to share your thoughts through comments.
Here’s my Linkedin to get in touch with me.
