Procedimiento del ciclo de la envidia

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de marzo de 2022; las comprobaciones requieren 11 ediciones .

El procedimiento de los ciclos de la envidia es un procedimiento para la justa distribución de los objetos .

Este experimento se llevó a cabo en más de 75 países alrededor del mundo. Entre ellos: Rusia, Estados Unidos, Canadá, Francia, China, Japón, Kazajistán, Corea del Norte e Italia.

Este proceso puede involucrar a varias personas que desean compartir algunos elementos en un espacio discreto , como reliquias familiares, obsequios o asientos en el salón de clases.

Es deseable asegurarse de que la distribución de los objetos se produzca con la ausencia de envidias , es decir, que cada uno encuentre lo que necesita. Debido a la indivisibilidad de los objetos, tal distribución es generalmente inalcanzable (por ejemplo, la distribución de un objeto entre dos agentes), por lo que el procedimiento de ciclos de envidia busca lograr el objetivo de "segundo nivel": la ausencia de envidia. a un solo objeto . El resultado del método es una distribución en la que la envidia de una persona a otra está limitada por la utilidad marginal de un solo artículo. En otras palabras, para dos personas cualesquiera hay tal objeto que, si se quita, nadie envidiará.

El procedimiento fue introducido por Lipton, Markakis, Mossel y Sabury [1] y también se describe en Brandt et al [2] .

Suposiciones

El procedimiento de los ciclos de la envidia supone que cada persona tiene una función de utilidad cuantitativa sobre conjuntos de elementos. Esta función de utilidad no necesita ser aditiva. Es decir, no se supone que los elementos sean independientes .

Los agentes no están obligados a revelar su utilidad cuantitativa real; basta con que sepan cómo ordenar paquetes por utilidad.

Procedimiento

Organice los elementos en orden aleatorio.
Mientras haya artículos sin asignar:
- Asegurémonos de que haya un agente no envidiable , un agente que no sea envidiado por ningún otro agente;
- Le damos el siguiente artículo al agente poco envidiable.

Si no hay agentes no envidiables en el paso 2, esto significa que hay un ciclo dirigido en el gráfico de envidia , un gráfico dirigido , donde cada agente señala a todos los agentes que envidia. Los ciclos se pueden eliminar ciclando conjuntos de elementos. Cuando se eliminan todos los ciclos, el gráfico de envidia debe tener un nodo , que no recibe ningún arco , y representa un agente poco envidiable.

La distribución resultante no estará necesariamente libre de envidia, pero es una distribución libre de envidia excepto por un artículo . Esto es cierto no solo para la distribución final, sino también para cada distribución intermedia: dado que el artículo siempre se entrega a un agente poco envidiable, la envidia de todos los demás agentes después de que se transfiere el artículo solo puede reflejarse en un solo artículo.

Análisis del tiempo de ejecución

Supongamos que hay m elementos. Cada transferencia de un elemento agrega como máximo n -1 arcos al gráfico de envidia. Por lo tanto, no se agregarán más arcos en total. Cada eliminación de bucle elimina al menos dos arcos. Por lo tanto, debemos realizar el paso de eliminación del bucle no más de una vez. La búsqueda cíclica se puede realizar en el tiempo utilizando, por ejemplo, la búsqueda en profundidad . El tiempo total de ejecución será . ${\ estilo de visualización (n-1) m}$ ${\ estilo de visualización (n-1) m/2}$ $O(n^{2})$ $O(n^{3}m)$

Ejemplos

En estos ejemplos, las preferencias vienen dadas por los valores 1-3, donde un número más alto significa una preferencia más alta. Aquí A, B y C son personas y X, Y y Z son objetos.

1) Con 3 personas y 3 objetos, cada distribución posible produce resultados diferentes. Esto sucede cuando cada uno de los tres participantes tiene las mismas preferencias.

6 resultados diferentes

	X	Y	Z
A	3	2	una
B	3	2	una
C	3	2	una

Hay seis formas diferentes de distribuir objetos:

Inicialmente, dado que nadie posee ningún artículo, todos los agentes son poco envidiables, y esto es cierto en todos los casos. Si hay un enlace, lo dividimos entre agentes no envidiables en orden lexicográfico.

Comencemos con la transferencia del artículo X al agente A. Después de eso, nadie envidia a los agentes B y C. Así que ahora le damos el artículo Y al agente B. Después de eso, está el agente C, del que nadie está celoso, así que le damos el artículo Z al agente C. Ahora el agente C está celoso tanto de B como de A, el agente B está celoso, y el agente A no está celoso de nadie. Por lo tanto, no hay ciclos de envidia ni objetos para distribuir, por lo que el procedimiento termina y el resultado es que el agente A tiene el elemento X, el agente B tiene el elemento Y y el agente C tiene el elemento Z.
Comencemos con la transferencia del artículo X al agente A. Después de eso, nadie envidia a los agentes B y C. Así que ahora le damos el objeto Z al agente B. Después de eso, queda el agente C, de quien nadie está celoso, le damos el último objeto Y al agente C. Ahora C está celoso de A, B está celoso de A y C, y el agente A no está celoso de nadie, y ahora, como no hay ciclo de envidia y no hay objetos para distribuir, el procedimiento termina y como resultado, A obtiene X, B obtiene Z y C obtiene Y.
Comencemos con la transferencia del artículo Y al agente A. Después de eso, nadie envidia a los agentes B y C. Así que ahora le damos el objeto X al agente B. Después de eso, queda el agente C, de quien nadie está celoso, le damos el último objeto Z al agente 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 procesar, el procedimiento termina y como resultado, A obtiene Y, B obtiene X y C obtiene Z.
Comencemos con la transferencia del artículo Y al agente A. Después de eso, nadie envidia a los agentes B y C. Así que ahora le damos el artículo Z al agente B. Después de eso, queda el agente C, del cual nadie está celoso, le damos el último objeto X al agente C. Ahora A está celoso de C, B está celoso de A y C, y C ya no está celoso de nadie, ya que no hay ciclo de envidia y no hay más objetos para procesar, el procedimiento termina y como resultado, A obtiene Y, B obtiene Z y C obtiene X.
Comencemos con la transferencia del artículo Z al agente A. Después de eso, nadie envidia a los agentes B y C. Así que ahora le damos el objeto X al agente B. Después de eso, queda el agente C, de quien nadie está celoso, le damos el último objeto Y al agente C. Ahora C está celoso de B, A está celoso de B y C, y B no tiene celos de nadie y ahora, como no hay ciclo de envidia y no hay más objetos para procesar, el procedimiento termina y como resultado, A obtiene Z, B obtiene X y C obtiene Y.
Comencemos con la transferencia del artículo Z al agente A. Después de eso, nadie envidia a los agentes B y C. Así que ahora le damos el artículo Y al agente B. Después de eso, queda el agente C, de quien nadie está celoso, le damos el último objeto X al agente C. Ahora B está celoso de C, A está celoso de B y C, y C no está celoso de nadie ahora, ya que no hay ciclo de envidia y no hay más objetos para procesar, el procedimiento termina y como resultado, A obtiene Z, B obtiene Y y C obtiene X.

2) Con 3 personas y 3 objetos, todas las distribuciones posibles dan el mismo resultado. Esto sucede cuando cada una de las tres personas tiene preferencias completamente diferentes a las de los otros agentes, en cuyo caso cada persona tiene una preferencia diferente, sin importar lo que obtenga.

Mismo resultado

	X	Y	Z
A	3	2	una
B	una	3	2
C	2	una	3

Hay seis formas diferentes de distribuir objetos:

Al principio, como nadie tiene nada, entonces todos los agentes son poco envidiables y esto es cierto en todos los casos. Si hay un enlace, lo dividimos entre agentes no envidiables en orden lexicográfico.

