Asignación de artículos sin envidia

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

Dado que los elementos son indivisibles, es posible que no exista una asignación EF. El caso más simple es cuando hay un solo artículo y al menos dos agentes: si el artículo está asignado a un agente, el otro lo envidiará.

Una manera 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 varios tipos de flexibilizaciones.

Encontrar una asignación libre de envidia siempre que exista

Órdenes de preferencia en paquetes: sin envidia

El procedimiento de socavado encuentra una asignación EF completa para dos agentes, si y sólo si dicha asignación existe. Requiere que los agentes clasifiquen paquetes de artículos, pero no requiere información de utilidad fundamental. Funciona siempre que las relaciones de preferencia de los agentes son estrictamente monótonas, pero no es necesario asumir que son preferencias responsivas . En el peor de los casos, es posible que los agentes tengan que clasificar todos los paquetes posibles, por lo que el tiempo de ejecución podría ser exponencial en el número de artículos.

Ordenes de preferencia sobre artículos: necesaria/posible ausencia de envidia

Por lo general, es más fácil para las personas clasificar artículos individuales que clasificar paquetes. Suponiendo que todos los agentes tienen preferencias de respuesta , es posible elevar la clasificación de artículos a una clasificación de paquete parcial. Por ejemplo, si la clasificación del elemento 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} y {y,z}, etc. Dada una clasificación de elementos:

Una asignación es necesariamente libre de envidia (NEF) si está libre de envidia según todas las clasificaciones de paquetes receptivos consistentes con la clasificación de artículos;
Una asignación posiblemente esté libre de envidia (PEF) si para cada agente i hay al menos una clasificación de paquete responsivo consistente con la clasificación de elementos 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 responsivo consistente con la clasificación de ítems de i , por la cual i no envidia a j ;
Una asignación es necesariamente óptima de Pareto (NPE) si es óptima de Pareto según todas las clasificaciones de paquetes sensibles consistentes con la clasificación de elementos (consulte Eficiencia ordinal de Pareto );
Una asignación es posiblemente óptima de Pareto (PPE) si es óptima de acuerdo con al menos una clasificación de paquetes responsivos consistente con la clasificación de ítems.

Se conocen los siguientes resultados:

Bouveret, Endriss y Lang ^[2] suponen que todos los agentes tienen preferencias estrictas . Estudian las cuestiones algorítmicas para encontrar una asignación NEF/PEF con una condición de eficiencia adicional, en particular, integridad 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 realizar en tiempo polinomial.
Aziz, Gaspers, Mackenzie y Walsh ^[3] estudian el entorno más general en el que los agentes pueden tener preferencias débiles (con indiferencias). En este entorno, comprobar la existencia de WPEF es NP-completo. Decidir si existe una asignación del FPE se realiza en P para preferencias estrictas o para n=2, pero en general es NP-completo. Es una cuestión abierta si, cuando el número de agentes es constante, decidir la existencia de la asignación NEF está en P.

Utilidades cardinales

La asignación vacía es siempre 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 FE y una asignación completa es NP completo . Esto es cierto incluso cuando sólo hay dos agentes, e incluso cuando sus utilidades son aditivas e idénticas, ya que en este caso encontrar una asignación EF equivale a resolver el problema de partición . ^[4]
Decidir si existe una asignación justa 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 eficiente de EF y de Pareto 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). $\Sigma _{2}^{\textrm {P}}$ $\Sigma _{2}^{\textrm {P}}$

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

Considerando el número de objetos m como parámetro, se puede decidir en el 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 cae a . Aquí, la notación oculta expresiones que son polinomiales en los otros parámetros (por ejemplo, número de agentes). $O^{*}(m^{2m})$ $O^{*}(m^{m})$ $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 tales 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 respecto al número de agentes incluso si todas las utilidades son idénticas y están codificadas en unario. $n\geq 5$ $2^{n+1}$ $2^{n-4}$
Considerando tanto el número de agentes n como la mayor utilidad V como parámetros, se puede decidir a tiempo la existencia de una asignación PE+EF para utilidades aditivas utilizando programación dinámica . $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 este tipo de ILP a tiempo $d=n\cdot z^{n}$ $O^{*}(d^{2.5d})$

