A well-known method of dividing a cake between two people is to have the first person to cut the cake and have the second person to have the first pick. This will guarantee that the first person will cut the cake in half so that the second person cannot leave him with a smaller piece.
Now we want to divide the cake among n people. Let's make the following assumptions:
(a) Each person cannot cut the cake more than once
(b) Everyone is logical
(c) Everyone wishes to get the largest possible piece
(d) Everyone wishes to narrow the gap with those who have a bigger piece than he does
(e) No one cares about anyone who has a smaller piece than themselves.
Can you generalize the strategy to n people? Give your logical steps/proof that this strategy will yield a fair result.
The cutting proceeds in n-1 rounds.
On round 1, person 2 (the cutter) cuts a slice (roughly 1 nth of the
cake) which he offers to person 1 (the decider). Person 1 accepts
it if he/she thinks it is fair, or gives it to person 2 if he/she
thinks it is too small.
On round k, the decider is whichever of persons 1,2,...k does not yet
have a slice (there is guaranteed to be exactly one such person).
Person k+1 (the cutter) cuts a slice (roughly equal to 1/(n+1-k) of the
remaining cake) which he offers to the decider. The decider
accepts if he/she thinks it is fair, or gives it
to the cutter if he/she thinks it is too small.
At each round, the decider (which is each person 1 or a person who has
already cut a slice) keeps the cutter (the person k+1) honest, because
if the cutter cuts less than a fair share of the remaining cake, then
the cutter receives the small slice and everybody who has not yet
received a slice gets a windfall.
The only problem is that persons k=1, k+2, ... n will be unhappy if
they disagree with the decider on round k, but this will not happen,
because they are all logical people who can accurately determine
whether or not the proposed slice is less than 1/(n+1-k) of the
remaining cake. In fact, as logical people, they can rely on the
self-interest of the cutter and the decider, and do not even need to
form an opinion until they are deciders.
One fair cut deserves another
