Asignación de artículos sin envidia

Problema de asignación justa de elementos

La asignación de ítems sin envidia (EF) es un problema de asignación de ítems justa , en el que el criterio de equidad es la ausencia de envidia : cada agente debe recibir un paquete que crea que es al menos tan bueno como el paquete de cualquier otro agente. ^{[1] : 296–297}

Como los elementos son indivisibles, no puede existir una asignación de EF. El caso más simple es cuando hay un solo elemento y al menos dos agentes: si el elemento se asigna a un agente, el otro lo envidiará.

Una forma de lograr la equidad es utilizar transferencias monetarias . Cuando las transferencias monetarias no están permitidas o no son deseadas, existen algoritmos de asignación que ofrecen diversos tipos de flexibilidades.

Encontrar una asignación libre de envidia cuando exista

Ordenamientos de preferencia en los paquetes: ausencia de envidia

El procedimiento de socavación encuentra una asignación de EF completa para dos agentes, si y solo si dicha asignación existe. Requiere que los agentes clasifiquen paquetes de elementos, pero no requiere información de utilidad cardinal. Funciona siempre que las relaciones de preferencia de los agentes sean estrictamente monótonas, pero no necesita asumir que son preferencias responsivas . En el peor de los casos, los agentes pueden tener que clasificar todos los paquetes posibles, por lo que el tiempo de ejecución puede ser exponencial en la cantidad de elementos.

Ordenamiento de preferencias sobre los artículos: necesaria/posible ausencia de envidia

Por lo general, es más fácil para las personas clasificar elementos individuales que clasificar paquetes. Suponiendo que todos los agentes tienen preferencias receptivas , es posible elevar la clasificación de elementos a una clasificación de paquete parcial. Por ejemplo, si la clasificación de elementos es w>x>y>z, entonces la capacidad de respuesta implica que {w,x}>{y,z} y {w,y}>{x,z}, pero no implica nada sobre la relación entre {w,z} y {x,y}, entre {x} e {y,z}, etc. Dado un ranking de elementos:

• Una asignación es necesariamente libre de envidia (NEF) si está libre de envidia de acuerdo con todas las clasificaciones de paquetes en respuesta que son consistentes con la clasificación de elementos;
• Una asignación es posiblemente libre de envidia (PEF) si para cada agente i , hay al menos una clasificación de paquete responsiva consistente con la clasificación de ítems de i , por la cual i no envidia;
• Una asignación es débilmente posiblemente libre de envidia (WPEF) si para cada par de agentes i, j , hay al menos una clasificación de paquete responsiva consistente con la clasificación de ítems de i , por la cual i no envidia a j ;
• Una asignación es necesariamente Pareto-óptima (NPE) si es Pareto-óptima de acuerdo con todas las clasificaciones de paquetes que responden a la clasificación de elementos (ver Eficiencia ordinal de Pareto );
• Una asignación es posiblemente Pareto-óptima (PPE) si es Pareto-óptima de acuerdo con al menos una clasificación de paquete responsiva consistente con la clasificación de artículos.

Se conocen los siguientes resultados:

• Bouveret, Endriss y Lang ^[2] suponen que todos los agentes tienen preferencias estrictas . Estudian las cuestiones algorítmicas de encontrar una asignación NEF/PEF con una condición de eficiencia adicional, en particular, completitud o NPE o PPE. En general, PEF es fácil mientras que NEF es difícil: verificar si existe una asignación NEF es NP-completo , mientras que verificar la existencia de WPEF se puede hacer en tiempo polinomial.
• Aziz, Gaspers, Mackenzie y Walsh ^[3] estudian el contexto más general en el que los agentes pueden tener preferencias débiles (con indiferencias). En este contexto, comprobar la existencia de WPEF es NP-completo. Decidir si existe una asignación de PEF está en P para preferencias estrictas o para n=2, pero es NP-completo en general. Es una pregunta abierta si, cuando el número de agentes es constante, decidir la existencia de una asignación de NEF está en P.

