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. This fundamental fair division problem is known to always admit a solution where each agent obtains a connected piece of the cake.

For monotone valuations of cake pieces, Deng, Qi, and Saberi (2012) gave an efficient algorithm for three agents, and it was conjectured by Brânzei and Nisan (2022) that the problem for four agents is hard. Surprisingly, we show that there is an efficient algorithm for the case of four agents. We also prove that as soon as the valuations are allowed to be non-monotone, the problem becomes hard, even in the communication model. The question for five (or more) monotone agents remains open.

Based on joint work with Aviad Rubinstein that appeared at FOCS 2023.

Hosted by the Centre for Computational Finance and Economic Agents.