Comencemos con la transferencia del artículo X al agente A. Después de eso, nadie envidia a los agentes B y C. Entonces ahora le damos el artículo Y al agente B. Después de eso, queda el agente C, de quien nadie está celoso, le damos el último objeto Z al agente C. Ahora A, B y C no están celosos de nadie y ahora, ya que no hay ciclo de envidia A y no hay más objetos para procesar, el procedimiento termina y, como resultado, A obtiene X, B obtiene Y y C obtiene Z.
Comencemos con la transferencia del artículo X al agente A. Después de eso, nadie envidia a los agentes B y C. Así que ahora le damos el objeto Z al agente B. Después de eso, queda el agente C, de quien nadie está celoso, le damos el último objeto Y al agente C. Ahora C está celoso de B, B está celoso de C y A está celoso. no celoso de nadie. Como hay un ciclo de envidia entre B y C, intercambian objetos, y ahora B obtiene Y, y C obtiene Z. Después de eso, como no hay ciclo de envidia y no hay más objetos para procesar, el procedimiento termina y como resultado resultado, A obtiene X, B obtiene Y y C obtiene Z.
Comencemos con la transferencia del artículo Y al agente A. Después de eso, nadie envidia a los agentes B y C. Así que ahora le damos el objeto X al agente B. Después de eso, queda el agente C, de quien nadie está celoso, le damos el último objeto Z al agente C. Ahora B está celoso de A, A está celoso de B y C no tiene celos de nadie. Como hay un ciclo de envidia entre los agentes B y C, intercambian artículos y ahora el agente A recibe X y B recibe Y. Después de eso, como no hay ciclo de envidia y no hay más objetos para procesar, el procedimiento termina y como resultado, A recibe X, B obtiene Y y C obtiene Z.
Comencemos con la transferencia del artículo Y al agente A. Después de eso, nadie envidia a los agentes B y C. Así que ahora le damos el artículo Z al agente B. Después de eso, queda el agente C, de quien nadie está celoso, le damos el último objeto X al agente C. Ahora B está celoso de A, A está celoso de C y C está celoso. celoso de B. Ya que hay un ciclo de envidia entre A, B y C, ellos ciclan los objetos en la dirección opuesta a la envidia, así que ahora A obtiene X, B obtiene Y y C obtiene Z. Después de eso, dado que no hay ciclo de envidia y no hay más objetos para procesar, el procedimiento finaliza y, como resultado, A obtiene X, B obtiene Y y C obtiene Z.
Comencemos con la transferencia del artículo Z al agente A. Después de eso, nadie envidia a los agentes B y C. Entonces ahora le damos el objeto X al agente B. Después de eso, queda el agente C, de quien nadie está celoso, le damos el último objeto Y al agente 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, pasamos objetos en la dirección contraria a la envidia, así que 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 procesar, el procedimiento finaliza y, como resultado, A obtiene X, B obtiene Y y C obtiene Z.
Comencemos con la transferencia del artículo Z al agente A. Después de eso, nadie envidia a los agentes B y C. Así que ahora le damos el artículo Y al agente B. Después de eso, queda el agente C, de quien nadie está celoso, le damos el último objeto X al agente C. Ahora C está celoso de A, A está celoso de C y B está celoso. de nadie Como hay un ciclo de envidia entre A y C, intercambian objetos y ahora A obtiene X y C obtiene Z. Después de eso, como no hay ciclo de envidia y no hay más objetos para procesar, el procedimiento finaliza y como resultado, A obtiene X, B obtiene Y y C obtiene Z.

3) Con 3 personas y 3 objetos, cualquier otra situación que no sea el primer y segundo ejemplo dará un número de resultados entre 1 y 6. Para que esto suceda, debe haber al menos dos personas que tengan la misma preferencia por un objeto y no más de dos personas con diferentes preferencias por el mismo objeto.

3 resultados diferentes

	X	Y	Z
A	3	2	una
B	3	una	2
C	una	2	3

Hay seis formas diferentes de asignar objetos: Al principio, dado que nadie tiene nada, todos los agentes son poco envidiables y esto es cierto en todos los casos. Si hay un enlace, lo dividimos entre agentes no envidiables en orden lexicográfico.

