Minimización de la envidia

En informática e investigación de operaciones , el problema de minimización de la envidia es el problema de asignar elementos discretos entre agentes con diferentes valoraciones sobre los elementos, de modo que la cantidad de envidia sea lo más pequeña posible.

Idealmente, desde una perspectiva de equidad, a uno le gustaría encontrar una asignación de elementos libre de envidia : una asignación en la que ningún agente envidia a otro agente. Es decir: ningún agente prefiere el paquete asignado a otro agente. Sin embargo, con elementos indivisibles esto podría resultar imposible. Una forma de afrontar esta imposibilidad es convertir el problema en un problema de optimización , en el que la función de pérdida sea una función que describa la cantidad de envidia. En general, este problema de optimización es NP-difícil , ya que incluso decidir si existe una asignación libre de envidia es equivalente al problema de partición . Sin embargo, existen algoritmos de optimización que pueden dar buenos resultados en la práctica.

Definiendo la cantidad de envidia

Hay varias formas de definir la función objetivo (la cantidad de envidia) a minimizar. Algunos de ellos son:

El número de agentes envidiosos ;
El número de relaciones de envidia (- bordes en el gráfico de envidia );
El índice de envidia máximo , donde el índice de envidia de i en j en la asignación X se define como :; entonces la proporción es 1 si no envidio a j , y es mayor cuando envidio a j . ${\text{EnvyRatio}}(X,i,j):=\max \left(1,{u_{i}(X_{j}) \over u_{i}(X_{i})} \bien)$
- De manera similar, se puede considerar la suma de las razones de envidia, o su producto.
El máximo, la suma o el producto de la envidia-diferencia .

Minimizar el ratio de envidia

Con valoraciones generales, cualquier algoritmo determinista que minimice el máximo índice de envidia requiere un número de consultas que es exponencial en el número de bienes en el peor de los casos. ^[1]^{: 3}

Con valoraciones aditivas e idénticas : ^[1]^{: 4–6}

El siguiente algoritmo codicioso encuentra una asignación cuyo índice de envidia máximo es como máximo 1,4 veces el óptimo: ^[2]
1. Ordene los artículos por valor descendente;
2. Mientras haya más artículos, entregue el siguiente artículo al agente con el valor total más pequeño.
Existe un PTAS para minimizar el índice máximo de envidia. Además, cuando el número de jugadores es constante, existe una FPTAS .

Con valoraciones aditivas y diferentes : ^[3]

Cuando el número de agentes forma parte del input, es imposible obtener en tiempo polinómico un factor de aproximación mejor que 1,5, a menos que P=NP.
Cuando el número de agentes es constante (no es parte de la entrada), existe un FPTAS para minimizar el índice de envidia máximo y el producto de los índices de envidia.
Cuando el número de agentes es igual al número de elementos, existe un algoritmo de tiempo polinomial.

Minimización de la envidia distribuida

En algunos casos, es necesario calcular una asignación que minimice la envidia de manera distribuida, es decir, cada agente debe calcular su propia asignación, de manera que garantice que la asignación resultante sea consistente. Este problema se puede resolver presentándolo como un problema de optimización de restricciones distribuidas asimétricas (ADCOP) de la siguiente manera. ^[4]

Agregue una variable binaria v _ij para cada agente i y elemento j . El valor de la variable es "1" si el agente obtiene el artículo y "0" en caso contrario. La variable es propiedad del agente i .
Para expresar la restricción de que cada artículo se le da como máximo a un agente, agregue restricciones binarias para cada dos variables diferentes relacionadas con el mismo artículo, con un costo infinito si las dos variables son simultáneamente "1" y un costo cero en caso contrario.
Para expresar la restricción de que se deben asignar todos los artículos, agregue una restricción n -aria para cada artículo (donde n es el número de agentes), con un costo infinito si ninguna variable relacionada con este artículo es "1".

El problema se puede resolver utilizando el siguiente algoritmo de búsqueda local . ^[4]

Todos los agentes están ordenados lexicográficamente (por ejemplo, por su nombre o índice).
Cada agente también ordena lexicográficamente sus variables.
Cada agente, a su vez, reclama cualquier elemento que no haya sido asignado a un agente con mayor prioridad ("reclamaciones" significa que el agente asigna "1" a la variable correspondiente).
Después de que un agente ha asignado todas sus variables (ya sea 1 o 0), envía la asignación resultante al siguiente agente en el orden lexicográfico.
Los agentes se envían mensajes entre sí con su envidia evaluación de la misión actual.
Después de recibir evaluaciones de envidia de otros agentes, el agente puede decidir dar marcha atrás en una variable; Si no hay más variables para retroceder, el agente puede retroceder a un agente anterior. Una vez que el primer agente retrocede su primera variable, la búsqueda finaliza y se encuentra la asignación óptima.

