Seminar "Geometry and Combinatorics"

Envy-free divisions of cakes: recent results and open questions

by Prof. Frédéric Meunier

Europe/Moscow
Zoom

Zoom

Description

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 from 1980 ensures the existence of such an envy-free division under mild conditions. 

Recently, there has been a surge of interest for this problem from various communities (computer science, game theory, topological combinatorics) and several new versions have been proved, e.g., the cake can now be poisoned, or there can be several cakes with joint preferences, or the cake can be discrete (i.e., it is actually  a necklace).

This talk aims at providing the current state of knowledge on that topic and at reviewing the main open questions and challenges that it offers.