Envidiosa distribución de objetos.

La distribución de objetos sin envidia (sin envidia, KB, English Envy-free , EF distribución [1] ) es un problema de distribución justa de objetos , en el que el criterio de justicia es la ausencia de envidia en la distribución resultante - cada agente debe recibir un conjunto de objetos, cuyo valor (según él considere) no sea inferior a las acciones recibidas por otros agentes [2] .

Dado que los objetos son indivisibles, es posible que la distribución de KB no exista. El caso más simple de tal división es un objeto, que debe distribuirse entre al menos dos agentes: si un agente obtiene el objeto, el segundo lo envidiará. Así, los procedimientos de división implican varios tipos de relajación del requisito de no envidia .

Encontrar una distribución libre de envidia, si existe

Preferencias de pedido de conjuntos: Sin celos

El procedimiento de poda encuentra una distribución de KB completa para dos agentes si y solo si dicha distribución existe. El procedimiento requiere que los agentes clasifiquen conjuntos de objetos, pero no requiere información de utilidad cuantitativa . El algoritmo funciona si las preferencias de los agentes son estrictamente monótonas y no hay necesidad de asumir que son preferencias adaptativas . En el peor de los casos, los agentes pueden tener varios conjuntos posibles, por lo que el tiempo de ejecución puededepender exponencialmente del número de objetos.

Orden de preferencia de objetos: notorio/posible sin envidia

Por lo general, es más fácil para las personas ordenar objetos individuales que ordenar conjuntos de objetos. Asumiendo que todos los agentes tienen preferencias adaptativas , entonces es posible elevar la ordenación de objetos a una ordenación parcial de conjuntos. Por ejemplo, si los objetos están ordenados w>x>y>z, esto implica que {w, x}>{y, z} y {w, y}>{x, z}, pero no implica ninguna preferencia entre {w, z} y {x, y}, entre {x} y {y, z}, y así sucesivamente.

Dada una ordenación de objetos:

Se sabe que una distribución está libre de envidia ( necesariamente libre de envidia , NEF) si no está libre de envidia para todas las ordenaciones de conjuntos adaptables consistentes con la ordenación de objetos;
Una distribución posiblemente esté libre de envidia (posiblemente libre de envidia , PEF ) si no está libre de envidia para al menos una ordenación de conjuntos adaptativos consistente con la ordenación de objetos;
Una distribución es ciertamente Pareto - óptima ( NPE) si es Pareto-óptima para todos los ordenamientos de conjuntos adaptativos consistentes con el ordenamiento de objetos;
Una distribución es posiblemente Pareto-óptima (PPE) si es Pareto-óptima para al menos una ordenación de conjuntos adaptativos consistente con la ordenación de objetos.

Bouvre, Endriss y Leng [3] estudiaron los problemas algorítmicos de encontrar una distribución ZBZ/WBZ con una condición adicional de eficiencia, parcialidad, integridad, COP o COP. En general, el caso WBZ es computacionalmente más simple, mientras que el caso ZBZ es más difícil.

¿Existe una distribución KB

La distribución vacía siempre es KB, pero si queremos requerir eficiencia además de KB, la solución al problema se vuelve computacionalmente difícil [4] :

Decidir si existe una distribución KB completa es un problema NP-completo . Esto es cierto incluso cuando solo hay dos agentes e incluso cuando las funciones de utilidad son aditivas e idénticas , ya que en este caso la búsqueda de una distribución de KB equivale a resolver el problema de particionar un conjunto de números [5] .
Decidir si existe una distribución KB eficiente en el sentido de Pareto es más difícil que una distribución NP; es completa incluso con funciones de preferencia dicotómicas [6] e incluso con funciones de utilidad aditivas [7] . $\Sigma _{2}^{\textrm {P}}$

Distribución de búsquedas con nivel limitado de envidia

Algunos procedimientos encuentran una distribución que no tiene envidia, excepto por un objeto (BZ1) : para dos agentes A y B, hay un objeto, al eliminarlo del conjunto del agente B, el agente A ya no envidiará al agente B. [8] .

Procedimiento circular

Si todos los agentes tienen utilidades poco aditivas , el siguiente protocolo (que es similar a la planificación por turnos ) brinda la distribución completa de KB1:

