A super-envy-free division is a kind of a fair division. It is a division of resources among n partners, in which each partner values his/her share at strictly more than his/her due share of 1/n of the total value, and simultaneously, values the share of every other partner at strictly less than 1/n. Formally, in a super-envy-free division of a resource C among n partners, each partner i, with value measure Vi, receives a share Xi such that:

.

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

Existence

edit

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   for which  ,

Computation

edit

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]

References

edit
  1. ^ Barbanel, Julius B. (1996-01-01). "Super Envy-Free Cake Division and Independence of Measures". Journal of Mathematical Analysis and Applications. 197 (1): 54–60. doi:10.1006/S0022-247X(96)90006-2. ISSN 0022-247X.
  2. ^ Webb, William A. (1999-11-01). "An Algorithm For Super Envy-Free Cake Division". Journal of Mathematical Analysis and Applications. 239 (1): 175–179. doi:10.1006/jmaa.1999.6581. ISSN 0022-247X.
  3. ^ Chèze, Guillaume (2020-05-05). "Envy-free cake cutting: A polynomial number of queries with high probability". arXiv:2005.01982 [cs.CC].