Fair division with multiple pieces

Abstract Given a set of p players, we consider problems concerning envy-free allocation of collections of k pieces from given sets of goods or chores. We show that if p = n and each player prefers k pieces in any division of a cake into n pieces, then there exists a division of the cake where at least p k 2 − k + 1 players get their desired k pieces each. We further show that if p = k ( n − 1 ) + 1 and each player prefers k pieces, one piece from each of k cakes, in any division of the k cakes into n pieces each, then there exists a division of the cakes where at least p k 2 − k players get their desired k pieces each. Finally we prove that if p ≥ k ( n − 1 ) + 1 and each player prefers one shift in each of k days that are partitioned into n shifts each, then, given that players prefer empty shifts if possible (e.g., if salaries are fixed and do not depend on the number of working hours), there exist n ( 1 + ln k ) players covering all the shifts, and moreover, if k = 2 then n players suffice. Our proofs combine topological methods and theorems of Furedi, Lovasz and Gallai from hypergraph theory.