  With very few exceptions, recent research in fair division has mostly focused
on deterministic allocations. Deviating from this trend, we study the fairness
notion of interim envy-freeness (iEF) for lotteries over allocations, which
serves as a sweet spot between the too stringent notion of ex-post
envy-freeness and the very weak notion of ex-ante envy-freeness. iEF is a
natural generalization of envy-freeness to random allocations in the sense that
a deterministic envy-free allocation is iEF (when viewed as a degenerate
lottery). It is also certainly meaningful as it allows for a richer solution
space, which includes solutions that are provably better than envy-freeness
according to several criteria. Our analysis relates iEF to other fairness
notions as well, and reveals tradeoffs between iEF and efficiency. Even though
several of our results apply to general fair division problems, we are
particularly interested in instances with equal numbers of agents and items
where allocations are perfect matchings of the items to the agents.
Envy-freeness can be trivially decided and (when it can be achieved, it)
implies full efficiency in this setting. Although computing iEF allocations in
matching allocation instances is considerably more challenging, we show how to
compute them in polynomial time, while also maximizing several efficiency
objectives. Our algorithms use the ellipsoid method for linear programming and
efficient solutions to a novel variant of the bipartite matching problem as a
separation oracle. We also study the extension of interim envy-freeness notion
when payments to or from the agents are allowed. We present a series of results
on two optimization problems, including a generalization of the classical rent
division problem to random allocations using interim envy-freeness as the
solution concept.
