Introduction to the cake cutting problem

Speaker : Emma Caizergues
Nokia Bell Labs
Date: 06/03/2024
Time: 10:30 am - 11:30 am
Location: Room 4B01


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.