The stronger criterion of envy-freeness was introduced into the cake-cutting problem by George Gamow and Marvin Stern in 1950s.
The question whether bounded-time procedures exist for the case of general pieces had remained open for a long time.
Haris Aziz and Simon Mackenzie presented a discrete envy-free protocol that requires at most
For the case of connected pieces, it was noted that the hardness result assumes that the entire cake must be divided.
As we show in the following subsection, it may be impossible to find an envy-free cake-cutting with connected pieces with a finite number of queries.
An envy-free division with connected pieces for 3 or more agents cannot be found by a finite protocol in the Robertson–Webb query model.
[4] The reason this result doesn't contradict the previously mentioned algorithms is that they are not finite in the mathematical sense.
Since envy-free cake-cutting with connected pieces cannot be done in finite time, cake-cutters have tried to find work-arounds.
Length-based approximation uses the following definitions: The parameter δ represents the tolerance of the partners in units of length.
E.g., if land is divided and the partners agree that a difference of 0.01 meter in the location of the border is not relevant to them, then it makes sense to look for a 0.01-multi-partition which is envy-free.
Deng at al[6] present a modification of Simmons' cake-cutting protocol which finds an envy-free δ-multi-partition using
Even when the utility functions are given explicitly by polynomial-time algorithms, the envy-free cake-cutting problem is PPAD-complete.
[6] Hence, Deng et al.'s results prove that, if all partners have Lipschitz continuous valuations, an ε-envy-free partition can be found with
With additive valuations, for any ε > 0, an ε-envy-free connected cake-cutting requires at least Ω(log ε−1) queries.
For 4 or more agents, the best known protocol requires O(n ε−1), which shows an exponential gap in the query complexity.
[8] Offline calculation is a second work-around that finds a totally-envy-free division but only for a restricted class of valuations.
The currently known bounds are: It is not known whether there exists a bounded-time envy-free and proportional division procedure for four or more partners with connected pieces.
As explained above, when free disposal is allowed, the procedures are measured by their level of proportionality - the value that they guarantee to all agents.
The following results are currently known:[12] An envy-free division exists even with non-additive value functions, multi-dimensional simplex cake, and the pieces must be polytopes.
[15] For five partners, a procedure by Saberi and Wang makes an envy-free division with a bounded number of cuts.
For four or more partners, there are three algorithms which are finite but unbounded - there is no fixed bound on the number of cuts required.
[17] There are three such algorithms: Although the protocols are different, the main idea behind them is similar: Divide the cake to a finite but unbounded number of "crumbs", each of which is so small that its value for all partners is negligible.
[19] The question of whether envy-free cake-cutting can be done in bounded time for four or more partners had been open for many years.
A reentrant variant of the last diminisher protocol finds an additive approximation to an envy-free division in bounded time.
In both cases, the algorithm gathers information only about intervals whose end-points were mentioned in the query or in the reply.
C. Suppose all partners answer all queries as if their value measure is uniform (i.e. the value of an interval is equal to its length).
Zeng presented an alternative algorithm for approximate weighted envy-free division, which requires a smaller number of cuts.
To see this, note that every weighted-envy-free division is also weighted-proportional with the same weight-vector; this means that, for every agent i with value measure Vi:
It is known that weighted-proportional allocation with connected pieces may not exist: see proportional cake-cutting with different entitlements for an example.
Note that there is an alternative definition of weighted-envy-free division, where the weights are assigned to pieces rather than to agents.