The algorithm we are going to explain is called Gale-Shapley algorithm after mathematical economist David Gale and Lloyd Shapley who described and analyzed in 1962. In this algorithm individuals are making choices that are all individually reasonable in order to come out with a globally acceptable solution also called stable matching.
Let’s clarify what stable matching means with an example. Imagine we have two men and two women: Bob, Peter, Alice and Kate. Based on preference list we will try to match those couples.
Matching 1 is stable as Alice is Bob’s first choice and vice versa. Alice is also Peter’s first choice but Alice won’t leave Bob for Peter because she prefers Bob to Peter. Kate prefers Bob to Peter as well but Bob won’t leave Alice for Kate as he prefers Alice to Kate.
Matching 2 is not stable as Bob prefers Alice and Alice prefers Bob, so they will defect and chose each other so that Peter and Kate will remain stranded.
A stable matching is one that avoids such defects, this is called stability. In stable matching none of the matched candidate pairs wants to make a deal with each other and leave their assigned partners stranded.
This small scale of example shows that when we have equal number of candidates on each side with equal number of preferences the algorithm will generate a stable matching between all candidates and nobody will be left stranded. Lets’ explain how the algorithm works step by step, imagine we have the following couples each with their own preference list.
The men in the left side start to propose to women on the right side based on their preference list. Women on their side will either accept the proposal or reject it if they already have a better proposal from their preference list.
We complete the first iteration after all men try to make proposals to their first candidates in their lists. In the second iteration the men that don’ have any match and they still have left candidates on their lists try to propose to remaining candidates based on their priority.
After the second iteration we repeat the same step again.
At the end of third iteration we are on a situation where every man has a current match and no man can make a proposal to any women. The algorithm terminates either when every man has a match or the list of men’s candidates is exhausted.
Take into account that it is possible to have more than one stable matching and it is not guaranteed which one the algorithm will find.
One drawback of the algorithm is related to who benefits from the situation. Although the above example doesn’t show this case, the sides that make the proposals get their best candidates as possible from their preference list. On the other side the sides which are being proposed get their worst candidates as possible. So it matters who makes the proposals.
Implementation
We will show a slightly different implementation which is object orientated. We will create a Candidate class with several methods required to implement the algorithm.
public class Candidate
{
private readonly List<Candidate> preferences;
private readonly string name;
public Candidate CurrentMatch { get; set; }
public Candidate(string name)
{
this.preferences = new List<Candidate>();
this.name = name;
}
public bool HasAnyPreferencesLeft()
{
return this.preferences.Any();
}
//Gets the first candidate from a not proposed candidates yet
public Candidate GetCandidateToPropose()
{
return preferences.FirstOrDefault();
}
public void AddPreferences(List<Candidate> preferenceList)
{
this.preferences.AddRange(preferenceList);
}
// Propose a match to a candidate
public void Propose(Candidate toCandidate)
{
// We can only propose if we haven't got a match already
if (CurrentMatch == null)
{
//Call receive proposal on the other candidate
toCandidate?.ReceiveProposal(this);
}
}
// Implement the logic for receiving proposal
public void ReceiveProposal(Candidate fromCandidate)
{
// If we don't have a match already accept the proposal
if (CurrentMatch == null)
{
this.AcceptProposal(fromCandidate);
}
else
{ // Check if the candidate sending the current proposal
// is not with higher priority in our preference list
if (preferences.IndexOf(fromCandidate) < preferences.IndexOf(this.CurrentMatch))
{
// So we have a better match then break the current match
CurrentMatch.BreakMatch(this);
// Accept the new proposal
this.AcceptProposal(fromCandidate);
}
else
{
// Reject the current proposal as we already have a better match
fromCandidate.BreakMatch(this);
}
}
}
public void AcceptProposal(Candidate fromCandidate)
{
// When a proposal is accepted link both candidates to each other
this.CurrentMatch = fromCandidate;
fromCandidate.CurrentMatch = this;
}
public void BreakMatch(Candidate fromCandidate)
{
// When breaking or rejecting a proposal then remove the candidate
// that broke or rejected the offer from list of preferences
this.preferences.Remove(fromCandidate);
this.CurrentMatch = null;
}
public override string ToString()
{
return this.name;
}
}
In the next step we will implement the algorithm and call it to find a stable matching for the example explained above.
class Program
{
static void Main(string[] args)
{
var bob = new Candidate("Bob");
var peter = new Candidate("Peter");
var alex = new Candidate("Alex");
var alice = new Candidate("Alice");
var kate = new Candidate("Kate");
var jane = new Candidate("Jane");
bob.AddPreferences(new List<Candidate> { alice, kate, jane });
peter.AddPreferences(new List<Candidate> { kate, alice, jane });
alex.AddPreferences(new List<Candidate> { alice, kate, jane });
kate.AddPreferences(new List<Candidate> { peter, bob, alex });
alice.AddPreferences(new List<Candidate> { bob, peter, alex });
jane.AddPreferences(new List<Candidate> { bob, peter, alex });
List<Candidate> men = new List<Candidate>
{
bob,
peter,
alex
};
List<Candidate> women = new List<Candidate>
{
alice,
kate,
jane
};
StableMatch(men);
PrintMatches(men);
}
private static void StableMatch(List<Candidate> candidates)
{
// execute the algorithm when there are candidates without matches
// and the candidate has items in his preference list
while (candidates.Any(c => c.HasAnyPreferencesLeft() && c.CurrentMatch == null))
{
foreach (var candidate in candidates)
{
candidate.Propose(candidate.GetCandidateToPropose());
}
}
}
private static void PrintMatches(List<Candidate> candidates)
{
foreach (var candidate in candidates)
{
Console.WriteLine($"{candidate} <---> {candidate.CurrentMatch}");
}
}
}
If we run the program above we will get the following result:
Bob <—> Alice
Peter <—> Kate
Alex <—> Jane
Time Complexity of Gale-Shapley Algorithm is O(n2)
You can read more about this algorithm here.
Pair Coders 