Combinatorics: Shira Zerbib (U. Michigan, Iowa State University) "Envy-free division of a cake without the “hungry players" assumption"

Speaker: Shira Zerbib (U. Michigan, Iowa State University) Title: Envy-free division of a cake without the “hungry players" assumption Abstract: The fair division theorem due to Stromquist (1980) ensures that under some conditions it is possible to divide a rectangular cake into n pieces and assign one piece to each of n players such that no player strictly prefers a piece that has not been assigned to him. One of the conditions of this theorem, 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 the fair division theorem holds even if this condition is not satisfied. This was conjectured by Erel Segal-Halevi (2017), who proved it for at most 3 players. The main step in our proof is a new topological lemma which is reminiscent of Sperner’s 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.

Date: 

Mon, 13/05/2019 - 11:00 to 13:00

Location: 

CS bldg, room B-500, Safra campus