Stable matching theorem for non-equal sides

43 Views Asked by At

Given a bipartite graph with two sides $A$ and $B$, for a vertex $v$, there is a linear order on $N(v)$ (a preference list). The stable matching theorem says that if $|A|=|B|$, then there exists a perfect matching $M$ that is stable: there is no $a\in A$ preferring $b'$ to $b$, where $b$ is matched to $a$, where $b'$ also prefers $a$ to $a'$, where $a'$ is matched to $b'$.

I am wondering what if $|A|<|B|$, is there a matching from $A$ that is stable?

1

There are 1 best solutions below

0
On BEST ANSWER

First, note that for the theorem (due to Gale and Shapley) that your citing to be valid, the bipartite graph is complete; otherwise it could even fail Hall's condition, and clearly not have a perfect matching.

The answer to your question is yes. One way to see this is to add $|B|-|A|$ "dummy" vertices to $A$ to obtain $A'$, and a bipartite graph $G'$ with bipartition $(A', B)$, with some arbitrary ordering of preferences, and include these vertices last in the preferences of the vertices in $B$. Then apply the theorem of Gale and Shapley, giving a stable matching $M'$ of $G'$. Let $M$ be the submatching of $M'$ saturating $A$. We should probably modify the condition of stability in the setting $|A|<|B|$, since $B$ has unmatched vertices, for which stability as previously defined does not say anything. Otherwise, using the old definition, we are done; $M$ is stable, as $M'$ is. Let stability in our case mean in addition, for $a$ matched to $b$ in $M$, there is no $b'\in B$ which $a$ prefers to $b$. Suppose for contradiction there exists $ab\in M$ and $b'\in B$, where $b'$ is not matched in $M$, and $a$ prefers $b'$ to $b$. Since $M'$ is stable, $b'$ prefers some $a'\in A'\setminus A$ to $a$. But this is a contradiction, since all all $b\in B$ have the dummy vertices last in the preference lists.