Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division

A matching in a bipartite graph $G:=(X + Y,E)$ is said to be envy-free if no unmatched vertex in $X$ is adjacent to a mathced vertex in $Y$. Every perfect matching is envy-free, but envy-free matchings may exist even when perfect matchings do not. We provide a polynomial-time algorithm for finding an envy-free matching of maximum cardinality. For edge-weighted bipartite graphs, we provide a polynomial-time algorithm for finding a maximum-cardinality envy-free matching of minimum weight. We show how envy-free matchings can be used in various fair division problems with either continuous resources ("cakes") or discrete ones. In particular, we show a symmetric algorithm for proportional cake-cutting, an algorithm for $1$-out-of-$(2n-2)$ maximin-share allocation of discrete goods, and an algorithm for $1$-out-of-$\lfloor 2n/3\rfloor$ maximin-share allocation of discrete bads (chores) among $n$ agents.