Envy-Free Cake-Cutting for Four Agents

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 epsilon-envy-free allocation. For monotone valuations of cake pieces, Deng, Qi, and Saberi (2012) gave an efficient (poly(log(1/epsilon)) queries) algorithm for three agents and posed the open problem of four (or more) monotone agents. Even for the special case of additive valuations, Branzei and Nisan (2022) conjectured an Omega(1/epsilon) lower bound on the number of queries for four agents. We provide the first efficient algorithm for finding a connected epsilon-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/epsilon) queries in the black-box model, and even poly(1/epsilon) 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.