Encontrar una asignación con un nivel limitado de envidia

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

EF1: sin envidia hasta un máximo de un artículo

Una asignación se llama EF1 si por cada dos agentes A y B, si eliminamos como máximo un elemento del paquete 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. , particularmente:

Cuando todos los agentes tienen utilidades débilmente aditivas , el protocolo de operación por turnos encuentra una asignación EF1 completa. Se requiere una aditividad débil ya que cada agente debería poder elegir, en cada situación, el "mejor elemento".
En el caso más general, cuando todos los agentes tienen utilidades crecientes monótonamente, el procedimiento del gráfico de envidia encuentra una asignación EF1 completa. El único requisito es que los agentes puedan clasificar paquetes 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 de envidia numérico de cada agente es como máximo la utilidad marginal máxima: la utilidad marginal más grande de un solo elemento 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 paquetes de artículos. Es posible que una pequeña cantidad de elementos queden sin asignar y que sea necesario agregar una pequeña cantidad de elementos. La asignación es Pareto-eficiente 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 artículo y supone que las utilidades de los agentes son aditivas. La asignación resultante es tanto EF1 como Pareto-eficiente . ^[10]
Varios otros algoritmos devuelven asignaciones EF1 que también son eficientes en el sentido de Pareto; consulte Asignación de artículos eficiente y aproximadamente justa .
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ítmicas en el número de artículos. ^[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 como máximo 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 artículos se reservan por adelantado en una línea, como 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 casi cualquier artículo

Una asignación se llama 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 artículo más valioso (para A) del paquete 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 óptima de leximina es EFx y óptima de Pareto. Sin embargo, requiere un número exponencial de 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 máximo de Nash es EFx. Además, existe un algoritmo eficiente para calcular una asignación EFx (aunque no necesariamente el bienestar máximo de Nash). ^[16]
Cuando hay n agentes con valoraciones aditivas , pero hay como máximo dos tipos diferentes de valoraciones. ^[17]
Cuando existen 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 polinómico. ^[20]
En tiempo polinomial 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 maximina grupal y participación maximina por pares^{). [21]}
Siempre existe una asignación EFx parcial , donde el bienestar de Nash es al menos la mitad del bienestar de Nash máximo 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 forma EFx. Este límite es el mejor posible. En mercados grandes, donde las valoraciones de un agente para cada artículo son relativamente pequeñas, el algoritmo logra 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]

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

A diferencia de EF1, que requiere un número de consultas logarítmicas en el número de artículos, calcular una asignación EFx puede requerir un número lineal de consultas incluso cuando hay dos agentes con valoraciones aditivas idénticas. ^[11]

Otra diferencia entre EF1 y EFx es que el número de asignaciones EFX puede ser tan solo 2 (para cualquier número de elementos), mientras que el número de asignaciones EF1 siempre es exponencial en el número de elementos. ^[24]

EFm: aproximadamente libre de envidia para una mezcla de elementos divisibles e indivisibles

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

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

Existe una asignación EFm para cualquier número de agentes. Sin embargo, encontrarlo requiere un oráculo para la división exacta de un pastel. Sin este oráculo, una asignación EFm se puede calcular 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 el óptimo de Pareto, EFm puede ser incompatible con él.

Minimizando la envidia

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

Encontrar una asignación parcial del EF

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

