Title: Bipartite Envy-Free Matching,
Abstract: Bipartite Envy-Free Matching (BEFM) is a relaxation of perfect matching. In a
bipartite graph with parts X and Y, a BEFM is a matching of some vertices in X
to some vertices in Y, such that each unmatched vertex in X is not adjacent to
any matched vertex in Y (so the unmatched vertices do not "envy" the matched
ones). The empty matching is always a BEFM. This paper presents sufficient and
necessary conditions for the existence of a non-empty BEFM. These conditions
are based on cardinality of neighbor-sets, similarly to Hall's condition for
the existence of a perfect matching. The conditions can be verified in
polynomial time, and in case they are satisfied, a non-empty BEFM can be found
by a polynomial-time algorithm. The paper presents some applications of BEFM as
a subroutine in fair division algorithms.