Super envy-freeness

Strong envy-freeness and super envy-freeness are two related conditions for fair division.^[1][2] Both of them strengthen the condition of envy-freeness (EF). Speficially, a division of a resource among n partners is called -

• envy-free - if each partner values his/her share at least as much as the share of any other partner;
• strongly envy-free - if each partner values his/her share strictly more than the share of any other partner;
• super envy-free - if each partner values his/her share strictly more than the due share of 1/n, and values the share of any other partner strictly less than 1/n.

Formally, consider a division of a resource C among n partners, where each partner i, with value measure V_i, receives a share X_i, The division is called:

• envy-free - if ${\displaystyle V_{i}(X_{i})\geq V_{i}(X_{j})}$ for all i ≠ j;
• strongly envy-free - if ${\displaystyle V_{i}(X_{i})>V_{i}(X_{j})}$ for all i ≠ j;
• super envy-free - if ${\displaystyle V_{i}(X_{i})>V_{i}(C)/n~~{\text{ and }}~~\forall j\neq i:V_{i}(X_{j})<V_{i}(C)/n}$.

Super envy-freeness implies strong envy-freeness; strong envy-freeness implies both envy-freeness and super-proportionality.

This is a strong fairness requirement: it is stronger than both envy-freeness and super-proportionality.

Existence

Strong EF and super EF were introduced by Julius Barbanel in 1996^[1] and detailed in his later book.^{[2]: Chapter 5} He proved that

• a strongly envy-free cake-cutting exists if-and-only-if the value measures of the n partners are pairwise-different (no two measures are equal).
• 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}$,

The same holds both for goods and for chores.^{[2]: Chapter 5}

Computation

In 1999,^[3] William Webb presented an algorithm that finds a super-envy-free allocation in when all measures are linearly independent. 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, Cheze^[4] later proved that, if the value measures are drawn uniformly at random from the unit simplex, with high probability, the runtime is polynomial in n.

Hyper envy-freeness

Cheze and Amodei^[5] generalized the notion of super envy-freeness to agents with different entitlements and different comparison signs; they called the generalized notion hyper envy-freeness. They provided an efficient algorithm for deciding whether a particular hyper envy-free cake allocation exists. The algorithm uses the Gram matrix of the instance.