El procedimiento de ganador ajustado devuelve una asignación EF completa y eficiente para dos agentes, pero es posible que tenga que eliminar un solo artículo (alternativamente, un artículo 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 único artículo, y las valoraciones son binarias (a cada agente le gusta o no le gusta cada artículo), existe un algoritmo de tiempo polinómico que encuentra una coincidencia libre de envidia de cardinalidad máxima. ^[26]

Existencia de asignaciones de FA con valoraciones aleatorias

Si los agentes tienen funciones de utilidad aditivas que se extraen de distribuciones de probabilidad que satisfacen algunos 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 EF con alta probabilidad . Particularmente:

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

Por otro lado, si el número de ítems no es suficientemente grande, entonces, con alta probabilidad, no existe una asignación del FA.

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

Libre de envidia versus otros criterios de equidad

Cada asignación de EF es min-max-fair . Esto se deriva 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 EF también es proporcional y máxima-mín-equitativa . De lo contrario, una asignación del EF puede no ser proporcional e incluso no ser justa entre el máximo y el mínimo.
Cualquier 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]
Cada asignación óptima de Nash (asignación que maximiza el producto de las utilidades) es EF1. ^[14]
La libertad de envidia grupal es un fortalecimiento de la libertad de envidia, que es aplicable tanto a objetos divisibles como a indivisibles.

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

tabla resumen

A continuación, se utilizan las siguientes abreviaturas:

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

Referencias

