How to Cut a Discrete Cake Fairly

Cake-cutting is a fundamental model of dividing a heterogeneous resource, such as land, broadcast time, and advertisement space. In this study, we consider the problem of dividing a discrete cake fairly in which the indivisible goods are aligned on a path and agents are interested in receiving a connected subset of items. We prove that a connected division of indivisible items satisfying a discrete counterpart of envy-freeness, called envy-freeness up to one good (EF1), always exists for any number of agents n with monotone valuations. Our result settles an open question raised by Bilò et al. (2019) , who proved that an EF1 connected division always exists for the number of agents n 4. Moreover, the proof can be extended to show the following (1) "secretive" and ( 2 ) "extra" versions: (1) for n agents with monotone valuations, the path can be divided into n connected bundles such that an EF1 assignment of the remaining bundles can be made to the other agents for any selection made by the "secretive agent"; (2) for n + 1 agents with monotone valuations, the path can be divided into n connected bundles such that when any "extra agent" leaves, an EF1 assignment of the bundles can be made to the remaining agents.