= Stable matching in a bipartite graph
= Stable matching
{synonym}
A <stable matching in a bipartite graph> pairs two groups so that no acceptable unpaired pair would both rather be together. Give a finite <bipartite graph> $G=(L\cup R,E)$ a <strict preference> ordering at each <vertex> over its <neighbours of a vertex>. An <edge> means that both endpoints regard the pair as acceptable; every acceptable partner ranks above being unmatched. Lists may be incomplete, and $L$ and $R$ may have unequal <cardinalities>. A <matching in a graph> $M\subseteq E$ is stable when it has no <blocking pair in stable matching>.
Write $M(v)$ for the partner of a <vertex> $v$, or $\bot$ if $v$ is an <unmatched vertex in a matching>. An unused <edge> $(\ell,r)$ is a <blocking pair in stable matching> precisely when
$$
r\succ_\ell M(\ell)\quad\text{and}\quad \ell\succ_r M(r),
$$
where $\succ_v$ denotes the <strict preference> at $v$ and $\bot$ ranks below every <neighbour of a vertex>. Both inequalities matter: wanting a different partner alone cannot upset a <stable matching>. A <stable matching> need not be a <perfect matching>; the <Gale-Shapley algorithm> still finds one with incomplete lists and unequal sides.
Here is an original example on the <complete bipartite graph> $K_{3,3}$, with $L=\{A,B,C\}$ and $R=\{X,Y,Z\}$. Read each row from best to worst:
$$
\begin{array}{c|ccc|c|ccc}
\text{left}&1&2&3&\text{right}&1&2&3\\\hline
A&X&Y&Z&X&C&A&B\\
B&X&Y&Z&Y&A&B&C\\
C&Y&Z&X&Z&A&B&C
\end{array}
$$
There are two <stable matchings>,
$$
M_L=\{(A,X),(B,Y),(C,Z)\},\qquad
M_R=\{(A,Y),(B,Z),(C,X)\}.
$$
For $M_L$, the only unpaired partners preferred by left <vertices> are $B$ wanting $X$ and $C$ wanting $Y$. But $X$ prefers its partner $A$ to $B$, and $Y$ prefers its partner $B$ to $C$. Hence neither is a <blocking pair in stable matching>. For $M_R$, the left <vertices> want $A$ with $X$, $B$ with $X$ or $Y$, and $C$ with $Y$ or $Z$. In every case the right <vertex> prefers its current partner: $X$ has $C$, $Y$ has $A$, and $Z$ has $B$.
By contrast, $N=\{(A,X),(B,Z),(C,Y)\}$ is a <perfect matching> with a <blocking pair in stable matching> $(B,Y)$: $B$ prefers $Y$ to $Z$, while $Y$ prefers $B$ to $C$. The abandoned partners need not agree to the change; stability tests the incentives of the two endpoints of the unused <edge>.
\Image[/stable-matching-blocking-pair-comparison.png]
{title=One <blocking pair in stable matching> and two <stable matchings> for the same strict preference lists}
There are $3!=6$ <permutations> of right partners. The following table lists every <blocking pair in stable matching> for each <perfect matching>; the middle column gives the partners of $A,B,C$ in that order:
$$
\begin{array}{c|c|l}
& (M(A),M(B),M(C))&\text{blocking pairs}\\\hline
M_L&(X,Y,Z)&\text{none}\\
N&(X,Z,Y)&(B,Y)\\
&(Y,X,Z)&(A,X)\\
M_R&(Y,Z,X)&\text{none}\\
&(Z,X,Y)&(A,X),\ (A,Y)\\
&(Z,Y,X)&(A,Y)
\end{array}
$$
This exhausts the <stable matchings>: any nonperfect <matching in a graph> here leaves an unmatched <vertex> on each side, and those two form a <blocking pair in stable matching> because every cross-pair is acceptable. Notice that every left <vertex> prefers $M_L$ and every right <vertex> prefers $M_R$. Stability can accommodate opposing interests without selecting a single universally preferred outcome.
A <stable matching> addresses the possibility of mutually beneficial departures. Its definition contains no numerical total social benefit or <maximum-weight matching> objective. For example, assigning benefit $100$ to each <edge> of $N$ and zero to every other <edge> makes $N$ the unique <maximum-weight matching>, yet $(B,Y)$ still blocks it under the displayed <preference relations>. Such external benefits need not represent participants' rankings.
Back to article page
