The stable marriage problem
The stable marriage problem (SM) describes the problem of finding a stable matching between two distinct, equally sized sets of players with complete preferences.
Key definitions
The game
Consider two distinct sets, \(S\) and \(R\), each of size \(N\), and let us refer to these sets as suitors and reviewers respectively. Each element of \(S\) and \(R\) has a ranking of all the other set’s elements associated with it, and we call this ranking their preference list.
We can consider the preference lists for the elements of each set as a function which produces tuples. We call these functions \(f\) and \(g\) respectively:
\[f : S \to R^N; \quad g : R \to S^N\]
This construction of suitors, reviewers and preference lists is called a game of size \(N\), and is denoted by \((S,R)\). This game is used to model instances of SM.
Matching
A matching \(M\) is any bijection between \(S\) and \(R\). If a pair \((s,r) \in S \times R\) are matched in \(M\), then we say that \(M(s) = r\) and, equivalently, \(M^{−1}(r) = s\).
Preference
Let \((S, R)\) be an instance of SM. Consider \(s \in S\) and \(r, r' \in R\). We say that \(s\) prefers \(r\) to \(r'\) if \(r\) appears before \(r'\) in \(f(s)\). The definition is equivalent for reviewers.
Blocking pair
A pair \((s,r)\) is said to block a matching \(M\) if all of the following hold:
- \(s\) and \(r\) aren’t matched by \(M\), i.e. \(M(s) \neq r\).
- \(s\) prefers \(r\) to \(M(s) = r'\).
- \(r\) prefers \(s\) to \(M^{-1}(r) = s′\).
Stable matching
A matching \(M\) is said to be stable if it contains no blocking pairs, and unstable otherwise.
An example
Consider the unsolved matching game of size three shown below as an edgeless graph with suitors on the left and reviewers on the right. Beside each vertex is the name of the player and their associated ranking of the complementary set’s elements:
In this representation, a matching \(M\) creates a bipartite graph where an edge between two vertices (players) indicates that they are matched by \(M\). Consider the matching shown below:
Here we can see that players \(A\), \(C\) and \(F\) are matched to their favourite player but \(B\), \(D\) and \(E\) are matched to their least favourite. There’s nothing particularly special about that but we can see that players \(B\) and \(D\) form a blocking pair given that they would both rather be matched with one another than with their current match. Hence, this matching is unstable.
We can attempt to rectify this instability by swapping the matches for the first two rows:
Upon closer inspection, we can see that each suitor is now matched with their most preferred reviewer so as not to form a blocking pair that would upset any current matchings. This matching is stable and is considered suitor-optimal.
The algorithm
David Gale and Lloyd Shapley presented an algorithm for solving SM in Gale and Shapley (1962). The algorithm provides a unique, stable, suitor-optimal matching for any instance of SM. A more efficient, robust extension of the original algorithm, taken from Gusfield and Irving (1989), is given below.
- Assign all suitors and reviewers to be unmatched.
- Take any suitor \(s\) that is not currently matched, and consider their favourite reviewer \(r\).
- If \(r\) is matched, get their current match \(s' = M^{-1}(r)\) and unmatch the pair.
- Match \(s\) and \(r\), i.e. set \(M(s) = r\).
- For each successor, \(t\), to \(s\) in \(g(r)\), delete the pair \((t, r)\) from the game by removing \(r\) from \(f(t)\) and \(t\) from \(g(r)\).
- Go to 1 until there are no such suitors, then end.
As the game requires equally sized sets of players, the reviewer-optimal algorithm is equivalent to the above but with the roles of suitors and reviewers reversed.