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 two partners, the problem is easy and was solved in antiquity by the divide and choose protocol. When there are three or more partners, the problem becomes much more challenging.
Two major variants of the problem have been studied: Connected pieces, e.g. if the cake is a 1-dimensional interval then each partner must receive a single sub-interval. If there are partners, only cuts are needed. General pieces, e.g. if the cake is a 1-dimensional interval then each partner can receive a union of disjoint sub-intervals.
Short history
Modern research into the fair cake-cutting problem started in the 1940s. The first fairness criterion studied was proportional division, and a procedure for n partners was soon found.
The stronger criterion of envy-freeness was introduced into the cake-cutting problem by George Gamow and Marvin Stern in 1950s.
A procedure for three partners and general pieces was found in 1960. A procedure for three partners and connected pieces was found only in 1980.
Envy-free division for four or more partners had been an open problem until the 1990s, when three procedures for general pieces and a procedure for connected pieces were 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 were published in the 2000s. For general pieces, the lower bound is Ω(n2). For connected pieces the lower bound is infinity – there is provably no finite protocol for three or more partners.
In the 2010s, several approximation procedures and procedures for special cases were 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.
For the case of connected pieces, it was noted that the hardness result assumes that the entire cake must be divided. If this requirement is replaced by the weaker requirement that every partner receives a proportional value (at least 1/n of the total cake value according to their own valuation), then a bounded procedure for three partners is known, but it has remained an open problem whether there exist bounded-time procedures for four or more partners.
Connected pieces
Existence proof
An envy-free division for n agents with connected pieces always exists under the following mild assumptions: No agent prefers an empty piece over a non-empty piece. The preferences of the agents are continuous. Note that it is not required that the preferences of the agents are represented by an additive function.
The main concept in the proof is the simplex of partitions. Suppose the cake is the interval [0,1]. Each partition with connected pieces can be uniquely represented by n − 1 numbers in [0,1] which represent the cut locations. The union of all partitions is a simplex.
For each partition, each agent has one or more pieces which they weakly prefer. E.g., for the partition represented by "0.3,0.5", one agent may prefer piece #1 (the piece [0,0.3]) while another agent might prefer piece #2 (the piece [0.3,0.5]) while a third agent might prefer both piece #1 and piece #2 (which means that they are indifferent between them but like any of them more than piece #3).