Minimal Number of Cuts for Fair Division

Abstract

The problem of fairly dividing a piece of cake apparently originates with Hugo Steinhaus in 1948 at which time he raised the question of the number of cuts required in fair division algorithms. In this paper, an algorithm requiring $O(n\log n)$ cuts is given, improving known algorithms which require $O(n^2)$ or more cuts. The algorithm is shown to be optimal in a certain class, and general algorithms are shown to allow a certain freedom of participants to choose pieces.