Super envy-freeness

Super envy-freeness was introduced by Julius Barbanel in 1996.[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 ${\displaystyle c_{1},\ldots ,c_{n}\in \mathbb {R} }$ for which ${\displaystyle c_{1}\cdot V_{1}+\cdots +c_{n}\cdot V_{n}=0}$,

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.

The run-time of the algorithm depends on the properties of the matrix. However, if the value measures are drawn uniformly at random from the unit simplex, with high probability, the runtime is polynomial in n.[3]