Fair cutting of a cake

259 Views Asked by At

For the fair cutting of a cake into n pieces for n people, is it sufficient for one person to cut the cake, and for them to get the last pick of piece?

If any one piece is bigger than 1/n, another person will take that piece. If any one piece is smaller than 1/n, then the cutter may end up with that piece. Therefore the cutter has an incentive to cut the cake fairly.

Is this correct?

2

There are 2 best solutions below

3
On

You want to make it so that it is impossible for any number of people to conceive a plan so that the $k$ of them altogether get more than a fraction of $\frac kn$ of the cake.

That's why the method you suggest doesn't answer the question, because the person who cuts and the first person who picks can arrange so that one part is huge and the other $n-1$ are tiny.

A correct version with $3$ people that can be straightforwardly generalised:

  • Person $1$ splits the cake in $2$ parts.

  • Person $2$ chooses one, Person $1$ gets the other.

  • Each of $1$ and $2$ splits their own part into $3$ parts.

  • Person $3$ picks one (of the three parts) from each of them.

You can easily check that each person can selfishly ensure that they will get at least a third of the cake.

5
On

No your solution is not an acceptable one, as the order in which the people would pick the slices will introduce jealousy among them.

This is a highly non trivial problem for which a general algorithm was only given recently, by Haris Aziz and Simon Mackenzie (2016). In particular, their envy-free protocol has an complexity upper bounded by $n^{n^{n^{n^{n^{n}}}}}$. So when considering cake, be prepared for a lot of cutting, and do not hope your slices to look like anything you would actually want to eat afterwards.

You can take a look at this introductory article on the subject that gives a reference to the general algorithm, or on arxiv directly for a rigorous analysis.