^ ab Brandt, Félix; Conitzer, Vicente; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Manual de elección social computacional. Prensa de la Universidad de Cambridge. ISBN 9781107060432.(versión gratuita en línea)
^ Bouveret, Sylvain; Endriss, Ulle; Lang, Jérôme (4 de agosto de 2010). "División justa según preferencias ordinales: cálculo de asignaciones de bienes indivisibles sin envidia". Actas de la Conferencia de 2010 sobre ECAI 2010: XIX Conferencia Europea sobre Inteligencia Artificial . NLD: IOS Press: 387–392. ISBN 978-1-60750-605-8.
^ Aziz, Haris; Gaspers, Serge; Mackenzie, Simón; Walsh, Toby (1 de octubre de 2015). "Asignación justa de objetos indivisibles según preferencias ordinales". Inteligencia artificial . 227 : 71–92. arXiv : 1312.6546 . doi : 10.1016/j.artint.2015.06.002 . ISSN 0004-3702. S2CID 1408197.
^ 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.
^ Plaut, Benjamín; Roughgarden, Tim (1 de enero de 2020). "Complejidad de la comunicación de la división justa discreta". Revista SIAM de Computación . 49 (1): 206–243. arXiv : 1711.04066 . doi :10.1137/19M1244305. ISSN 0097-5397. S2CID 212667868.
^ abc 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 .
^ De Keijzer, Bart; Bouveret, Sylvain; Klos, Tomás; 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 conferencias sobre informática. vol. 5783. pág. 98.doi :10.1007/978-3-642-04428-1_9 . ISBN 978-3-642-04427-4.
^ Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf (9 de julio de 2016). "Complejidad de la asignación de recursos eficiente y sin envidia: pocos agentes, recursos o niveles de utilidad". Actas de la Vigésima Quinta Conferencia Internacional Conjunta sobre Inteligencia Artificial . IJCAI'16. Nueva York, Nueva York, Estados Unidos: AAAI Press: 102–108. ISBN 978-1-57735-770-4.
^ ab Budish, Eric (2011). "El problema de la 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.
^ Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). La imparcialidad irrazonable del máximo bienestar de Nash (PDF) . Actas de la Conferencia ACM sobre Economía y Computación de 2016 - EC '16. pag. 305. doi : 10.1145/2940716.2940726. ISBN 9781450339360.
^ ab Oh, Hoon; Procaccia, Ariel D.; Suksompong, Warut (17 de julio de 2019). "Asignación justa de muchos productos 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.
^ ab 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].
^ 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.
^ abc Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). La imparcialidad irrazonable del máximo bienestar de Nash (PDF) . Actas de la Conferencia ACM sobre Economía y Computación de 2016 - EC '16. pag. 305. doi : 10.1145/2940716.2940726. ISBN 9781450339360.
^ Plaut, Benjamín; Roughgarden, Tim (1 de enero de 2020). "Casi libre de envidia con valoraciones generales". Revista SIAM de Matemática Discreta . 34 (2): 1039–1068. arXiv : 1707.04769 . doi :10.1137/19M124397X. ISSN 0895-4801. S2CID 216283014.
^ Amanatidis, Georgios; Birmpas, Georgios; Filos-Ratsikas, Aris; Hollender, Alexandros; Voudouris, Alexandros A. (2021). "Máximo bienestar de Nash y otras historias sobre EFX". Informática Teórica . 863 : 69–85. arXiv : 2001.09838 . doi :10.1016/j.tcs.2021.02.020. S2CID 210920309.
^ Mahara, Ryoga (20 de agosto de 2020). "Existencia de EFX para dos valoraciones aditivas". arXiv : 2008.08798 [cs.GT].
^ Chaudhury, Bhaskar Ray; Garg, yugal; Mehlhorn, Kurt (30 de mayo de 2020). "EFX existe para tres agentes". arXiv : 2002.05119 [cs.GT].
^ {{citar arXiv:2205.07638 [cs.GT]}}
^ 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].
^ Amanatidis, Georgios; Ntokos, Apóstolos; Markakis, Evangelos (2020). "Varios pájaros de un tiro: vencer a 1/2 para EFX y GMMS mediante la eliminación del ciclo de envidia". Informática Teórica . 841 : 94-109. arXiv : 1909.07650 . doi : 10.1016/j.tcs.2020.07.006. S2CID 222070124.
^ 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 . CE '19. Phoenix, AZ, EE.UU.: Asociación de Maquinaria de Computación. págs. 527–545. arXiv : 1902.04319 . doi :10.1145/3328526.3329574. ISBN 978-1-4503-6792-9. S2CID 60441171.
^ Chaudhury, Bhaskar Ray; Kavitha, Telikepalli ; Mehlhorn, Kurt; Sgouritsa, Alkmini (23 de diciembre de 2019), "Un poco de caridad garantiza casi la ausencia de envidia", Actas del Simposio ACM-SIAM de 2020 sobre algoritmos discretos , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. : 1907.04596 , doi :10.1137/1.9781611975994.162, ISBN 978-1-61197-599-4, S2CID 195874127 , consultado el 2 de octubre de 2020
^ Suksompong, Warut (30 de septiembre de 2020). "Sobre el número de asignaciones casi libres de envidia". Matemática Aplicada Discreta . 284 : 606–610. arXiv : 2006.00178 . doi : 10.1016/j.dam.2020.03.039. ISSN 0166-218X. S2CID 215715272.
^ Bei, Xiaohui; Li, Zihao; Liu, Jinyan; Liu, Shengxin; Lu, Xinhang (2021). "División equitativa de bienes mixtos divisibles e indivisibles". Inteligencia artificial . 293 : 103436. arXiv : 1911.07048 . doi :10.1016/j.artint.2020.103436. S2CID 231719223.
^ Aigner-Horev, Elad; Segal-Halevi, Erel (2022). "Emparejamientos sin envidia en gráficos 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.
^ Manurangsi, Pasin; Suksompong, Warut (8 de abril de 2021). "Cerrar brechas en la división justa asintótica". Revista SIAM de Matemática Discreta . 35 (2): 668–706. arXiv : 2004.05563 . doi :10.1137/20M1353381. S2CID 215744823.
^ ab John P. Dickerson; Jonathan Goldman; Jérémy Karp; Ariel D. Procaccia; Tuomas Sandholm (2014). El ascenso y la caída computacional de la equidad . En Actas de la Vigésima Octava Conferencia AAAI sobre Inteligencia Artificial (2014). págs. 1405-1411. CiteSeerX 10.1.1.703.8413 . enlace ACM
^ ab Manurangsi, Pasin; Suksompong, Warut (2 de julio de 2020). "¿Cuándo existen las asignaciones libres de envidia?". Revista SIAM de Matemática Discreta . 34 (3): 1505-1521. arXiv : 1811.01630 . doi :10.1137/19M1279125. S2CID 220363902.