A note on cake cutting

AbstractThe algorithmic aspects of the following problem are investigated: n (≥2) persons want to cut a cake into n shares so that every person will get at least 1/n of the cake by his own measure and so that the number of cuts made on the cake is minimal. The cutting process is to be governed by a protocol (computer program). It is shown that no deterministic protocol exists which is fair (in a sense defined in the text) and results in at most n − 1 cuts. An O(n log n)-cut deterministic protocol and an O(n)-cut randomized protocol are given explicitly and a deterministic fair protocol with 4 cuts for n=4 is described in the appendix