Introduction to the cake cutting problem

Speaker: Emma Caizergues (Nokia Bell Labs)
Check our website : www.lincs.fr
Abstract:
The cake cutting problem arises when a cake must be divided fairly among individuals who have different preferences. In this presentation, after a brief explanation of the model, we will introduce different definitions of “dividing fairly”, exploring what it means to achieve fairness in such a scenario. Notably, we will emphasize on “envy-freeness” (no one envies the piece of cake allocated to another person), especially by showing an algorithm that achieves it when the number of individuals is 2 or 3. This will be the occasion to talk about the computational complexity of allocation algorithms, and the theoretical bounds obtained so far in the literature.