Minimización en línea de la diferencia de envidia

A veces, los elementos a asignar no están disponibles todos a la vez, sino que llegan con el tiempo en línea. Cada artículo que llega debe asignarse inmediatamente. Un ejemplo de aplicación es el problema de un banco de alimentos , que acepta donaciones de alimentos y debe destinarlas inmediatamente a organizaciones benéficas.

Benade, Kazachkov, Procaccia y Psomas ^[5] consideran el problema de minimizar la máxima diferencia de envidia , donde las valoraciones se normalizan de modo que el valor de cada artículo esté en [0,1]. Tenga en cuenta que en la variante fuera de línea de esta configuración, es fácil encontrar una asignación en la que la diferencia de envidia máxima sea 1 (dicha asignación se llama EF1; consulte la asignación de elementos sin envidia para obtener más detalles). Sin embargo, en la variante online la diferencia de envidia aumenta con el número de artículos. Muestran un algoritmo en el que la envidia después de T elementos está en . Jiang, Kulkarni y Singla ^[6] mejoran su envidia utilizando un algoritmo para la minimización de discrepancias bidimensionales en línea . $O({\sqrt {T/n}})$

Otras configuraciones

Otros entornos en los que se estudió la minimización de la envidia son:

Impuesto óptimo . ^[7]
Elección de escuela . ^[8]

Referencias

^ ab Lipton, RJ; Markakis, E.; Mossel, E.; Saberi, A. (2004). "Sobre asignaciones aproximadamente justas de bienes indivisibles". Actas de la quinta conferencia de la ACM sobre comercio electrónico - EC '04 . pag. 125. doi : 10.1145/988772.988792. ISBN 1-58113-771-0.
^ Graham, RL (1969). "Límites de las anomalías de sincronización del multiprocesamiento". Revista SIAM de Matemática Aplicada . 17 (2): 416–429. CiteSeerX 10.1.1.90.8131 . doi :10.1137/0117039.
^ Nguyen, Trung Thanh; Rothe, Jörg (2014). "Minimizar la envidia y maximizar el bienestar social promedio de Nash en la asignación de bienes indivisibles". Matemática Aplicada Discreta . 179 : 54–68. doi : 10.1016/j.dam.2014.09.010 .
^ ab Netzer, Arnón; Meisels, Amnón; Zivan, Roie (1 de marzo de 2016). "Minimización de la envidia distribuida para la asignación de recursos". Agentes Autónomos y Sistemas Multiagente . 30 (2): 364–402. doi :10.1007/s10458-015-9291-7. ISSN 1387-2532. S2CID 13834856.
^ Benade, Gerdus; Kazachkov, Aleksandr M.; Procaccia, Ariel D.; Psomas, Christos-Alexandros (11 de junio de 2018). "Cómo hacer que la envidia desaparezca con el tiempo". Actas de la Conferencia ACM de 2018 sobre Economía y Computación . CE '18. Ithaca, Nueva York, EE. UU.: Asociación de Maquinaria de Computación. págs. 593–610. doi :10.1145/3219166.3219179. ISBN 978-1-4503-5829-3. S2CID 3340196.
^ Jiang, Haotian; Kulkarni, Janardhan; Singla, Sahil (2 de octubre de 2019). "Discrepancia geométrica en línea para llegadas estocásticas con aplicaciones a la minimización de la envidia". arXiv : 1910.01073 [cs.DS].
^ Yukihiro, Nishimura (2008). "Minimización de la envidia en el contexto fiscal óptimo". Búsqueda AgEcon . Documento de trabajo n.° 1178. doi :10.22004/ag.econ.273655.
^ Abdulkadiroglu, Atila; Che, Yeon-Koo; Pathak, Parag A.; Roth, Alvin E.; Tercieux, Olivier (27 de marzo de 2017). "Minimizar la envidia justificada en la elección de escuela: el diseño de OneApp de Nueva Orleans". Serie de documentos de trabajo. doi :10.3386/w23265. S2CID 9497845. {{cite journal}}: Citar diario requiere |journal=( ayuda )