A Missing preliminaries

A mechanism R is randomized if for every reported valuations b it outputs a randomized allocation, i.e. it returns integral allocations that are drawn from a probability distribution corresponding to a randomized allocation. Since every randomized allocation has an associated expected fractional allocation, the output of a randomized mechanism for reported valuations b can also be interpreted as representing a fractional allocation. Notice that for randomized mechanisms, the definition of NOM takes an expectation over the randomness of the mechanism, and minimum/maximum are over the reports of other agents; we sometimes write "NOM in expectation" when referring specifically to a randomized mechanism. The PS-Lottery algorithm is based on the well-known probabilistic serial algorithm, which outputs fractional allocations that are envy-free. On a high level, the PS-Lottery algorithm uses Birkhoff's algorithm For the sake of completeness, the PS-Lottery algorithm is formally described in Appendix B.1.