Procedimiento del gráfico de envidia

Procedimiento para la asignación justa de artículos

El procedimiento del grafo de envidia (también llamado procedimiento de ciclos de envidia ) es un procedimiento de asignación justa de elementos . Puede ser utilizado por varias personas que desean dividir entre ellas varios elementos discretos, como reliquias, dulces o asientos en una clase.

Idealmente, nos gustaría que la asignación fuera libre de envidia (FE), es decir, que se diera a cada agente un conjunto de elementos que prefiera sobre los conjuntos de todos los demás agentes. Sin embargo, los elementos son discretos y no se pueden eliminar, por lo que una asignación libre de envidia podría ser imposible (por ejemplo, considere un solo elemento y dos agentes). El procedimiento del grafo de envidia apunta a lograr la opción "siguiente mejor" - libre de envidia hasta como máximo un solo bien (FE1): encuentra una asignación en la que la envidia de cada persona hacia todas las demás personas está limitada por la utilidad marginal máxima que deriva de un solo elemento. En otras palabras, para cada dos personas i y j , existe un elemento tal que, si se elimina ese elemento, 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}

Supuestos

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

Los agentes no tienen que informar realmente su utilidad cardinal: basta con que sepan cómo clasificar los paquetes.

El procedimiento

1. Ordene los artículos arbitrariamente.
2. Si hay elementos sin asignar:
   • Asegúrese de que haya un agente no envidiado , un agente al que ningún otro agente envidie.
   • Entregue el siguiente artículo al agente poco envidiado.

En el paso 2, si no hay ningún agente no envidiado, significa que hay 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 que se eliminan todos los ciclos, el grafo de envidia debe tener un nodo sin aristas entrantes; este nodo representa un agente no envidiado.

La asignación resultante no es necesariamente EF, pero está libre de envidia, excepto por un elemento. Esto es cierto no solo en la asignación final, sino también en cada asignación intermedia: dado que siempre se le da 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.

Análisis en tiempo de ejecución

Supongamos que hay m elementos. Cada asignación de un elemento agrega al gráfico de envidia como máximo n -1 aristas. Por lo tanto, como máximo se agregan aristas en total. 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 . Encontrar un ciclo se puede hacer a tiempo usando, por ejemplo, una búsqueda en profundidad . En total, el tiempo de ejecución es . ${\displaystyle (n-1)m}$ ${\displaystyle (n-1)m/2}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{3}m)}$

Ejemplos

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 posible asignación dará un resultado diferente. Este caso se da cuando cada una de las tres personas tiene las mismas preferencias. Existen seis formas distintas de asignar los objetos:

Al principio, como nadie tiene nada, todos son agentes no envidiados y esto es así en todos los casos. En caso de empate, desempatamos los agentes no envidiados en orden lexicográfico.

1. Empecemos por darle el objeto X a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora le damos el objeto Y a b. Después de eso, c es un agente no envidiado. Así que ahora le damos el último objeto Z a c. Ahora c está celoso de b y a, b está celoso de a y a no está celoso de nadie 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 Y y c obtiene Z.
2. Empecemos por darle el objeto X a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora le damos el objeto Z a b. Después de eso, c es un agente no envidiado. Así que ahora le damos el último objeto Y a c. Ahora c está celoso de a, b está celoso de a y c y a no está celoso de nadie 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.
3. Empecemos por darle el objeto Y a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora le damos el objeto X a b. Después de eso, c es un agente no envidiado. Así que ahora le damos el último objeto Z a c. Ahora c está celoso de a y b, a está celoso de b y b no está celoso de nadie 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 Y, b obtiene X y c obtiene Z.
4. Empecemos por darle el objeto Y a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora le daremos el objeto Z a b. Después de eso, c es un agente no envidiado. Así que ahora le daremos el último objeto X a c. Ahora a está celoso de c, b está celoso de a y c y c no está celoso de nadie 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 Y, b obtiene Z y c obtiene X.
5. Empecemos por darle el objeto Z a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora le damos el objeto X a b. Después de eso, c es un agente no envidiado. Así que ahora le damos el último objeto Y a c. Ahora c está celoso de b, a está celoso de b y c y b no está celoso de nadie 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 Z, b obtiene X y c obtiene Y.
6. Empecemos por darle el objeto Z a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora le damos el objeto Y a b. Después de eso, c es un agente no envidiado. Así que ahora le damos el último objeto X a c. Ahora b está celoso de c, a está celoso de b y c y c no está celoso de nadie 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 Z, b obtiene Y y c obtiene X.

