Procedimiento de gráfico de envidia

El procedimiento del grafo de envidia (también llamado procedimiento de ciclos de envidia ) es un método para la asignación equitativa de artículos . Puede ser utilizado por varias personas que desean repartirse entre sí varios artículos discretos, como reliquias familiares, dulces o plazas en una clase.

Idealmente, nos gustaría que la asignación fuera libre de envidia (EF), es decir, que cada agente recibiera una cesta que prefiriera sobre las cestas de todos los demás agentes. Sin embargo, los artículos son discretos y no se pueden cortar, por lo que una asignación libre de envidia podría ser imposible (por ejemplo, consideremos un solo artículo y dos agentes). El procedimiento del grafo de envidia tiene como objetivo lograr la opción "siguiente mejor" —libre de envidia hasta como máximo un solo bien (EF1)—: encuentra una asignación en la que la envidia de cada persona hacia cualquier otra persona está limitada por la utilidad marginal máxima que obtiene de un solo artículo. En otras palabras, para cada par de personas i y j , existe un artículo tal que, si se elimina ese artículo, i no envidia a j .

El procedimiento fue presentado por Lipton y Markakis y Mossel y Saberi ^{[ 1 ]} y también se describe en . ^{[ 2 ] : 300–301}

El procedimiento del grafo de envidia supone que cada persona tiene una función de utilidad cardinal sobre conjuntos de artículos. Esta función de utilidad debe ser monótona (la utilidad de un conjunto es al menos tan grande como la utilidad de sus subconjuntos). Sin embargo, no tiene por qué ser aditiva. Es decir, no se supone que los artículos sean bienes independientes .

Los agentes no tienen que informar explícitamente sobre su utilidad cardinal: basta con que sepan cómo clasificar los conjuntos de bienes y servicios.

1. Ordena los artículos arbitrariamente.
2. Mientras haya elementos sin asignar:
   • Asegúrese de que haya un agente que nadie envidie , un agente al que ningún otro agente envidie.
   • Dale el siguiente artículo al agente que no es envidiado.

En el paso 2, si no hay ningún agente no envidiado, significa que existe un ciclo dirigido en el grafo de envidia : un grafo dirigido en el que cada agente apunta a todos los agentes que envidia. Los ciclos se pueden eliminar mediante el intercambio cíclico de paquetes. Una vez eliminados todos los ciclos, el grafo de envidia debe tener un nodo sin aristas entrantes; este nodo representa a un agente no envidiado.

La asignación resultante no es necesariamente EF, pero está libre de envidia, salvo un elemento. Esto se cumple no solo en la asignación final, sino también en cada asignación intermedia: dado que siempre se le asigna un elemento a un agente no envidiado, la envidia de todos los demás agentes después de esa asignación es, como máximo, de un solo elemento.

Supongamos que hay m elementos. Cada asignación de un elemento agrega al grafo de envidia como máximo n -1 aristas. Por lo tanto, como máximo${\displaystyle (n-1)m}$Se añaden aristas en general. Cada eliminación de ciclo elimina al menos dos aristas. Por lo tanto, necesitamos ejecutar el paso de eliminación de ciclo como máximo${\displaystyle (n-1)m/2}$veces. Encontrar un ciclo se puede hacer en tiempo ${\displaystyle O(n^{2})}$utilizando, por ejemplo, la búsqueda en profundidad . En general, el tiempo de ejecución es${\displaystyle O(n^{3}m)}$.

En estos ejemplos, las preferencias van del 1 al 3, donde cuanto mayor sea el número, mayor será la preferencia. Además, a, b y c son personas, mientras que X, Y y Z son objetos.

1) Con 3 personas y 3 objetos, cada asignación posible dará como resultado algo diferente. Esto ocurre cuando las tres personas tienen las mismas preferencias. Hay seis maneras diferentes de asignar los objetos:

Al principio, como nadie tiene nada, todos son agentes no envidiados, y esto es igual en todos los casos. En caso de empate, resolvemos los empates entre agentes no envidiados en orden lexicográfico .

