Gale Shapley Algorithm for Stable Matching

Achieving Stable Matching between two sets of entities with various preferences for each other is a real world problem (a.k.a Stable Marriage Problem). Examples include dating sites, matching medical students to hospital jobs (National Resident Matching Program) etc. How can we ensure that there is a stable matching (defined as any pairings, such that no entity can find any one they would rather be with, who would rather be with them)? Such a matching would be stable (or in equilibrium) because any further change would be detrimental to the entities involved in terms of their stated preferences. Some questions that arise are whether such a matching actually exists? If it exists, how do we find it? How can we be confident that the solution that we get is the ‘best’ among all possible matchings? These issues are not trivial and when the elements of the entity sets increase, it soon becomes an intractable problem to solve by trial and error.

Thankfully in answer to the question of whether a stable matching exists, we have a theorem that guarantees exactly that! It states that:
“For any number entities of two disjoint sets (having equal number of elements), no matter how they rank each other, there always exists at least one stable matching

While the solution is stable, it is not necessarily optimal from all individuals’ points of view. The traditional form of the algorithm is optimal for the initiator (suitor) of the proposals and the stable, suitor-optimal solution may or may not be optimal for the acceptor of the proposals. It will be acceptor pessimal.

To find the solution, we have the Gale-Shapley Algorithm. In 1962,  David Gale and Lloyd Shapley proved that, for any equal number of suitors and acceptors, it is always possible to solve the Stable Marriage Problem.

 

The Gale-Shapely Algorithm:
Each suitor proposes to his highest preferred acceptor. If the acceptor is not already matched, we automatically match suitor to acceptor. If the acceptor is previously matched; acceptor picks the most preferred suitor. The rejected suitor moves on to his next preferred acceptor. When each suitor is matched the problem is solved.

Download

Download source code. It is an implementation of the algorithm in .NET 4 using Visual Studio 2010 and C#.

/Here Optimal Entity is the Suitor and Pessimal Entity is the acceptor
//The function that implements the Gale-Shapley algorithm in .NET is shown
public static SortedDictionary<T,U> Match(HashSet<SuitorEntity<T, U>> optimalEntities, HashSet<AcceptorEntity<U, T>> pessimalEntities)
        {
            Dictionary<AcceptorEntity<U, T>, SuitorEntity<T, U>> matching = new Dictionary<AcceptorEntity<U, T>, SuitorEntity<T, U>>();
            Stack<SuitorEntity<T,U>> processStack = new Stack<SuitorEntity<T, U>>(optimalEntities);
            while(processStack.Count>0)
            {
               
                //Store each suitor in a Stack.
                SuitorEntity<T, U> suitorEntity = processStack.Pop();
                // Match the optimal entity to its first preference
                //If its first preference is not previously matched then automatically match and dequeue
                SuitorEntity<T, U> matchedEntity;
                AcceptorEntity<U, T> acceptorEntity = suitorEntity.Preferences.Dequeue();
                if(!matching.TryGetValue(acceptorEntity,out matchedEntity))
                {
                    matching.Add(acceptorEntity, suitorEntity);
                }
                else//Else
                {
                    foreach (SuitorEntity<T,U> entity in acceptorEntity.Preferences)
                    {
                        if(matchedEntity == entity)
                        {
                            //The Pessimal Entity makes a choice: If it already has a better preference then it keeps it
                            processStack.Push(suitorEntity);
                            break;
                        }
                        // Replace the matching of the acceptor with the most preferred new suitor
                        if (suitorEntity != entity) continue;
                        matching[acceptorEntity] = suitorEntity;
                        //Push the previously matched suitor who is now rejected on to the stack for further processing
                        processStack.Push(matchedEntity);
                        break;
                    }

                }

            }
            SortedDictionary<T,U> result = new SortedDictionary<T, U>();
            foreach (KeyValuePair<AcceptorEntity<U, T>, SuitorEntity<T, U>> keyValuePair in matching)
            {
                result.Add(keyValuePair.Value.Entity,keyValuePair.Key.Entity);
            }
            return result;
        }

References

Interactive Flash Demonstration of Stable Marriage Problem

Posted in Technology Tagged with: , ,
%d bloggers like this: