A Missing preliminaries Allocations. A randomized allocation R = { (p

A, B to denote allocations that are exclusively integral and R for randomized allocations. On a high level, the PS-Lottery algorithm uses Birkhoff's We begin by proving a lemma that highlights a connection between not obvious manipulability and randomized mechanisms that output ex-ante proportional allocations. Lemma 5. Inequality (1) (the worst-case guarantee) is satisfied for every randomized mechanism Note that multiple randomized allocations may have the same expected fractional allocation. Recall that, Birkhoff's algorithm, given a square bistochastic matrix, decomposes it into a convex combination (or a lottery) over permutation matrices. Using Lemma 5 we can prove the following theorem.