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?
I think I can prove your conjecture using Hall's theorem.
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.