Utilidades cardinales

La asignación vacía siempre es EF. Pero si queremos algo de eficiencia además de EF, entonces el problema de decisión se vuelve computacionalmente difícil: ^{[1] : 300–310}

• Decidir si existe un EF y una asignación completa es NP completo . Esto es cierto incluso cuando solo hay dos agentes, e incluso cuando sus utilidades son aditivas e idénticas, ya que en este caso encontrar una asignación EF es equivalente a resolver el problema de partición . ^[4]
• Para decidir si existe una asignación justa se requiere una comunicación exponencial (en el número de bienes) cuando hay más de dos agentes. Cuando hay dos agentes, la complejidad de la comunicación depende de combinaciones específicas de parámetros. ^[5]
• Decidir si existe una asignación EF y Pareto eficiente está por encima de NP: es -completo incluso con utilidades dicotómicas ^[6] e incluso con utilidades aditivas [ ^7] ( es la clase de problemas que se pueden resolver en tiempo no determinista dado un oráculo que puede resolver cualquier problema en NP). ${\displaystyle \Sigma _{2}^{\textrm {P}}}$ ${\displaystyle \Sigma _{2}^{\textrm {P}}}$

El problema de decisión puede volverse manejable cuando algunos parámetros del problema se consideran constantes pequeñas fijas: ^[8]

• Considerando el número de objetos m como parámetro, se puede decidir a tiempo la existencia de una asignación PE+EF para utilidades aditivas o dicotómicas. Cuando las utilidades son binarias y/o idénticas, el tiempo de ejecución se reduce a . Aquí, la notación oculta expresiones que son polinómicas en los otros parámetros (por ejemplo, número de agentes). ${\displaystyle O^{*}(m^{2m})}$ ${\displaystyle O^{*}(m^{m})}$ ${\displaystyle O^{*}}$
• Considerando el número de agentes n como parámetro, la existencia de una asignación PE+EF sigue siendo difícil. Con utilidades dicotómicas, es NP-difícil incluso para n = 2. ^[6] Sin embargo, ahora está en NP y se puede resolver de manera eficiente con un oráculo NP (por ejemplo, un solucionador SAT ). Con agentes, se puede hacer con dichos oráculos, y al menos se necesitan oráculos a menos que P = NP. Con utilidades aditivas, es NP-difícil incluso para n = 2. ^[6] Además, es W[1]-completo con respecto al número de agentes incluso si todas las utilidades son idénticas y están codificadas en unario. ${\displaystyle n\geq 5}$ ${\displaystyle 2^{n+1}}$ ${\displaystyle 2^{n-4}}$
• Considerando tanto el número de agentes n como la mayor utilidad V como parámetros, la existencia de una asignación PE+EF se puede decidir a tiempo para utilidades aditivas utilizando programación dinámica . ${\displaystyle O^{*}((m\cdot V+1)^{n^{2}}\cdot mn^{2})}$
• Considerando tanto el número de agentes n como el número de niveles de utilidad z como parámetros, la existencia de una asignación PE+EF para utilidades aditivas idénticas se puede decidir utilizando un programa lineal entero con variables; el algoritmo de Lenstra permite resolver dicho ILP en el tiempo. ${\displaystyle d=n\cdot z^{n}}$ ${\displaystyle O^{*}(d^{2.5d})}$

Encontrar una asignación con un nivel de envidia limitado

Muchos procedimientos encuentran una asignación que está "casi" libre de envidia, es decir, el nivel de envidia está limitado. Existen varias nociones de "casi" libre de envidia:

EF1 - libre de envidia hasta un artículo como máximo

Una asignación se llama EF1 si por cada dos agentes A y B, si eliminamos como máximo un elemento del conjunto de B, entonces A no envidia a B. ^[9] Una asignación EF1 siempre existe y se puede encontrar de manera eficiente mediante varios procedimientos, en particular:

• Cuando todos los agentes tienen utilidades débilmente aditivas , el protocolo round-robin encuentra una asignación EF1 completa. La aditividad débil es necesaria ya que cada agente debería poder elegir, en cada situación, un "mejor elemento".
• En el caso más general, cuando todos los agentes tienen utilidades que aumentan monótonamente, el procedimiento del gráfico de envidia encuentra una asignación EF1 completa. El único requisito es que los agentes puedan clasificar conjuntos de artículos. Si las valoraciones de los agentes están representadas por una función de utilidad cardinal , entonces la garantía EF1 tiene una interpretación adicional: el nivel numérico de envidia de cada agente es, como máximo, la utilidad marginal máxima (la utilidad marginal más grande de un solo artículo para ese agente).
• Cuando los agentes tienen utilidades arbitrarias (no necesariamente aditivas o monótonas), el mecanismo A-CEEI devuelve una asignación EF1 parcial. El único requisito es que los agentes puedan clasificar conjuntos de elementos. Es posible que quede una pequeña cantidad de elementos sin asignar y que sea necesario agregar una pequeña cantidad de elementos. La asignación es eficiente en términos de Pareto con respecto a los elementos asignados.
• El algoritmo de máximo bienestar de Nash selecciona una asignación completa que maximiza el producto de las utilidades. Requiere que cada agente proporcione una valoración numérica de cada elemento y supone que las utilidades de los agentes son aditivas. La asignación resultante es EF1 y Pareto-eficiente . ^[10]
• Varios otros algoritmos devuelven asignaciones EF1 que también son Pareto-eficientes; consulte Asignación de elementos aproximadamente justa y eficiente .
• Para dos agentes con valoraciones monótonas arbitrarias, o tres agentes con valoraciones aditivas, se puede calcular una asignación EF1 utilizando un número de consultas logarítmico en el número de elementos. ^[11]
• Para dos agentes con funciones de utilidad arbitrarias (no necesariamente monótonas), se puede encontrar una asignación EF1 en tiempo polinomial. ^[12]
• Para un máximo de 4 agentes con valoraciones monótonas arbitrarias, o n agentes con valoraciones monótonas idénticas, siempre existe una asignación EF1 que también está conectada (cuando los elementos están preordenados en una línea, como las casas en una calle). La prueba utiliza un algoritmo similar a los protocolos Simmons-Su . Cuando hay n > 4 agentes, no se sabe si existe una asignación EF1 conectada, pero siempre existe una asignación EF2 conectada . ^[13]

EFx - sin envidia hasta en la mayoría de los artículos

Una asignación se denomina EFx si, por cada dos agentes A y B, si eliminamos cualquier elemento del conjunto de B, entonces A no envidia a B. ^[14] EFx es estrictamente más fuerte que EF1: EF1 nos permite eliminar la envidia eliminando el elemento más valioso (para A) del conjunto de B; EFx requiere que eliminemos la envidia eliminando el elemento menos valioso (para A). Se sabe que existe una asignación EFx en algunos casos especiales:

• Cuando hay dos agentes, o cuando hay n agentes con valoraciones idénticas , en este caso la asignación leximin -óptima es EFx y Pareto-óptima, pero requiere exponencialmente muchas consultas para su cálculo. ^{[15] [12]}
• Cuando hay n agentes con valoraciones aditivas , pero hay como máximo dos valores diferentes para los bienes, en este caso, cualquier asignación de bienestar de Nash máximo es EFx. Además, existe un algoritmo eficiente para calcular una asignación EFx (aunque no necesariamente de bienestar de Nash máximo). ^[16]
• Cuando hay n agentes con valoraciones aditivas , pero hay como máximo dos tipos diferentes de valoraciones. ^[17]
• Cuando hay tres agentes con valoraciones aditivas , en este caso existe un algoritmo de tiempo polinomial. ^{[18] [19]}

Se conocen algunas aproximaciones:

• Se puede encontrar una asignación EFx aproximada de 1/2 (que también satisface una noción diferente de equidad aproximada llamada Maximin Aware ) en tiempo polinomial. ^[20]
• Se puede encontrar una asignación EFx aproximada de 0,618 (que también es EF1 y se aproxima a otras nociones de equidad llamadas participación maximin por grupo y participación maximin por pares ^{) en tiempo polinomial. [21]}
• Siempre existe una asignación EFx parcial , donde el bienestar de Nash es al menos la mitad del máximo bienestar de Nash posible. En otras palabras, después de donar algunos artículos a una organización benéfica, los artículos restantes se pueden asignar de manera EFx. Este límite es el mejor posible. En mercados grandes, donde las valoraciones de un agente por cada artículo son relativamente pequeñas, el algoritmo alcanza EFx con un bienestar de Nash casi óptimo. ^[22] Es suficiente donar n -1 artículos, y ningún agente envidia el conjunto de artículos donados. ^[23]

No está claro si existe una asignación de EFx en general. El caso abierto más pequeño es el de 4 agentes con valoraciones aditivas.

A diferencia de EF1, que requiere una cantidad de consultas logarítmica en la cantidad de elementos, calcular una asignación EFx puede requerir una cantidad lineal de consultas incluso cuando hay dos agentes con valoraciones aditivas idénticas. ^[11]

Otra diferencia entre EF1 y EFx es que la cantidad de asignaciones de EFX puede ser tan pequeña como 2 (para cualquier cantidad de elementos), mientras que la cantidad de asignaciones de EF1 siempre es exponencial en la cantidad de elementos. ^[24]

EFm - aproximado libre de envidia para una mezcla de elementos divisibles e indivisibles

Algunos escenarios de división involucran elementos tanto divisibles como indivisibles, como terrenos divisibles y casas indivisibles. Una asignación se llama EFm si para cada dos agentes A y B: ^[25]

• Si el paquete de B contiene algunos bienes divisibles, entonces A no envidia a B (como en una asignación FE).
• Si el paquete de B contiene sólo bienes indivisibles, entonces A no envidia a B después de eliminar como máximo un artículo del paquete de B (como en una asignación EF1).

Existe una asignación de EFm para cualquier número de agentes. Sin embargo, para encontrarla se necesita un oráculo para la división exacta de una torta. Sin este oráculo, se puede calcular una asignación de EFm en tiempo polinómico en dos casos especiales: dos agentes con valoraciones aditivas generales o cualquier número de agentes con valoraciones lineales por partes.

A diferencia de EF1, que es compatible con la optimalidad de Pareto, EFm puede ser incompatible con ella.

Minimizar la envidia

En lugar de utilizar un límite de peor caso para la cantidad de envidia, se puede intentar minimizar la cantidad de envidia en cada caso particular. Consulte la minimización de la envidia para obtener más detalles y referencias.

Encontrar una asignación parcial de EF

El procedimiento AL encuentra una asignación de elementos de efecto invernadero para dos agentes. Puede descartar algunos de los elementos, pero la asignación final es Pareto-eficiente en el sentido siguiente: ninguna otra asignación de elementos de efecto invernadero es mejor para uno y débilmente mejor para el otro. El procedimiento AL solo requiere que los agentes clasifiquen los elementos individuales. Supone que los agentes tienen preferencias receptivas y devuelve una asignación que está necesariamente libre de envidia (NEF).

El procedimiento de ganador ajustado devuelve una asignación de EF completa y eficiente para dos agentes, pero es posible que deba eliminar un solo elemento (o bien, un elemento permanece en propiedad compartida). Requiere que los agentes informen un valor numérico para cada elemento y supone que tienen utilidades aditivas .

Cuando cada agente puede obtener como máximo un solo artículo y las valoraciones son binarias (a cada agente le gusta o le disgusta cada artículo), existe un algoritmo de tiempo polinomial que encuentra una correspondencia sin envidia de cardinalidad máxima. ^[26]

