finding bipartite matching (stable marriage problem)

Question

Let $T=\{T_1 ...T_5 \}$ be a set of n=5 tutors and $L=\{L_1 ...L_7\}$ be the set of m=7 lectures. The tutors specified lectures they would like to hold (preferences for $T$) and they specified which, in their opinion, tutors should hold a given lecture (preference for $L$)

I do know how to calcualte the matching if both sets have the same cardinality. I could use the Gale–Shapley algorithm in that case. However, how do I deal with problems, where both $T$ and $L$ have preferences but the cardinality is not the same ?

Would appreciate any help.

Answer 1

As suggested by bof, you can extend the list of tutors with two dummy tutors $T_6, T_7$. The preferences for these additional tutors are:

• $T_6, T_7$ have arbitrary preferences (these are irrelevant)
• $L_1, L_2, \dots, L_7$ have their original preferences, appended with $T_6,T_7$ as their lowest preferences (again, the order of $T_6$ and $T_7$ in these preferences is irrelevant).

After running Gale-Shapley on the extended list and receiving matching $M'$, you delete the matchings that involve $T_6$ and $T_7$ from $M'$ to receive $M$. This matching is stable.

Assume (towards a contradiction) that it is not stable. This means that there is a tutor (w.l.o.g. $T_1$) that is assigned to a lecture (w.l.o.g. $L_1$) but would prefer to teach lecture another lecture (w.l.o.g. $L_2$). Also, $L_2$'s preference for $T_1$ is higher than the preference of its match (or $L_2$ is not matched at all). If this is the case, then $M'$ was not stable to begin with - a contradiction.

Answer 2

A slight reformulation of the problem gives you this: Consider a bipartite undirected graph $G = (V_1, V_2, E)$. A matching in $G$ is a subset $M \subseteq E$ such that no two edges from $M$ have a vertex in common.

I am assuming that you are looking for a maximum matching, i.e. a matching with the largest possible cardinality $|M|$.

Assume w.l.o.g. $|V_1| = n$, $|V_2| = m$, $n \leq m$.

Create $m-n$ dummy nodes $V_1'$ and run the matching algorithm on $G' = (V_1 \cup V_1', V_2, E \cup V_1' \times V_2)$, giving you a matching $M'$. You get the maximum matching $M$ you are looking for by removing those edges from $M'$ that have vertices in $V_1'$.

This process obviously yields a matching, but is it a maximum matching? Assume (toward a contradiction), that there is a matching $N$ of larger cardinality than $M$. You can extend this matching to a matching in $G'$ by connecting the nodes in $V_1'$ to free nodes in $V_2$ (these nodes exist because $n \leq m$, and you can connect them, because the vertices in $V_1'$ are connected to all vertices in $V_2$). By this process, you have found a larger matching for $G'$ than $M'$ - a contradiction.