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?

  • $\begingroup$ After trying some examples, it seems to be true, but I can't proof it. Maybe you can use induction. $\endgroup$ – Ragnar Dec 29 '13 at 14:05
  • $\begingroup$ Sounds like "stable Marriage" Theorem. $\endgroup$ – hbm Dec 29 '13 at 18:21
  • $\begingroup$ @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. $\endgroup$ – Erel Segal-Halevi Dec 30 '13 at 5:33

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.

  • $\begingroup$ I converted your proof into an algorithm and added a necessary condition and some examples: arxiv.org/abs/1901.09527 you are welcome to join the paper if you want (but you will have to read it carefully to ensure there are no bugs... my proofs often have bugs) $\endgroup$ – Erel Segal-Halevi Jan 29 at 2:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.