1. Para empezar, le damos el objeto X a a. Después, b y c son agentes que no sienten envidia. Ahora le damos el objeto Y a b. Después, c es un agente que no siente envidia. Ahora le damos el último objeto Z a c. Ahora c siente envidia de b y a, b siente envidia de a y a no siente envidia de nadie. Como ya no hay ciclo de envidia ni más objetos que repartir, el procedimiento termina y el resultado final es que a recibe X, b recibe Y y c recibe Z.
2. Para empezar, le damos el objeto X a a. Después, tanto b como c son agentes que no sienten envidia. Ahora le damos el objeto Z a b. Después, c es un agente que no siente envidia. Ahora le damos el último objeto Y a c. Ahora c siente envidia de a, b siente envidia de a y c, y a no siente envidia de nadie. Como ya no hay ciclo de envidia ni más objetos que repartir, el procedimiento termina y el resultado final es que a recibe X, b recibe Z y c recibe Y.
3. Para empezar, le damos el objeto Y a a. Después, b y c son agentes que no sienten envidia. Ahora le damos el objeto X a b. Después, c es un agente que no siente envidia. Ahora le damos el último objeto, Z, a c. Ahora c siente envidia de a y b, a siente envidia de b y b no siente envidia de nadie. Como ya no hay ciclo de envidia ni más objetos que repartir, el procedimiento termina y el resultado final es que a recibe Y, b recibe X y c recibe Z.
4. Para empezar, le damos el objeto Y a a. Después, tanto b como c son agentes que no sienten envidia. Ahora le damos el objeto Z a b. Después, c es un agente que no siente envidia. Ahora le damos el último objeto X a c. Ahora a siente envidia de c, b siente envidia de a y c, y c no siente envidia de nadie. Como ya no hay ciclo de envidia ni más objetos que repartir, el procedimiento termina y el resultado final es que a recibe Y, b recibe Z y c recibe X.
5. Para empezar, le damos el objeto Z a a. Después, b y c son agentes que no sienten envidia. Ahora le damos el objeto X a b. Después, c es un agente que no siente envidia. Ahora le damos el último objeto Y a c. Ahora c siente envidia de b, a siente envidia de b y c, y b no siente envidia de nadie. Como ya no hay ciclo de envidia ni más objetos que repartir, el procedimiento termina y el resultado final es que a recibe Z, b recibe X y c recibe Y.
6. Para empezar, le damos el objeto Z a a. Después, tanto b como c son agentes que no sienten envidia. Ahora le damos el objeto Y a b. Después, c es un agente que no siente envidia. Ahora le damos el último objeto X a c. Ahora b siente envidia de c, a siente envidia de b y c, y c no siente envidia de nadie. Como ya no hay ciclo de envidia ni más objetos que repartir, el procedimiento termina y el resultado final es que a recibe Z, b recibe Y y c recibe X.

2) Con 3 personas y 3 objetos, cualquier asignación posible dará como resultado lo mismo. Esto ocurre cuando cada una de las tres personas tiene preferencias completamente diferentes, ya que cada una tiene algo distinto que prefiere; de ​​todas formas, obtendrán lo que desean.

Existen seis formas diferentes de asignar los objetos:

Al principio, como nadie tiene nada, todos son agentes no envidiados, y esto se aplica a todos los casos. En caso de empate, se resuelve el desempate entre agentes no envidiados en orden lexicográfico.

