Envy-free division of a cake: the poisoned case, and other variations

Le lundi 16 mars, Salle C, de 14:00 à 15:00

Frédric Meunier (https://cermics.enpc.fr/~meuniefr/)

Titre: Envy-free division of a cake: the poisoned case, and other variations

Résumé: Given a cake (identified with the interval [0,1]) and players with different tastes, the envy-free cake-cutting problem asks for a partition of the cake into connected pieces so that it is possible to assign the pieces to the players without making any of them jealous. The Stromquist-Woodall theorem ensures the existence of such an envy-free division under mild conditions. Recently, Segal-Halevi asked whether these conditions could be even further relaxed by allowing that some players dislike the cake (e.g., they know the cake has been poisoned). In the traditional setting, all players are "hungry", and always prefer to get something instead of nothing. We provide a partial answer to that question and propose also other extensions, e.g., when suddenly one player disappears. Based on joint works with Florian Frick, Kelsey Houston-Edwards, Francis E. Su, Shira Zerbib.