“A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents”, Haris Aziz, Simon Mackenzie2016-04-13 (algorithms)⁠:

We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from n agents. The problem has received attention in computer science, mathematics, and economics. It has been a major open problem whether there exists a discrete and bounded envy-free protocol.

We resolve the problem by proposing a discrete and bounded envy-free protocol for any number of agents. The maximum number of queries required by the protocol is nⁿⁿⁿⁿⁿ.

We additionally show that even if we do not run our protocol to completion, it can find in at most n³(n³)ⁿ queries a partial allocation of the cake that achieves proportionality (each agent gets at least 1⁄n of the value of the whole cake) and envy-freeness. Finally we show that an envy-free partial allocation can be computed in at most n³(n³)ⁿ queries such that each agent gets a connected piece that gives the agent at least 1⁄(3n) of the value of the whole cake.