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.

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