Envy-free division of a cake without the "hungry players" assumption

Envy-free division of a cake without the "hungry players" assumption

-
Shira Zerbib, University of Michigan
Fine Hall 224

Consider n players having preferences over a rectangular cake, identified with the interval [0,1]. A classical theorem due to Stromquist ensures that under some conditions it is possible to divide the cake into n interval pieces and assign one piece to each player in an envy-free manner, such that no player strictly prefers a piece that has not been assigned to him. One of these conditions, which has been always considered as crucial, is that the players are "hungry": in every partition of the cake, every player prefers a non-empty piece. We prove that it is still possible to get an envy-free division even if this condition is not satisfied. This was conjectured by Erel Segal-Halevi, who proved it for at most 3 players. The main step in our proof is a new combinatorial lemma in topology, which is reminiscent of the Sperner lemma: Instead of restricting the labels that can appear on each face of the simplex, the lemma considers labelings that enjoy a certain symmetry on the boundary. Joint with Frederic Meunier.