Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Leg G(X,Y,E) be a bipartite graph with two equal-sized parts (|X|=|Y|=n).

An envy-free matching is a matching between $X_1 \subseteq X$ and $Y_1 \subseteq Y$, such that no unmatched $x$ ($\in X-X1$) wants any matched $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?

share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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