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

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

Date: 
Mon, 13/05/201911:00-13:00
Location: 
CS bldg, room B-500, Safra campus
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.