Mark-Choose-Cut Algorithms For Fair And Strongly Fair Division

This paper proposes a new criterion to evaluate algorithms for cake division, by the number of resulting pieces. Then, inspired by the idea of "cut-and-choose", we present "mark-choose-cut" algorithms for fair and strongly fair cake division problems. They are game-theoretic algorithms. The number of resulting pieces is bounded by 2 × 3n-2 + 1 and 4 × 3n-2 + 1, for fair and strongly fair division respectively.