Envy-free cake-cutting
An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation.
When there are only 2 partners, the problem is easy and has been solved in Biblical times by the divide and choose protocol. When there are 3 or more partners, the problem becomes much more challenging.
Two major variants of the problem have been studied:
The modern research of the fair cake-cutting problem has started in the 1940s. The first fairness criterion studied was proportional division, and a procedure for n partners has been found soon.
The stronger criterion of envy-freeness was introduced into the cake-cutting problem by George Gamow and Marvin Stern in 1950s.
A procedure for 3 partners and general pieces was found in 1960. A procedure for 3 partners and connected pieces was found only in 1980.
Envy-free division for 4 or more partners has been an open problem until the 1990s, when three procedures for general pieces and a procedure for connected pieces have been published. All these procedures are unbounded - they may require a number of steps which is not bounded in advance. The procedure for connected pieces may even require an infinite number of steps.
Two lower bounds on the run-time complexity of envy-freeness have been published in the 2000s.
In the 2010s, several approximation procedures and procedures for special cases have been published. The question whether bounded-time procedures exist for the case of general pieces had remained open for a long time. The problem was finally solved in 2016. Haris Aziz and Simon Mackenzie presented a discrete envy-free protocol that requires at most queries. There is still a very large gap between the lower bound and the procedure. As of August 2016, the exact run-time complexity of envy-freeness is still unknown.
...
Wikipedia