37 — A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents

How do you a split a cake between two people?

Person 1 cuts it in half, person 2 picks a piece.

How do you split a cake between three people?

Unless your knifeperson has superhuman precision, they’re not going to manage to cut it precisely in thirds. And, armed with no extra tools or devices, there’s no way to guarantee that everyone is happy with their piece of cake, even if they are in reality perfectly even.

How do you split a cake between $n$ people?

Read the paper.

This paper explores an algorithm to split an interval $[0, 1]$ into $n$ components, where different agents $1..n$ have different preferences of which part of the interval they want. (In analogy; one person prefers the flower-shaped icing, another person prefers the part of the cake with more cookie bits, etc…)

Before you read more: It’s not simple. You’re not going to manage this at the next party you attend. The worst-case scenario is

cuts… For context, if you performed one trillion cuts per second, you wouldn’t finish splitting a worst-case $n=5$ before the heat-death of the universe.

(Note: for three people to split a cake, the algorithm is much more tractable, and Hannah Fry shows Numberphile how to do it with an actual cake on YouTube.)

This algorithm is interesting to me because it relies heavily on preference instead of mathematical accuracy; it’s trivial to divide a number by $n$ if the distribution of preference is uniform. But if the distributionis uneven — or if people’s preferences differ (gasp!) — the problem is much harder. This system ensures that everyone is happy with their piece of cake even if they’re not the optimal split, which is my favorite part. To understand this, I’d go watch that YouTube video, because it is extremely well-done.