Envy free cake cutting method works for any number of people
Cutting a Cake For Human Consumption: An Elementary $n$-agent Cake Cutting Protocol
Computer Science and Game Theory
Summary
The problem is how to divide a cake fairly among any number of people so no one feels jealous of another's share. The authors provide a clear step-by-step method that guarantees everyone is satisfied without envy, using a limited number of questions. They base their approach on previously known ideas but organize them in a simpler way with a short proof. This makes the cake-cutting process easier to understand and apply.
What this means in practice
- •For resource allocation teams: Create procedures to fairly divide resources among multiple parties without causing envy, using a protocol that guarantees bounded interaction steps.
- •For online dispute resolution platforms: Implement fair division algorithms that ensure envy-free outcomes when dividing shared digital assets or benefits among users.
A theory result. No direct application yet.
Authors
Alexandros Psomas
Abstract
We give a bounded envy-free cake-cutting protocol for any number $n$ of agents in the Robertson--Webb model, with a short, self-contained, and elementary correctness proof. The protocol uses $2^{O(n \log n)}$ queries. Most ingredients are already known and well understood in the fair division literature; our main contribution is a simpler organization of these ideas into a protocol whose complete description and proof fit in a few pages.