2) Con 3 personas y 3 objetos, cada posible asignación dará el mismo resultado. Este caso ocurre cuando cada una de las tres personas tiene preferencias completamente diferentes, porque cada persona tiene algo más que prefiere, sin importar lo que obtenga, obtendrá lo que quiere.

Hay seis formas diferentes de asignar los objetos:

Al principio, como nadie tiene nada, todos son agentes no envidiados y esto es así en todos los casos. En caso de empate, desempatamos los agentes no envidiados en orden lexicográfico.

1. Comencemos por darle el objeto X a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora le daremos el objeto Y a b. Después de eso, c es un agente no envidiado. Así que ahora le daremos el último objeto Z a c. Ahora a, b y c no tienen celos de nadie y ahora, como no hay ciclo de envidia y no hay más objetos para entregar, el procedimiento termina y el resultado final es que a obtiene X, b obtiene Y y c obtiene Z.
2. Empecemos por darle el objeto X a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora le damos el objeto Z a b. Después de eso, c es un agente no envidiado. Así que ahora le damos el último objeto Y a c. Ahora c está celoso de b, b está celoso de c y a no está celoso de nadie. Como hay un ciclo de envidia entre b y c, intercambiarán objetos y ahora b obtiene Y y c obtiene Z. 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 Y y c obtiene Z.
3. Empecemos por darle el objeto Y a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora le damos el objeto X a b. Después de eso, c es un agente no envidiado. Así que ahora le damos el último objeto Z a c. Ahora b está celoso de a, a está celoso de b y c no está celoso de nadie. Como hay un ciclo de envidia entre b y c, intercambiarán objetos y ahora a obtiene X y b 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 que a obtiene X, b obtiene Y y c obtiene Z.
4. Empecemos por darle el objeto Y a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora vamos a darle el objeto Z a b. Después de eso, c es un agente no envidiado. Así que ahora vamos a darle el último objeto X a c. Ahora b está celoso de a, a está celoso de c y c está celoso de b. Como hay un ciclo de envidia entre a, b y c, rotarán los objetos en contra de la dirección de los celos 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 para entregar, entonces el procedimiento termina y el resultado final es que a obtiene X, b obtiene Y y c obtiene Z.
5. Empecemos por darle el objeto Z a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora vamos a darle el objeto X a b. Después de eso, c es un agente no envidiado. Así que ahora vamos a darle el último objeto Y 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. Como hay un ciclo de envidia entre a, b y c, rotarán los objetos en contra de la dirección de los celos y ahora a obtiene X y b obtiene Y y c obtiene Z. 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 Y y c obtiene Z.
6. Empecemos por darle el objeto Z a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora le damos el objeto Y a b. Después de eso, c es un agente no envidiado. Así que ahora le damos el último objeto X a c. Ahora c está celoso de a, a está celoso de c y b no está celoso de nadie. Como hay un ciclo de envidia entre a y c, intercambiarán objetos y ahora a obtiene X y c obtiene Z. 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 Y y c obtiene Z.

3) Con 3 personas y 3 objetos, cualquier otra situación distinta a la del primer y segundo ejemplo dará entre 1 y 6 resultados. Por lo tanto, para que esto suceda, solo se necesita 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.

Hay seis formas diferentes de asignar los objetos:

Al principio, como nadie tiene nada, todos son agentes no envidiados y esto es así en todos los casos. En caso de empate, desempatamos los agentes no envidiados en orden lexicográfico.