1. Para empezar, le damos el objeto X a a. Después, b y c son agentes que no sienten envidia. Ahora le damos el objeto Y a b. Después, c es un agente que no siente envidia. Así que ahora le damos el último objeto, Z, a c. Ahora, a, b y c no sienten envidia de nadie y, como ya no hay ciclo de envidia ni más objetos que repartir, el procedimiento termina y el resultado final es que a recibe X, b recibe Y y c recibe Z.
2. Para empezar, le damos el objeto X a a. Después, b y c son agentes que no sienten envidia. Ahora le damos el objeto Z a b. Después, c es un agente que no siente envidia. Así que ahora le damos el último objeto Y a c. Ahora c siente envidia de b, b siente envidia de c y a no siente envidia de nadie. Como hay un ciclo de envidia entre b y c, intercambiarán objetos y ahora b recibe Y y c recibe Z. Y ahora, como no hay ciclo de envidia ni más objetos que repartir, el procedimiento termina y el resultado final es que a recibe X, b recibe Y y c recibe Z.
3. Para empezar, le damos el objeto Y a a. Después, b y c son agentes que no sienten envidia. Ahora le damos el objeto X a b. Después, c es un agente que no siente envidia. Ahora le damos el último objeto, Z, a c. Ahora b siente envidia de a, a siente envidia de b y c no siente envidia de nadie. Como hay un ciclo de envidia entre b y c, intercambiarán objetos y ahora a recibe X y b recibe Y. Y ahora, como no hay ciclo de envidia ni más objetos que repartir, el procedimiento termina y el resultado final es que a recibe X, b recibe Y y c recibe Z.
4. Para empezar, le damos el objeto Y a a. Después, b y c son agentes que no son envidiados. Ahora le damos el objeto Z a b. Después, c es un agente que no es envidiado. Ahora le damos el último objeto X a c. Ahora b siente envidia de a, a siente envidia de c y c siente envidia de b. Como hay un ciclo de envidia entre a, b y c, rotarán los objetos en sentido contrario a la dirección de la envidia y ahora a obtiene X, b obtiene Y y c obtiene Z. Y ahora, como no hay ciclo de envidia y no hay más objetos que repartir, el procedimiento termina y el resultado final es que a obtiene X, b obtiene Y y c obtiene Z.
5. Para empezar, le damos el objeto Z a a. Después, b y c son agentes que no son envidiados. Así que ahora le damos el objeto X a b. Después, c es un agente que no es envidiado. Así que ahora le damos el último objeto Y a c. Ahora b siente envidia de a y c, a siente envidia de b y c, y c siente envidia de b y a. Como hay un ciclo de envidia entre a, b y c, rotarán los objetos en sentido contrario a la dirección de la envidia y ahora a obtiene X, b obtiene Y y c obtiene Z. Y ahora, como no hay ciclo de envidia y no hay más objetos que repartir, el procedimiento termina y el resultado final es que a obtiene X, b obtiene Y y c obtiene Z.
6. Para empezar, le damos el objeto Z a a. Después, b y c son agentes que no sienten envidia. Ahora le damos el objeto Y a b. Después, c es un agente que no siente envidia. Ahora le damos el último objeto X a c. Ahora c siente envidia de a, a siente envidia de c y b no siente envidia de nadie. Como hay un ciclo de envidia entre a y c, intercambiarán objetos y ahora a recibe X y c recibe Z. Y ahora, como no hay ciclo de envidia ni más objetos que repartir, el procedimiento termina y el resultado final es que a recibe X, b recibe Y y c recibe Z.

3) Con 3 personas y 3 objetos, cualquier otra situación distinta a los dos primeros ejemplos dará entre 1 y 6 resultados. Por lo tanto, para que esto ocurra, basta con que al menos dos personas tengan la misma preferencia por un objeto o, como máximo, que dos personas tengan preferencias diferentes por el mismo objeto.

Existen seis formas diferentes de asignar los objetos:

Al principio, como nadie tiene nada, todos son agentes no envidiados, y esto se aplica a todos los casos. En caso de empate, se resuelve el desempate entre agentes no envidiados en orden lexicográfico.

