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, uno querría encontrar una asignación de ítems libre de envidia - una asignación en la que ningún agente envidie a otro agente. Es decir: ningún agente prefiere el paquete asignado a otro agente. Sin embargo, con ítems indivisibles esto podría ser imposible. Un enfoque para lidiar con esta imposibilidad es convertir el problema en un problema de optimización , en el que la función de pérdida es una función que describe la cantidad de envidia. En general, este problema de optimización es NP-hard , ya que incluso decidir si existe una asignación libre de envidia es equivalente al problema de partición . Sin embargo, hay algoritmos de optimización que pueden arrojar buenos resultados en la práctica.

Definiendo la cantidad de envidia

Existen varias formas de definir la función objetivo (la cantidad de envidia) para la minimización. Algunas de ellas son:

El número de agentes envidiosos ;
El número de relaciones de envidia (- aristas en el gráfico de envidia );
La razón de envidia máxima , donde la razón de envidia de i en j en la asignación X se define como: ; por lo que la razón es 1 si i no envidia a j , y es mayor cuando i envidia a j . ${\text{Ratio de envidia}}(X,i,j):=\max \left(1,{u_{i}(X_{j}) \over u_{i}(X_{i})}\right)$
- De manera similar, se puede considerar la suma de los ratios de envidia, o su producto.
El máximo, la suma o el producto de la diferencia de envidia .

Minimizar la proporción de envidia

En las valoraciones generales, cualquier algoritmo determinista que minimice la máxima relación 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 cuya máxima relación de envidia es como máximo 1,4 veces la óptima: ^[2]
1. Ordenar los artículos por valor descendente;
2. Mientras haya más artículos, entregue el siguiente artículo a un agente con el valor total más bajo.
Existe un PTAS para minimizar la proporción máxima de envidia. Además, cuando el número de jugadores es constante, existe un FPTAS .

Con valoraciones aditivas y diferentes : ^[3]

Cuando el número de agentes es parte de la entrada, es imposible obtener en tiempo polinomial 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 la razón de envidia máxima y el producto de las razones 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 se 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 elemento y "0" en caso contrario. La variable es propiedad del agente i .
Para expresar la restricción de que cada artículo se entrega 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 todos los elementos deben ser asignados, agregue una restricción n -aria para cada elemento (donde n es el número de agentes), con un costo infinito si ninguna variable relacionada con este elemento 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 sus variables lexicográficamente.
Cada agente, a su vez, reclama cualquier elemento que no haya sido asignado a un agente con mayor prioridad ("reclama" significa que el agente asigna "1" a la variable correspondiente).
Después de que un agente ha asignado todas sus variables (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 evaluación de envidia de la tarea actual.
Después de recibir evaluaciones de envidia de otros agentes, el agente puede decidir retroceder 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 en su primera variable, la búsqueda ha finalizado y se ha encontrado la asignación óptima.

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

En ocasiones, los artículos que se deben asignar no están disponibles todos a la vez, sino que llegan con el tiempo de forma online. Cada artículo que llega debe asignarse de inmediato. Un ejemplo de aplicación es el problema de un banco de alimentos , que acepta donaciones de alimentos y debe asignarlas de inmediato 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 elemento esté en [0,1]. Nótese que en la variante fuera de línea de esta configuración, es fácil encontrar una asignación en la que la máxima diferencia de envidia sea 1 (tal asignación se llama EF1; vea la asignación de elementos sin envidia para más detalles). Sin embargo, en la variante en línea la diferencia de envidia aumenta con el número de elementos. Muestran un algoritmo en el que la envidia después de T elementos está en . Jiang, Kulkarni y Singla ^[6] mejoran su límite de envidia usando un algoritmo para la minimización de discrepancia bidimensional en línea . $O({\sqrt {T/n}})$

Otros ajustes

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 5.ª conferencia de la ACM sobre comercio electrónico - EC '04 . pág. 125. doi :10.1145/988772.988792. ISBN 1-58113-771-0.
^ Graham, RL (1969). "Límites en anomalías de tiempo de multiprocesamiento". Revista SIAM de Matemáticas Aplicadas . 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áticas Aplicadas Discretas . 179 : 54–68. doi : 10.1016/j.dam.2014.09.010 .
^ ab Netzer, Arnon; Meisels, Amnon; 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 . EC '18. Ithaca, NY, EE. UU.: Association for Computing Machinery. págs. 593–610. doi :10.1145/3219166.3219179. ISBN 978-1-4503-5829-3. Número de identificación del sujeto 3340196.
^ Jiang, Haotian; Kulkarni, Janardhan; Singla, Sahil (2 de octubre de 2019). "Discrepancia geométrica en línea para llegadas estocásticas con aplicaciones para la minimización de la envidia". arXiv : 1910.01073 [cs.DS].
^ Yukihiro, Nishimura (2008). "Minimización de la envidia en el contexto fiscal óptimo". AgEcon Search . 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 en Nueva Orleans". Serie de documentos de trabajo. doi :10.3386/w23265. S2CID 9497845. {{cite journal}}: Requiere citar revista |journal=( ayuda )