# Envy-free matching

Let $G \left(X, Y, E\right)$ be a bipartite graph with two equal-sized parts (that is, $|X|=|Y|=n$).

An envy-free matching is a perfect matching between two subsets $X_1 \subseteq X$ and $Y_1 \subseteq Y$ such that no unmatched $x$ (that is, $x \in X \setminus X_1$) wants (i.e., is connected to) any matched $y$ (that is, $y \in Y_1$).

For example, in the following graph (where an edge from $x$ to $y$ means that $x$ wants $y$):

• $x_1\ wants\ y_2$
• $x_2\ wants\ y_1,y_2,y_3$
• $x_3\ wants\ y_2$

an envy-free matching is: $x_2 \to y_1$, since $x_1$ and $x_3$ don't want $y_1$ so they are not envious.

Note that an envy-free matching may be different from the maximum-size matching. In the above graph, there is a maximum matching of size 2 ($x_2 \to y_1,x_1\to y_2$), but it is not envy-free because $x_3$ is envious.

In the following graph:

• $x_1\ wants\ y_2$
• $x_2\ wants\ y_2$

the only envy-free matching is the empty matching, since if $y_2$ is matched to $x_i$, then $x_{3-i}$ is envious.

My conjecture is that, if every $y$ is wanted by at least one $x$, then there is a non-empty envy-free matching.

Can you prove or disprove it?

• After trying some examples, it seems to be true, but I can't proof it. Maybe you can use induction. – Ragnar Dec 29 '13 at 14:05
• Sounds like "stable Marriage" Theorem. – hbm Dec 29 '13 at 18:21
• @hbm in the stable marrige problem, each man has a preference order over the women, and vice versa. The problem I presented is binary - each man either wants a woman or does not want her. – Erel Segal-Halevi Dec 30 '13 at 5:33

First of all, any perfect matching is also an envy-free matching, so if $G$ satisfies Hall's condition then there is an envy-free matching.
Otherwise let $S \subseteq X$ be a maximal subset such that $|N(S)|<|S|$. If $S=X$ then any $y$ that isn't in $N(S)$ isn't wanted by any $x$. If $|S|<n$ then the subgraph of $G$ on the vertices$X\smallsetminus S,Y \smallsetminus N(S)$ satisfies Hall's condition (otherwise we can make $S$ larger), and so it has a matching that matches all of the vertices in $X\smallsetminus S$. This matching is envy-free.