1. Para empezar, le damos el objeto X a a. Después, tanto b como c son agentes que no sienten envidia. Ahora le damos el objeto Y a b. Después, c es un agente que no siente envidia. Así que ahora le damos el último objeto Z a c. Ahora a no siente envidia de nadie, b siente envidia de a y c, y c no siente envidia de nadie. Como ya no hay ciclo de envidia ni más objetos que repartir, el procedimiento termina y el resultado final es que a recibe X, b recibe Y y c recibe Z.
2. Para empezar, le damos el objeto X a a. Después, tanto b como c son agentes que no sienten envidia. Ahora le damos el objeto Z a b. Después, c es un agente que no siente envidia. Ahora le damos el último objeto Y a c. Ahora a no siente envidia de nadie, b siente envidia de a y c siente envidia de b. Como ya no hay ciclo de envidia ni más objetos que repartir, el procedimiento termina y el resultado final es que a recibe X, b recibe Z y c recibe Y.
3. Para empezar, le damos el objeto Y a a. Después, b y c son agentes que no sienten envidia. Ahora le damos el objeto X a b. Después, c es un agente que no siente envidia. Ahora le damos el último objeto, Z, a c. Ahora b y c no sienten envidia de nadie, y a siente envidia de b. Como ya no hay ciclo de envidia ni más objetos que repartir, el procedimiento termina y el resultado final es que a recibe Y, b recibe X y c recibe Z.
4. Comencemos dándole el objeto Y a a. Después de eso, tanto b como c son agentes no envidiados. Entonces ahora demos el objeto Z a b. Después de eso, c es un agente no envidiado. Entonces ahora demos el último objeto X a c. Ahora a está celoso de c, b está celoso de c y c está celoso de a y b, por lo que hay dos ciclos de envidia, uno entre a y c y otro entre b y c. Debido a que el desempate es por orden lexicográfico, el procedimiento hace primero el ciclo de envidia de a y c, luego a y c intercambiarán, luego a no está celoso de nadie, b está celoso de a y c está celoso de b y ahora como no hay ciclo de envidia y no hay más objetos para entregar entonces el procedimiento termina y el resultado final es que a obtiene X, b obtiene Z y c obtiene Y.
5. Para empezar, le damos el objeto Z a a. Después, b y c son agentes que no son envidiados. Así que ahora le damos el objeto X a b. Después, c es un agente que no es envidiado. Así que ahora le damos el último objeto Y a c. Ahora a siente envidia de b y c, b no siente envidia de nadie y c siente envidia de a. Como hay un ciclo de envidia entre a y c, intercambiarán objetos y ahora a recibe Y y c recibe Z. Ahora, como no hay ciclo de envidia y no hay más objetos que repartir, el procedimiento termina y el resultado final es que a recibe Y, b recibe X y c recibe Z.
6. Comencemos dándole el objeto Z a a. Después de eso, tanto b como c son agentes no envidiados. Entonces, ahora demos el objeto Y a b. Después de eso, c es un agente no envidiado. Entonces, ahora demos el último objeto X a c. Ahora b está celoso de a y c, a está celoso de b y c, y c está celoso de b y a. Dado que hay un ciclo de envidia entre a, b y c, rotarán los objetos en contra de la dirección de los celos. Sin embargo, debido a que hay 2 ciclos de envidia entre a, b y c, podría haber dos opciones. Debido a que el desempate es por orden lexicográfico, a obtiene X de c, b obtiene Z de a y c obtiene Y de b, por lo que el resultado sería a obtiene X, b obtiene Z y c obtiene Y. Y ahora, como no hay ciclo de envidia y no hay más objetos para entregar, entonces el procedimiento termina y el resultado final es a obtiene X, b obtiene Z y c obtiene Y.

El algoritmo de grafo de envidia garantiza EF1 cuando los elementos son bienes (el valor marginal de cada elemento es positivo para todos los agentes). Sin embargo, cuando hay tanto bienes como tareas, no garantiza EF1. Una adaptación llamada grafo de envidia generalizado garantiza EF1 incluso con una mezcla de bienes y tareas. Funciona siempre que las valoraciones sean doblemente monótonas , es decir: cada agente puede dividir los elementos en dos subconjuntos: un subconjunto contiene bienes (elementos cuya utilidad marginal es siempre positiva) y el otro contiene tareas (elementos cuya utilidad marginal es siempre negativa). ^{[ 3 ]}

Cuando los agentes tienen restricciones de cardinalidad (es decir, para cada categoría de elementos, existe un límite superior en la cantidad de elementos que cada agente puede obtener de esta categoría), el algoritmo de grafo de envidia podría fallar. Sin embargo, al combinarlo con el protocolo round-robin, se obtiene un algoritmo que encuentra asignaciones que son EF1 y satisfacen las restricciones de cardinalidad. ^{[ 4 ]}

Cuando los agentes tienen valoraciones de asignación (también conocidas como valoraciones OXS), existe una extensión del algoritmo del grafo de envidia llamada "Algoritmo H", en la que la siguiente asignación a un agente no envidiado se selecciona de manera que se maximice la utilidad agente-elemento. No existe una prueba formal de las propiedades de este algoritmo, pero funciona bien con datos reales. ^{[ 5 ]}

• Asignación de artículos sin envidia
• La partición numérica voraz puede considerarse un caso especial del algoritmo de grafo de envidia para el caso en que todos los agentes tienen valoraciones idénticas.
• Procedimiento de reducción de la demanda y procedimiento de rebaja de precio : dos procedimientos adicionales basados ​​en la clasificación ordinal de los paquetes.