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 a given set of goods or chores. We show that if

p l e n

and each player can choose

k

pieces out of

n

pieces of a cake, then there exist a division of the cake and an allocation of the pieces where at least

f r a c p 2 (k^{2} - k + 1)

players get their desired

k

pieces each. We further show that if

p l e k (n - 1) + 1

and each player can choose

k

pieces, one from each of

k

cakes that are divided into

n

pieces each, then there exist a division of the cakes and allocation of the pieces where at least

f r a c p 2 k (k - 1)

players get their desired

k

pieces. Finally we prove that if

p g e k (n - 1) + 1

and each player can choose one shift in each of

k

days that are partitioned into

n

shifts each, then, given that the salaries of the players are fixed, there exist

n (1 + l n k)

players covering all the shifts, and moreover, if

k = 2

then

n

players suffice. Our proofs combine topological methods and theorems of F"uredi, Lov'asz and Gallai from hypergraph theory.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Fair division with multiple pieces