  We present a polynomial-time algorithm that computes an ex-ante envy-free
lottery over envy-free up to one item (EF1) deterministic allocations. It has
the following advantages over a recently proposed algorithm: it does not rely
on the linear programming machinery including separation oracles; it is
SD-efficient (both ex-ante and ex-post); and the ex-ante outcome is equivalent
to the outcome returned by the well-known probabilistic serial rule. As a
result, we answer a question raised by Freeman, Shah, and Vaish (2020) whether
the outcome of the probabilistic serial rule can be implemented by ex-post EF1
allocations. In the light of a couple of impossibility results that we prove,
our algorithm can be viewed as satisfying a maximal set of properties. Under
binary utilities, our algorithm is also ex-ante group-strategyproof and ex-ante
Pareto optimal. Finally, we also show that checking whether a given random
allocation can be implemented by a lottery over EF1 and Pareto optimal
allocations is NP-hard.