Existencia de asignaciones de EF con valoraciones aleatorias

Si los agentes tienen funciones de utilidad aditivas que se extraen de distribuciones de probabilidad que satisfacen ciertos criterios de independencia, y el número de elementos es suficientemente grande en relación con el número de agentes, entonces existe una asignación de FE con alta probabilidad . En particular:

• Si el número de elementos es suficientemente grande: , entonces existe una asignación EF (la probabilidad tiende a 1 cuando m tiende a infinito) y se puede encontrar mediante el protocolo round-robin . ^[27] ${\displaystyle m=\Omega (n\log n/\log \log n)}$
• Si , entonces existe una asignación de EF y se puede encontrar maximizando el bienestar social. ^[28] Este límite también es estricto debido a las conexiones con el problema del cobrador de cupones . ${\displaystyle m=\Omega (n\log n)}$
• Si m es divisible por n, entonces existe una asignación de EF y se puede encontrar mediante un algoritmo basado en correspondencia. ^[29] ${\displaystyle m\geq 2n}$

Por otra parte, si el número de elementos no es suficientemente grande, entonces, con alta probabilidad, no existe una asignación de FE.

• Si el número de elementos no es suficientemente grande, es decir, , entonces no existe una asignación de EF. ^[28] ${\displaystyle m=n+o(n)}$
• Si m no es "casi divisible" por n, entonces no existe una asignación EF. ^[29] ${\displaystyle m=o(n\log n/\log \log n)}$

Ausencia de envidia frente a otros criterios de equidad

• Toda asignación de EF es mínima-máxima-justa . Esto se desprende directamente de las definiciones ordinales y no depende de la aditividad.
• Si todos los agentes tienen funciones de utilidad aditivas , entonces una asignación de FE también es proporcional y máxima-mínima-justa . De lo contrario, una asignación de FE puede no ser proporcional e incluso no máxima-mínima-justa.
• Toda asignación de un equilibrio competitivo a partir de ingresos iguales también está libre de envidia. Esto es cierto independientemente de la aditividad. ^[9]
• Toda asignación óptima de Nash (asignación que maximiza el producto de las utilidades) es EF1. ^[14]
• La ausencia de envidia grupal es un fortalecimiento de la ausencia de envidia, que es aplicable tanto a objetos divisibles como indivisibles.

Consulte la asignación justa de artículos para obtener detalles y referencias.

Tabla resumen

A continuación se utilizan las siguientes abreviaturas:

• ${\displaystyle n}$= el número de agentes que participan en la división;
• ${\displaystyle m}$= el número de elementos a dividir;
• EF = libre de envidia, EF1 = libre de envidia excepto 1 elemento (más débil que EF), MEF1 = libre de envidia marginal excepto 1 elemento (más débil que EF1).
• PE = Pareto-eficiente.

Referencias

