Redividing the Cake

Abstract

A heterogeneous resource, such as a land-estate, is already divided among several agents in an unfair way. The challenge is to re-divide it among the agents in a way that balances fairness with ownership rights. We present re-division protocols that attain various combinations of fairness and ownership rights, in various settings differing in the geometric constraints on the allotments: (a) no geometric constraints; (b) connectivity --- the cake is a one-dimensional interval and each piece must be a contiguous interval; (c) rectangularity --- the cake is a two-dimensional rectangle and the pieces should be rectangles; (d) convexity --- the cake is a two-dimensional convex polygon and the pieces should be convex.