.This is a strong fairness requirement: it is stronger than both envy-freeness and super-proportionality.
[1] He proved that a super-envy-free cake-cutting exists if-and-only-if the value measures of the n partners are linearly independent.
"Linearly independent" means that there is no vector of n non-zero real numbers
, In 1999,[2] William Webb presented an algorithm that finds a super-envy-free allocation in this case.
His algorithm is based on a witness to the fact that the measures are independent.
A witness is an n-by-n matrix, in which element (i,j) is the value assigned by agent i to some piece j (where the pieces 1,...,n can be any partition of the cake, for example, partition to equal-length intervals).
The matrix should be invertible - this is a witness to the linear independence of the measures.
Using such a matrix, the algorithm partitions each of the n pieces in a near-exact division.
It can be shown that, if the matrix is invertible and the approximation factor is sufficiently small (w.r.t.
the values in the inverse of the matrix), then the resulting allocation is indeed super-envy-free.
However, if the value measures are drawn uniformly at random from the unit simplex, with high probability, the runtime is polynomial in n.[3]