1. 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)
2. Bouveret, Sylvain; Endriss, Ulle; Lang, Jérôme (4 de agosto de 2010). "División justa bajo preferencias ordinales: cálculo de asignaciones libres de envidia de bienes indivisibles". Actas de la Conferencia de 2010 sobre ECAI 2010: 19.ª Conferencia Europea sobre Inteligencia Artificial . NLD: IOS Press: 387–392. ISBN 978-1-60750-605-8.
3. Aziz, Haris; Gaspers, Serge; Mackenzie, Simon; Walsh, Toby (1 de octubre de 2015). "Asignación justa de objetos indivisibles bajo preferencias ordinales". Inteligencia artificial . 227 : 71–92. arXiv : 1312.6546 . doi : 10.1016/j.artint.2015.06.002 . ISSN  0004-3702. S2CID  1408197.
4. 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.
5. Plaut, Benjamin; Roughgarden, Tim (1 de enero de 2020). "Complejidad de la comunicación de la división justa discreta". Revista SIAM de informática . 49 (1): 206–243. arXiv : 1711.04066 . doi :10.1137/19M1244305. ISSN  0097-5397. S2CID  212667868.
6. Bouveret, S.; Lang, J. (2008). "Eficiencia y ausencia de envidia en la división justa de bienes indivisibles: representación lógica y complejidad". Revista de investigación en inteligencia artificial . 32 : 525–564. doi : 10.1613/jair.2467 .
7. De Keijzer, Bart; Bouveret, Sylvain; Klos, Tomas; Zhang, Yingqian (2009). "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 . Apuntes de clase en informática. Vol. 5783. pág. 98. doi :10.1007/978-3-642-04428-1_9. ISBN 978-3-642-04427-4.
8. Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf (9 de julio de 2016). "Complejidad de la asignación eficiente y sin envidia de recursos: pocos agentes, recursos o niveles de utilidad". Actas de la 25.ª Conferencia Conjunta Internacional sobre Inteligencia Artificial . IJCAI'16. Nueva York, Nueva York, EE. UU.: AAAI Press: 102–108. ISBN 978-1-57735-770-4.
9. Budish, Eric (2011). "El problema de asignación combinatoria: equilibrio competitivo aproximado a partir de ingresos iguales". Revista de economía política . 119 (6): 1061–1103. CiteSeerX 10.1.1.357.9766 . doi :10.1086/664613. S2CID  154703357. 
10. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). La justicia irrazonable del bienestar máximo de Nash (PDF) . Actas de la Conferencia ACM de 2016 sobre Economía y Computación - EC '16. p. 305. doi :10.1145/2940716.2940726. ISBN 9781450339360.
11. Oh, Hoon; Procaccia, Ariel D.; Suksompong, Warut (17 de julio de 2019). "Asignación justa de muchos bienes con pocas consultas". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 33 (1): 2141–2148. arXiv : 1807.11367 . doi : 10.1609/aaai.v33i01.33012141 . ISSN  2374-3468. S2CID  51867780.
12. Bérczi, Kristóf; Bérczi-Kovács, Erika R.; Boros, Endre; Gedefa, Fekadu Tolessa; Kamiyama, Naoyuki; Kavitha, Telikepalli ; Kobayashi, Yusuke; Makino, Kazuhisa (8 de junio de 2020). "Relajaciones sin envidia para bienes, tareas y artículos mixtos". arXiv : 2006.04428 [econ.TH].
13. Bilò, Vittorio; Caragiannis, Ioannis; Flammini, Michele; Igarashi, Ayumi; Mónaco, Gianpiero; Peters, Dominik; Vinci, Cosimo; Zwicker, William S. (2022). "Asignaciones casi sin envidia con paquetes conectados". Juegos y comportamiento económico . 131 : 197–221. arXiv : 1808.09406 . doi :10.1016/j.geb.2021.11.006. S2CID  52112902.
14. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). La justicia irrazonable del bienestar máximo de Nash (PDF) . Actas de la Conferencia ACM de 2016 sobre Economía y Computación - EC '16. p. 305. doi :10.1145/2940716.2940726. ISBN 9781450339360.
15. Plaut, Benjamin; Roughgarden, Tim (1 de enero de 2020). "Casi ausencia de envidia con valoraciones generales". Revista SIAM de Matemáticas Discretas . 34 (2): 1039–1068. arXiv : 1707.04769 . doi :10.1137/19M124397X. ISSN  0895-4801. S2CID  216283014.
16. Amanatidis, Georgios; Birmpas, Georgios; Filos-Ratsikas, Aris; Hollender, Alexandros; Voudouris, Alexandros A. (2021). "El bienestar máximo de Nash y otras historias sobre EFX". Ciencias de la Computación Teórica . 863 : 69–85. arXiv : 2001.09838 . doi :10.1016/j.tcs.2021.02.020. S2CID  210920309.
17. Mahara, Ryoga (20 de agosto de 2020). "Existencia de EFX para dos valoraciones aditivas". arXiv : 2008.08798 [cs.GT].
18. Chaudhury, Bhaskar Ray; Garg, Jugal; Mehlhorn, Kurt (30 de mayo de 2020). "EFX existe para tres agentes". arXiv : 2002.05119 [cs.GT].
19. {{cita arXiv:2205.07638 [cs.GT]}}
20. Chan, Hau; Chen, Jing; Li, Bo; Wu, Xiaowei (25 de octubre de 2019). "Asignaciones de bienes indivisibles conscientes de Maximin". arXiv : 1905.09969 [cs.GT].
21. Amanatidis, Georgios; Ntokos, Apostolos; Markakis, Evangelos (2020). "Múltiples pájaros de un tiro: vencer a 1/2 para EFX y GMMS mediante la eliminación del ciclo de envidia". Ciencias de la Computación Teórica . 841 : 94–109. arXiv : 1909.07650 . doi :10.1016/j.tcs.2020.07.006. S2CID  222070124.
22. Caragiannis, Ioannis; Gravin, Nick; Huang, Xin (17 de junio de 2019). "Libre de envidia hasta cualquier artículo con alto bienestar de Nash: la virtud de donar artículos". Actas de la Conferencia ACM de 2019 sobre Economía y Computación . EC '19. Phoenix, AZ, EE. UU.: Association for Computing Machinery. págs. 527–545. arXiv : 1902.04319 . doi :10.1145/3328526.3329574. ISBN 978-1-4503-6792-9.S2CID60441171  .​
23. Chaudhury, Bhaskar Ray; Kavitha, Telikepalli ; Mehlhorn, Kurt; Sgouritsa, Alkmini (23 de diciembre de 2019), "Un poco de caridad garantiza que casi no habrá envidia", Actas del Simposio ACM-SIAM de 2020 sobre algoritmos discretos , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 2658–2672, arXiv : 1907.04596 , doi : 10.1137/1.9781611975994.162, ISBN 978-1-61197-599-4, S2CID  195874127 , consultado el 2 de octubre de 2020
24. Suksompong, Warut (30 de septiembre de 2020). "Sobre el número de asignaciones casi libres de envidia". Matemáticas Aplicadas Discretas . 284 : 606–610. arXiv : 2006.00178 . doi :10.1016/j.dam.2020.03.039. ISSN  0166-218X. S2CID  215715272.
25. Bei, Xiaohui; Li, Zihao; Liu, Jinyan; Liu, Shengxin; Lu, Xinhang (2021). "División justa de bienes mixtos divisibles e indivisibles". Inteligencia artificial . 293 : 103436. arXiv : 1911.07048 . doi :10.1016/j.artint.2020.103436. S2CID  231719223.
26. Aigner-Horev, Elad; Segal-Halevi, Erel (2022). "Emparejamientos sin envidia en grafos bipartitos y sus aplicaciones a la división justa". Ciencias de la información . 587 : 164–187. arXiv : 1901.09527 . doi :10.1016/j.ins.2021.11.059. S2CID  170079201.
27. Manurangsi, Pasin; Suksompong, Warut (8 de abril de 2021). "Cerrando brechas en la división justa asintótica". Revista SIAM de Matemáticas Discretas . 35 (2): 668–706. arXiv : 2004.05563 . doi :10.1137/20M1353381. S2CID  215744823.
28. John P. Dickerson; Jonathan Goldman; Jeremy Karp; Ariel D. Procaccia; Tuomas Sandholm (2014). El ascenso y la caída computacional de la imparcialidad . En Actas de la vigésimo octava conferencia de la AAAI sobre inteligencia artificial (2014). págs. 1405–1411. CiteSeerX 10.1.1.703.8413 . Enlace ACM
29. Manurangsi, Pasin; Suksompong, Warut (2 de julio de 2020). "¿Cuándo existen asignaciones libres de envidia?". Revista SIAM de Matemáticas Discretas . 34 (3): 1505–1521. arXiv : 1811.01630 . doi :10.1137/19M1279125. S2CID  220363902.