Organizar los agentes de forma arbitraria.
Siempre que haya objetos sin asignar
- Permitimos que los agentes con números a partir del 1 elijan un objeto. $norte$

Prueba [9] : para cualquier agente , dividimos las elecciones realizadas por los agentes en subsecuencias : la primera subsecuencia comienza con el agente 1 y termina con el agente . La última subsecuencia comienza con y termina con . En la segunda secuencia, el agente elige primero, por lo que elige el mejor objeto y, por lo tanto, no envidia al otro agente. Un agente solo puede envidiar a uno de los agentes , y cualquier envidia proviene solo del objeto que se eligió en la primera subsecuencia. Si se quita este objeto, el agente no estará celoso.

i

i-1

i

i-1

i

i

{\ estilo de visualización 1,..., i-1}

i

El protocolo round robin requiere una aditividad débil , ya que requiere que cada agente elija el "mejor objeto" sin saber qué objetos elegirá posteriormente. En otras palabras, esto supone que los objetos son bienes independientes .

Procedimiento del Ciclo de la Envidia

El procedimiento de ciclos de envidia devuelve la distribución BZ1 completa para relaciones de preferencia arbitrarias. El único requisito es que los agentes puedan ordenar sus conjuntos de objetos.

Si las preferencias de los agentes están representadas por una función de utilidad cardinal , entonces la garantía BZ1 tiene una interpretación adicional: el nivel numérico de envidia de cada agente no excede la utilidad marginal máxima , es decir, la utilidad marginal máxima de un objeto individual para este agente

Procedimiento P-CRRD aproximado

Equilibrio competitivo aproximado a partir de ingresos iguales ( A- CEEI ) devuelve una distribución B31 parcial para preferencias arbitrarias. El único requisito es que el agente pueda ordenar colecciones de objetos.

Una pequeña cantidad de objetos pueden permanecer sin asignar. La distribución es eficiente en el sentido de Pareto para objetos distribuidos. Además, el mecanismo P-CRRD es aproximadamente estratégicamente invulnerable si el número de agentes es grande.

Máximo bienestar de Nash

El algoritmo Maximum-Nash-Welfare (MNW) elige la distribución completa que maximiza el producto de las utilidades. Requiere que cada agente proporcione un valor numérico para cada objeto y asume que las utilidades para los agentes son aditivas. La distribución resultante también será eficiente en BZ1 y Pareto [9] .

Si las preferencias de los agentes no son aditivas, la solución MNB no es necesariamente BZ1, pero si las preferencias de los agentes son al menos submodulares , la solución MNB satisface una propiedad más débil llamada distribución marginal sin envidia excepto por 1 objeto ( Marginal-Envy- Freeness , MEF1).

BZ1 / BZd

Hay un criterio alternativo llamado Sin Envidia excepto por el Más Barato (BZd) para dos agentes A y B. Si eliminamos cualquier objeto del conjunto de objetos del agente B, entonces A no envidiará a B. BZd es estrictamente más fuerte que BZ1. Pero aún se desconoce si siempre hay distribuciones BZd [9] .

Minimizando la Relación de Envidia

Dada una distribución de X , defina la relación de envidia de i a j (EnvyRatio) como:

EnvyRatio(X,i,j):=\max(1,{u_{i}(X_{j}) \over u_{i}(X_{i})})

entonces la razón es 1 si i no está celoso de j , y mayor que 1 si i está celoso de j . Definimos la relación de envidia de distribución como:

Relación de envidia(X):=\max _{i,j}(Relación de envidia(X,i,j)

El problema de minimización de la relación de envidia es el problema de encontrar la distribución X con la relación de envidia más pequeña.

Presupuestos generales

Según las preferencias generales, cualquier algoritmo determinista que calcule una distribución con un índice de envidia mínimo requiere un número de consultas que, en el peor de los casos, depende exponencialmente del número de objetos [5] .

Puntajes iguales aditivos

Con puntajes de preferencia aditivos e idénticos [5] :

El siguiente algoritmo codicioso encuentra una distribución cuya relación de envidia es como máximo 1,4 veces el mínimo [10] ;
1. Colocamos los objetos en orden descendente de valor;
2. Mientras haya objetos sin asignar, le damos el siguiente objeto al agente con el valor total mínimo;
Existe un esquema PTAS para minimizar la relación de envidia. Además, si el número de jugadores es constante, existe un esquema FPTAS .

Estimaciones varias aditivas

Con estimaciones de preferencias aditivas y diferentes [11]

Si el número de agentes se incluye en los datos de entrada, entonces en tiempo polinomial es imposible obtener un coeficiente de aproximación mejor que 1,5. A menos que P=NP.
Si el número de agentes es constante, existe un esquema FPTAS .
Si el número de agentes es igual al número de objetos, existe un algoritmo de distribución de tiempo polinomial.

Búsqueda de distribución parcial sin envidia

El procedimiento AL encuentra la distribución de KB para dos agentes. Puede descartar algunos de los objetos, pero la distribución final es eficiente en el sentido de Pareto en el sentido de que ninguna otra distribución de KB es mejor para uno y ligeramente mejor para el otro. El procedimiento AL requiere ordenar por valor los objetos separados solo de los agentes. El procedimiento asume que los agentes tienen preferencias adaptativas , y da una distribución que se sabe que no tiene envidia ( ciertamente sin envidia, ZBZ).

El procedimiento " ganador de ajuste " devuelve la distribución KB completa y efectiva para los dos agentes, pero puede requerir cortar uno de los objetos (o uno de los objetos permanece en uso común). El procedimiento requiere que cada agente informe un valor de utilidad numérico para cada objeto y asume que los agentes tienen funciones de utilidad aditivas .

La existencia de colocación sin envidia con evaluaciones aleatorias

Si los agentes tienen funciones de utilidad aditivas , que se toman de distribuciones de probabilidad que satisfacen algunos criterios, y la cantidad de objetos es lo suficientemente grande en relación con la cantidad de agentes, entonces la distribución KB existe con alta probabilidad . En particular [12]

Si el número de objetos es lo suficientemente grande , entonces existe la distribución KB con una alta probabilidad (es decir, la probabilidad tiende a 1 cuando m tiende a infinito). $m=\Omega (n\log n)$
Si el número de objetos no es lo suficientemente grande, es decir , es muy probable que la distribución de KB no exista. ${\ estilo de visualización m = n + o (n)}$

Falta de Envidia y Otros Criterios de Justicia

Cualquier distribución de KB es mínima-máxima justa . Esto se sigue directamente de las definiciones habituales y no depende de la aditividad.
Si los agentes tienen funciones de utilidad aditivas , entonces la distribución de KB también es proporcional y max-min-fair . De lo contrario, la distribución de KB puede no ser proporcional y puede que ni siquiera sea máxima-mínima-justa.
Cualquier distribución que tenga un equilibrio competitivo con ingresos iguales no tiene envidia. Esto es cierto independientemente de la aditividad [8] .
Cualquier distribución óptima de Nash (distribución que maximiza el producto de las utilidades) es una KB1 [9] .

Ver el artículo El problema de una distribución justa de objetos con una descripción detallada y referencias a la literatura.

Mesa final

A continuación se utilizan las siguientes notaciones:

$norte$ = número de agentes que participan en la compartición;
$metro$ = número de artículos (objetos) a distribuir;
BE = sin envidia, BE1 = sin envidia con la exclusión de un sujeto (requisito más débil que BE), BE1 = máximo sin envidia con la exclusión de un sujeto (requisito más débil que BE1).
EP = Pareto eficiente (PE = Inglés Pareto-eficiente ).

Nombre	Número de participantes	Entrada	preferencias	Número de solicitudes	Justicia	Eficiencia	Comentarios
Poda	2	Conjuntos ordenados	Estrictamente monótono	$2^{m}$	BZ	Completo	Si y solo si existe una distribución completa de KB
procedimiento AL	2	Objetos ordenados	Débilmente aditivo	${\ Displaystyle Poli (m)}$	Obviamente-BZ	Parcial, pero la distribución no está dominada por Pareto por otra ZBZ
Ganador ajustable	2	Valoración de objetos	Aditivo	${\ Displaystyle Poli (m)}$	bien informado e imparcial	EP	Un objeto puede ser compartido
planificación circular	$norte$	Objetos ordenados	Débilmente aditivo	$metro$	Obviamente-BZ1	Completo
ciclos de envidia	$norte$	Conjuntos ordenados	monótono	$O(mn^{3})$	BZ1	Completo
Mecanismo P-CRRD	$norte$	Conjuntos ordenados	Ningún	?	BZ1, y - maximización de acciones $(n+1)$	Parcial, pero ES en relación con los objetos distribuidos	Aproximadamente estratégicamente invulnerable si hay muchos agentes.
Máximo bienestar de Nash [9]	$norte$	Valoración de objetos	Aditivo	NP-hard (pero existen en casos especiales de aproximación)	BZ1 y aproximadamente -maximización de acciones $norte$	EP	Con funciones de utilidad submodulares, la distribución es EF y PBZ1.

Véase también

La maximización de las acciones es otro criterio de equidad.

Notas

↑ Literalmente - la distribución de objetos sin envidia, lo cual, en general, es confuso - solo la envidia es el factor principal en tal distribución.
↑ Brandt, Conitzer, Endriss et al., 2016 , pág. 296–297.
↑ Bouveret, Endriss, Lang, 2010 , pág. 387–392.
↑ Brandt, Conitzer, Endriss et al., 2016 , pág. 300–310.
↑ 1 2 3 Lipton, Markakis, Mossel, Saberi, 2004 , pág. 125.
↑ Bouveret, Lang, 2008 , pág. 525–564.
↑ De Keijzer, Bouveret, Klos, Zhang, 2009 , pág. 98.
↑ 1 2 Budish, 2011 , p. 1061-1103.
↑ 1 2 3 4 5 Caragiannis, Kurokawa et al., 2016 , pág. 305.
↑ Graham, 1969 , pág. 416–429.
↑ Nguyen, Rothe, 2014 , pág. 54–68.
↑ Dickerson, Goldman et al., 2014 , pág. 1405–1411.

Literatura

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 .
Sylvain Bouveret, Ulle Endriss, Jérôme Lang. División justa bajo preferencias ordinales: computación de asignaciones de bienes indivisibles sin envidia // ECAI 2010. - 2010. - págs. 387–392.
Bouveret S., Lang J. Eficiencia y ausencia de envidia en la división justa de bienes indivisibles: representación lógica y complejidad // JAIR. - 2008. - T. 32 . -doi : 10.1613 / jair.2467 .
Bart De Keijzer, Sylvain Bouveret, Tomas Klos, Yingqian Zhang. Sobre la complejidad de la eficiencia y la ausencia de envidia en la división justa de bienes indivisibles con preferencias aditivas // Teoría de la decisión algorítmica. - 2009. - T. 5783. - (Apuntes de cátedra en Informática). - ISBN 978-3-642-04427-4 . -doi : 10.1007 / 978-3-642-04428-1_9 .
Eric Budista. El problema de asignación combinatoria: equilibrio competitivo aproximado a partir de ingresos iguales // Revista de economía política. - 2011. - T. 119 , núm. 6 _ -doi : 10.1086/ 664613 .
Ioannis Caragiannis, David Kurokawa, Herve Moulin, Ariel D. Procaccia, Nisarg Shah, Junxing Wang. La justicia irrazonable del máximo bienestar de Nash // Actas de la Conferencia ACM de 2016 sobre economía y computación - EC '16 . - 2016. - S. 305. - ISBN 9781450339360 . -doi : 10.1145/ 2940716.2940726 .
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 .
Graham RL Límites en anomalías de tiempo de multiprocesamiento // SIAM Journal on Applied Mathematics. - 1969. - T. 17 , núm. 2 . -doi : 10.1137/ 0117039 .
Trung Thanh Nguyen, Jörg Rothe. Minimizando la envidia y maximizando el bienestar social promedio de Nash en la asignación de bienes indivisibles // Matemáticas Aplicadas Discretas. - 2014. - T. 179 . -doi : 10.1016/ j.dam.2014.09.010 .
John P. Dickerson, Jonathan Goldman, Jeremy Karp, Ariel D. Procaccia, Tuomas Sandholm. El auge computacional y la caída de la equidad // En las actas de la vigésima octava conferencia AAAI sobre inteligencia artificial (2014). — 2014. Enlace ACM