1. Empecemos por darle el objeto X a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora vamos a darle el objeto Y a b. Después de eso, c es un agente no envidiado. Así que ahora vamos a darle el último objeto Z a c. Ahora a no está celoso de nadie, b está celoso de a y c y c no está celoso de nadie, 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 Y y c obtiene Z.
2. Empecemos por darle el objeto X a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora le damos el objeto Z a b. Después de eso, c es un agente no envidiado. Así que ahora le damos el último objeto Y a c. Ahora a no está celoso de nadie, b está celoso de a y c está celoso de b. 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.
3. Empecemos por darle el objeto Y a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora le damos el objeto X a b. Después de eso, c es un agente no envidiado. Así que ahora le damos el último objeto Z a c. Ahora b y c no están celosos de nadie y a está celoso de b. Ahora, como no hay ciclo de envidia y no hay más objetos para entregar, el procedimiento termina y el resultado final es que a obtiene Y, b obtiene X y c obtiene Z.
4. Empecemos por darle el objeto Y a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora vamos a darle el objeto Z a b. Después de eso, c es un agente no envidiado. Así que ahora vamos a darle 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, así que hay dos ciclos de envidia, uno entre a y c y otro entre b y c. Como el desempate es por orden lexicográfico, el procedimiento hace primero el ciclo de envidia de a y c, luego a y c cambiará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. Empecemos por darle el objeto Z a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora vamos a darle el objeto X a b. Después de eso, c es un agente no envidiado. Así que ahora vamos a darle el último objeto Y a c. Ahora a está celoso de b y c, b no está celoso de nadie y c está celoso de a. Como hay un ciclo de envidia entre a y c, intercambiarán objetos y ahora a obtiene Y y c obtiene Z, 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 Y, b obtiene X y c obtiene Z.
6. Empecemos por darle el objeto Z a a. Después de eso, tanto b como c son agentes no envidiados. Así que ahora vamos a darle el objeto Y a b. Después de eso, c es un agente no envidiado. Así que ahora vamos a darle 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. Como 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, como hay 2 ciclos de envidia entre a, b y c, podría haber dos opciones. Como 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 que 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, el procedimiento termina y el resultado final es que a obtiene X, b obtiene Z y c obtiene Y.

Extensiones

El algoritmo del grafo de envidia garantiza EF1 cuando los ítems son bienes (- el valor marginal de cada ítem es positivo para todos los agentes). Sin embargo, cuando hay bienes y 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 ítems en dos subconjuntos: un subconjunto contiene bienes (- ítems cuya utilidad marginal es siempre positiva) y el otro contiene tareas (- ítems 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 del gráfico de envidia puede 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 llamado "Algoritmo H", en el que se selecciona la siguiente asignación a un agente no envidiado de modo que se maximice la utilidad del agente-artículo. No hay una prueba formal de las propiedades de este algoritmo, pero funciona bien con datos realistas. ^[5]

Véase también

• Asignación de artículos sin envidia
• Partición de números codiciosos : puede verse como un caso especial del algoritmo del gráfico de envidia en el caso en que todos los agentes tienen valoraciones idénticas.
• Procedimiento de demanda decreciente y procedimiento de rebaja : dos procedimientos adicionales basados ​​en la clasificación ordinal de los paquetes.

Referencias

1. Lipton, RJ; Markakis, E.; Mossel, E.; Saberi, A. (2004). "Sobre asignaciones aproximadamente justas de bienes indivisibles". Actas de la 5.ª conferencia de la ACM sobre comercio electrónico - EC '04 . p. 125. CiteSeerX  10.1.1.400.1762 . doi :10.1145/988772.988792. ISBN 1-58113-771-0.
2. Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Manual de elección social computacional. Cambridge University Press. ISBN 9781107060432.(versión gratuita en línea)
3. Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, Toby Walsh (2019). "Asignación justa de bienes y tareas indivisibles" (PDF) . Conferencia IJCAI 2019 .{{cite web}}: CS1 maint: varios nombres: lista de autores ( enlace )
4. Biswas, Arpita; Barman, Siddharth (13 de julio de 2018). "División justa bajo restricciones de cardinalidad". Actas de la 27.ª Conferencia conjunta internacional sobre inteligencia artificial . IJCAI'18. Estocolmo, Suecia: AAAI Press: 91–97. arXiv : 1804.09521 . ISBN 978-0-9992411-2-7.
5. Benabbou, Nawal; Chakraborty, Mithun; Elkind, Edith; Zick, Yair (10 de agosto de 2019). "Equidad hacia grupos de agentes en la asignación de elementos indivisibles". {{cite journal}}: Requiere citar revista |journal=( ayuda )