Súper libre de envidia

Tipo de división justa de los recursos

Una división súper libre de envidia es una especie de división justa . Es una división de recursos entre n socios, en la que cada socio valora su participación en estrictamente más que su parte debida de 1/ n del valor total y, simultáneamente, valora la participación de todos los demás socios en estrictamente menos. que 1/ n . Formalmente, en una división súper libre de envidia de un recurso C entre n socios, cada socio i , con una medida de valor Vi _, recibe una participación X _i tal que:

${\displaystyle V_{i}(X_{i})>V_{i}(C)/n~~{\text{ and }}~~\forall j\neq i:V_{i}(X_{j})<V_{i}(C)/n}$.

Este es un fuerte requisito de equidad: es más fuerte que la ausencia de envidia y la superproporcionalidad .

Existencia

Julius Barbanel introdujo la súper ausencia de envidia en 1996. ^[1] Demostró que existe un corte de pastel súper libre de envidia si, y sólo, si las medidas de valor de los n socios son linealmente independientes . "Linealmente independiente" significa que no existe un vector de n números reales distintos de cero para los cuales , ${\displaystyle c_{1},\ldots ,c_{n}\in \mathbb {R} }$ ${\displaystyle c_{1}\cdot V_{1}+\cdots +c_{n}\cdot V_{n}=0}$

Cálculo

En 1999, ^[2] William Webb presentó un algoritmo que encuentra una asignación súper libre de envidia en este caso. Su algoritmo se basa en un testimonio de que las medidas son independientes. Un testigo es una matriz n por n , en cuyo elemento ( i , j ) es el valor asignado por el agente i a alguna pieza j (donde las piezas 1,..., n pueden ser cualquier partición del pastel, por ejemplo (por ejemplo, partición en intervalos de igual longitud). La matriz debe ser invertible ; esto es un testimonio de la independencia lineal de las medidas.

Usando dicha matriz, el algoritmo divide cada una de las n piezas en una división casi exacta . Se puede demostrar que, si la matriz es invertible y el factor de aproximación es suficientemente pequeño (con respecto a los valores en el inverso de la matriz), entonces la asignación resultante está realmente libre de envidia.

El tiempo de ejecución del algoritmo depende de las propiedades de la matriz. Sin embargo, si las medidas de valor se extraen uniformemente al azar de la unidad simplex, con alta probabilidad, el tiempo de ejecución es polinomial en n . ^[3]

Referencias

1. Barbanel, Julio B. (1 de enero de 1996). "División de tartas súper sin envidia e independencia de medidas". Revista de Análisis y Aplicaciones Matemáticas . 197 (1): 54–60. doi : 10.1006/S0022-247X(96)90006-2 . ISSN  0022-247X.
2. Webb, William A. (1 de noviembre de 1999). "Un algoritmo para una división de pasteles súper libre de envidia". Revista de Análisis y Aplicaciones Matemáticas . 239 (1): 175-179. doi : 10.1006/jmaa.1999.6581 . ISSN  0022-247X.
3. Chèze, Guillaume (5 de mayo de 2020). "Corte de pastel sin envidia: un número polinómico de consultas con alta probabilidad". arXiv : 2005.01982 [cs.CC].