In the envy-free cake-cutting problem we are given a resource, usually called a cake and represented as the 0, 1 interval, and a set of n agents with heterogeneous preferences over pieces of the cake. The goal is to divide the cake among the n agents such that no agent is envious of any other agent. Even under a very general preferences model, this fundamental fair division problem is known to always admit an exact solution where each agent obtains a connected piece of the cake; we study the complexity of finding an approximate solution, i.e., a connected ε-envy-free allocation. For monotone valuations of cake pieces, Deng, Qi, and Saberi (2012) gave an efficient (poly(log (1/ε)) queries) algorithm for three agents and posed the open problem of four (or more) monotone agents. Even for the special case of additive valuations, Brânzei and Nisan (2022) conjectured an Ω (1/ε) lower bound on the number of queries for four agents. We provide the first efficient algorithm for finding a connected ε-envy-free allocation with four monotone agents. We also prove that as soon as valuations are allowed to be non-monotone , the problem becomes hard: it becomes PPAD/-hard, requires poly(1/ε) queries in the black-box model, and even poly(1/ε) communication complexity . This constitutes, to the best of our knowledge, the first intractability result for any version of the cake-cutting problem in the communication complexity model.
Hollender et al. (Tue,) studied this question.