Waste Makes Haste: On Fair Division and Partial Divisions

We consider the problem of fairly dividing a heterogeneous continuous good (aka “cake”) among multiple agents, and exhibit the advantages of partial divisions in this context.  We show that, somewhat paradoxically, dividing only part of the cake, while discarding the rest, may increase social welfare (utilitarian, egalitarian, and Pareto efficiency), and provide tight bounds on the possible increase. We also show that computing partial divisions enables to provably reduce the complexity of the division protocols from infinite to bounded time.

No prior knowledge of cake cutting will be assumed.