cutting cake & dividing candy
the math of...
Inspiration:
Math models are useful in the social sciences
Social sciences motivate
new math
Takeaways...
Cut a cake into n pieces fairly.
Goal.
Distribute a set of candies among n people fairly.
Indivisible Setting
Divisible Setting
Cut a cake into n pieces fairly.
Goal.
Distribute a set of candies among n people fairly.
Indivisible Setting
Divisible Setting
Cut a cake into n pieces fairly.
Goal.
Distribute a set of candies among n people fairly.
Indivisible Setting
Divisible Setting
0
1
Cut a cake into n pieces fairly.
Goal.
Distribute a set of candies among n people fairly.
Indivisible Setting
Divisible Setting
Each thinks her piece is at least 1/N in her measure.
Notions of fairness
Each thinks her piece is biggest.
Envy-free
Proprortional
Equitable
Each views his piece as the same as
everyone else views their piece.
Efficient
There is no other division that
dominates this one for ALL players.
divide one cake
between two people
nicely
Hesiod's Theogony:
Prometheus cuts ox in two, offers Zeus choice
Old Testament Book of Genesis:
Abraham offers Lot choice: land to left or right
Mining in the Ocean:
The United Nations Convention on the Law of the Sea applies a procedure similar to divide-and-choose for allocating areas in the ocean among countries.
Protocol dating back ages...
I cut, you choose.
1 cake, 2 people.
divide one cake
between N people
proportionally
1 cake, N people.
Goal: PROP
0
1
1 cake, N people.
Goal: PROP
0
1
stop!
1 cake, N people.
Goal: PROP
A referee starts moving a knife from left to right across a cake.
As soon as any player feels the piece to the left of the knife is worth a fair share, they shout “STOP.”
The referee then cuts the cake at the current knife position and the player who called stop gets the piece to the left of the knife.
This procedure continues until there is only one player left. The player left gets the remaining cake.
1 cake, N people.
Goal: PROP
Each partner is asked to draw a line dividing the cake into a right and left part such that he believes the ratio is ⌊n/2⌋:⌈n/2⌉.
1 cake, N people.
Goal: PROP
The algorithm sorts the n lines in increasing order and cuts the cake in the median of the lines, i.e. at the ⌊n/2⌋th line.
The algorithm assigns to each of the two parts the partners whose line is inside that part, i.e. the partners that drew the first ⌊n/2⌋ lines get assigned to the left part, the others to the right part. Each part is divided recursively among the partners assigned to it.
divide one cake
between 3 people
in an envy-free manner
1 cake, 3 people.
Goal: EF division
1 cake, 3 people.
Goal: EF division
1 cake, 3 people.
Goal: EF division
trimmings
P1 divides the cake into three pieces they consider of equal size.
Let's call A the largest piece according to P2.
P2 cuts off a bit of A to make it the same size as the second largest.
Now A is divided into: the trimmed piece A1 and the trimmings A2.
Leave the trimmings A2 to the side for now.
If P2 thinks that the two largest parts are equal (such that no trimming is needed), then each player chooses a part in this order: P3, P2 and finally P1.
P3 chooses a piece among A1 and the two other pieces.
P2 chooses a piece with the limitation that if P3 didn't choose A1, P2 must choose it.
P1 chooses the last piece leaving just the trimmings A2 to be divided.
PB cuts A2 into three equal pieces.
The trimmed piece A1 has been chosen by either P2 or P3;
let's call the player who chose it PA and the other player PB.
PA chooses a piece of A2 - we name it A21.
P1 chooses a piece of A2 - we name it A22.
PB chooses the last remaining piece of A2 - we name it A23.
Goal: Envy-free
divide one cake
between N people
in an envy-free manner
In the 2010s, several approximation procedures and procedures for special cases were published.
The question whether bounded-time procedures exist for the case of general pieces had remained open for a long time.
The problem was finally solved in 2016.
Haris Aziz and Simon Mackenzie presented a discrete envy-free protocol that requires at most \(n^{n^{n^{n^{n^n}}}}\) or \(n \uparrow \uparrow 6\) queries.
There is still a very large gap between the lower bound and the procedure The exact run-time complexity of envy-freeness is still unknown.
Label vertices of a triangulated triangle with 1, 2, 3 obeying: each corner keeps its own label; boundary vertices between corners i, j use only labels i or j.
Call every 1-2 edge a door. On the edge between corners 1 and 2, labels transition from 1 to 2, so there is an odd number of doors. The other two sides have no 1-2 edges.
Each non-rainbow triangle has 0 or 2 doors; each rainbow (1-2-3) triangle has exactly 1. Since boundary doors are odd, rainbow triangles must be odd too.
Click interior/boundary vertices to change labels!
Triangulate!
- A point \((x_1, x_2, x_3)\) in the simplex with \(x_1+x_2+x_3=1\) represents a division of the cake into three pieces of sizes \(x_1, x_2, x_3\).
- Each vertex is a division. Assign "owners".
- So ask owner at each vertex: "which piece would you choose in this division?"
- The answer is the label (1, 2, or 3).
- Corner \((1,0,0)\): all cake is piece 1 — owner must prefer piece 1. Similarly for the other corners. Sperner condition is satisfied!
- By Sperner's lemma, a rainbow triangle exists: three nearly-identical divisions where each player prefers a different piece — an approximately envy-free allocation.
Approximate Notions of fairness
Each thinks her piece is biggest,
Envy-free up to one item
after removing their most valued piece from
the other agent's bundle.