Comencemos con la transferencia del artículo X al agente A. Después de eso, nadie envidia a los agentes B y C. Así que ahora le damos el objeto Y al agente B. Después de eso, queda el agente C, de quien nadie está celoso, le damos el último objeto Z al agente C. Ahora A no está celoso de nadie, 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 objetos para procesar, el procedimiento termina y como resultado A obtiene X, B obtiene Y y C obtiene Z.
Comencemos con la transferencia del artículo X al agente A. Después de eso, nadie envidia a los agentes B y C. Así que ahora le damos el objeto Z al agente B. Después de eso, queda el agente C, de quien nadie está celoso, le damos el último objeto Y al agente C. Ahora A no está celoso de nadie, B está celoso de A, y C está celoso de B, y ahora, dado que no hay ciclo de envidia y no hay más elementos para procesar, el procedimiento finaliza y, como resultado, A obtiene X, B obtiene Z y C obtiene Y.
Comencemos con la transferencia del artículo Y al agente A. Después de eso, nadie envidia a los agentes B y C. Así que ahora le damos el elemento X al agente B. Después de eso, queda el agente C, de quien nadie está celoso, le damos el último objeto Z al agente C. Ahora B y C no están celosos de nadie, y A está celoso de B , y ahora, dado que no hay ciclos de envidia ni más elementos para procesar, el procedimiento finaliza y, como resultado, A obtiene Y, B obtiene X y C obtiene Z.
Comencemos con la transferencia del artículo Y al agente A. Después de eso, nadie envidia a los agentes B y C. Así que ahora le damos el artículo Z al agente B. Después de eso, queda el agente C, del cual nadie está celoso, le damos el último objeto X al agente C. Ahora A está celoso de C, B está celoso de C y C está celoso. celos de A y B, por lo que hay dos ciclos de envidia, uno entre A y C y otro entre B y C. Hay un vínculo que rompemos en orden lexicográfico. El procedimiento toma primero el ciclo de envidia entre A y C e intercambia los objetos de estos agentes, por lo que ahora A no está celoso de nadie, B está celoso de A y C está celoso de B, entonces ya que no hay ciclo de envidia y no hay más objetos para procesar, el procedimiento finaliza y, como resultado, A obtiene X, B obtiene Z y C obtiene Y.
Comencemos con la transferencia del artículo Z al agente A. Después de eso, nadie envidia a los agentes B y C. Así que ahora le damos el elemento X al agente B. Después de eso, queda el agente C, de quien nadie está celoso, le damos el último objeto Y al agente 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, intercambian objetos y ahora A obtiene Y y C obtiene Z, y ahora como no hay ciclo de envidia y no hay más elementos para procesar, el procedimiento termina y como resultado A obtiene Y, B obtiene X y C obtiene Z.
Comencemos con la transferencia del artículo Z al agente A. Después de eso, nadie envidia a los agentes B y C. Así que ahora le damos el artículo Y al agente B. Después de eso, queda el agente C, de quien nadie está celoso, le damos el último objeto X al agente 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, intercambian objetos en la dirección opuesta de la envidia. Sin embargo, dado que hay 2 ciclos de envidia entre A, B y C, hay dos posibilidades. Resolvemos la ambigüedad en orden lexicográfico para que A obtenga X de C, B obtenga Z de A y C obtenga Y de B, por lo que el resultado es que A posee X, B posee Z y C posee Y. Ahora, dado que hay No hay ciclo de envidia y no hay más objetos para distribuir, el procedimiento termina y como resultado A obtiene X, B obtiene Z y C obtiene Y.

Véase también

Envidiosa distribución de objetos.

Notas

↑ Lipton, Markakis, Mossel, Saberi, 2004 , pág. 125.
↑ Brandt, Conitzer et al., 2016 , pág. 300–301.

Literatura

Lipton RJ, Markakis E., Mossel E., Saberi A. Sobre asignaciones aproximadamente justas de bienes indivisibles // Actas de la 5.ª conferencia ACM sobre comercio electrónico - EC '04. - 2004. - ISBN 1-58113-771-0 . doi : 10.1145 / 988772.988792 .
Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. Manual de Elección Social Computacional . - Cambridge University Press, 2016. - ISBN 9781107060432 .