Super envy-freeness
Super envy-freeness
- Strong envy-freeness and super envy-freeness** are two related conditions for [[fair-division]]. 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 Vi, receives a share Xi, The division is called:
- envy-free - if <math>V_i(X_i) \geq V_i(X_j) </math> for all i ≠ j;
- strongly envy-free - if <math>V_i(X_i) > V_i(X_j) </math> for all i ≠ j;
- super envy-free - if <math>V_i(X_i) > V_i(C)/n ~~ \text{ and } ~~ \forall j\neq i:V_i(X_j) < V_i(C)/n </math>.
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 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 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.