Asignación igualitaria de artículos

Problema de asignación justa de artículos

La asignación igualitaria de ítems , también llamada asignación máxima-mínima de ítems, es un problema de asignación justa de ítems , en el que el criterio de equidad sigue la regla igualitaria . El objetivo es maximizar el valor mínimo de un agente. Es decir, entre todas las asignaciones posibles, el objetivo es encontrar una asignación en la que el valor más pequeño de un agente sea lo más grande posible. En caso de que haya dos o más asignaciones con el mismo valor más pequeño, entonces el objetivo es seleccionar, de entre estas asignaciones, aquella en la que el segundo valor más pequeño sea lo más grande posible, y así sucesivamente (por orden leximin ). . Por lo tanto, una asignación igualitaria de ítems a veces se denomina asignación de ítems leximin .

El caso especial en el que el valor de cada elemento j para cada agente es 0 o alguna constante v _j se denomina problema de Papá Noel : Papá Noel tiene un conjunto fijo de regalos y quiere distribuirlos entre los niños de modo que el menor- El niño feliz es lo más feliz posible.

Algunos problemas relacionados son:

• La partición de números multivía con el objetivo máximo-mínimo corresponde a un caso especial en el que todos los agentes tienen las mismas valoraciones. Un caso aún más especial es el problema de la partición , que corresponde al caso de dos agentes. Incluso este caso especial es NP-difícil en general.
• La programación de máquinas no relacionadas es un problema dual, en el que el objetivo es minimizar el valor máximo .
• La asignación de elementos de acciones de Maximin es un problema diferente, en el que el objetivo no es alcanzar una solución óptima, sino encontrar cualquier solución en la que cada agente reciba un valor por encima de un cierto umbral.

Normalización

Hay dos variantes de la regla igualitaria: ^[1]

• igualitario absoluto (o leximin absoluto ), donde la maximización utiliza los valores nominales de los agentes;
• igualitario relativo (o leximin relativo ) donde la maximización utiliza sus valores normalizados: valor del paquete dividido por el valor de todos los elementos.

Las dos reglas son equivalentes cuando las valoraciones de los agentes ya están normalizadas, es decir, todos los agentes asignan el mismo valor al conjunto de todos los ítems. Sin embargo, pueden diferir de las valoraciones no normalizadas. Por ejemplo, si hay cuatro elementos, Alice los valora en 1,1,1,1 y George los valora en 3,3,3,3, entonces la regla leximin absoluta le daría tres elementos a Alice y un elemento a George. , ya que el perfil de utilidad en este caso es (3,3), que es óptimo. En contraste, la regla del leximin relativo daría dos ítems a cada agente, ya que el perfil de utilidad normalizado en este caso, cuando el valor total de ambos agentes se normaliza a 1, es (0.5,0.5), que es óptimo.

Algoritmos exactos

Aunque el problema general es NP-difícil, los casos pequeños pueden resolverse exactamente mediante técnicas de programación de restricciones .

• Bouveret y Lemaître presentan cinco algoritmos diferentes para encontrar soluciones óptimas de leximina a problemas discretos de satisfacción de restricciones. ^[2] Presentan la asignación de artículos máximo-mínimo como un caso especial.
• Dall'Aglio y Mosca ^[3] proporcionaron un algoritmo exacto de ramificación y enlace para dos agentes, basado en una adaptación del procedimiento ganador ajustado .

Algoritmos aleatorios

Demko y Hill ^[4] presentan un algoritmo aleatorio que logra una asignación igualitaria de ítems según las expectativas.

Algoritmos de aproximación

A continuación, n es el número de agentes y m es el número de artículos.

Para el caso especial del problema de Papá Noel:

• Bansal y Sviridenko ^[5] dieron un algoritmo de aproximación, basado en el redondeo de un programa lineal . ${\displaystyle O(\log {\log {n}}/\log {\log {\log {n}}})}$
• Feige ^[6] demostró que existe un algoritmo de aproximación de factor constante de tiempo polinomial, pero la prueba utilizó el lema local de Lovász y no fue constructiva.
• Asadpour, Feige y Saberi ^[7] dieron un algoritmo de aproximación de factor constante real, utilizando coincidencia de hipergrafos . No pudieron demostrar que converge en un número finito de pasos.
• Annamalai, Kalaitzis y Svensson ^[8] dieron un algoritmo de 13 aproximaciones en tiempo polinomial.
• Davies, Rothvoss y Zhang ^[9] mejoraron el factor de aproximación a 4 introduciendo restricciones matroides al programa lineal básico .

Para el caso general, para agentes con valoraciones aditivas :

• Bezakova y Dani ^[10] presentaron dos algoritmos. El primero da una aproximación factorial al valor igualitario óptimo. El segundo encuentra una asignación que es igualitaria hasta un bien, es decir, cada agente recibe su valor en la asignación igualitaria óptima menos un solo elemento como máximo. Su algoritmo se basa en un algoritmo anterior de Lenstra, Shmoys y Tardos, ^[11] que esencialmente encuentra una asignación igualitaria hasta una tarea . Ambos algoritmos se basan en una idea similar. Encuentran una solución básica factible del programa lineal para encontrar una asignación igualitaria fraccionaria y la redondean de modo que cada agente pierda como máximo un bien o gane como máximo una tarea. ${\displaystyle (m-n+1)}$
• Asadpour y Saberi ^[12] dieron un algoritmo de aproximación. Su algoritmo utiliza un método iterativo para redondear una coincidencia fraccionaria en un árbol . También proporcionan mejores límites cuando se permite excluir del problema a una pequeña fracción de personas. ${\displaystyle O({\sqrt {n}}\cdot \log ^{3}n)}$

• Chakrabarty, Chuzoy y Khanna ^[13] dieron un algoritmo de aproximación con un tiempo de ejecución de , para cualquier . Para el caso especial en el que cada elemento tiene una utilidad distinta de cero para como máximo dos agentes, dieron un algoritmo de aproximación de 2 factores y demostraron que es difícil aproximarse a un factor mejor. ${\displaystyle O(m^{\varepsilon })}$ ${\displaystyle O(m^{1/\varepsilon })}$ ${\displaystyle \varepsilon \in \Omega \left({\frac {\log \log m}{\log m}}\right)}$
• Golovin ^[14] dio un algoritmo mediante el cual, por cada número entero , una fracción de los agentes recibe al menos utilidad . Este resultado se obtiene redondeando una relajación de programación lineal adecuada del problema y es el mejor resultado posible para este programa lineal. También dio un algoritmo de aproximación para el caso especial con dos clases de bienes. ${\displaystyle k}$ ${\displaystyle (1-1/k)}$ ${\displaystyle OPT/k}$ ${\displaystyle O({\sqrt {n}})}$
• Cuando el número de agentes es constante se tiene un FPTAS utilizando la técnica de Woeginger . ^[15]

Para agentes con funciones de utilidad submodulares :

• Golovin ^[14] proporcionó un algoritmo de aproximación y algunos resultados de inaproximabilidad para funciones de utilidad generales. ${\displaystyle (m-n+1)}$
• Goemans, Harvey, Iwata y Mirrkoni ^[16] dan un algoritmo de aproximación ${\displaystyle O({\sqrt {m}}\cdot n^{1/4}\cdot \log n\cdot \log ^{3/2}m)}$
• Nguyen, Roos y Rothe ^{[17] [18]} presentan algunos resultados de dureza más fuertes.

Asignaciones ordinariamente igualitarias

La regla igualitaria estándar requiere que cada agente asigne un valor numérico a cada objeto. A menudo, los agentes sólo tienen utilidades ordinales . Hay dos generalizaciones de la regla igualitaria a entornos ordinales.

1. Supongamos que los agentes tienen una clasificación ordinal sobre el conjunto de paquetes . Dada cualquier asignación discreta, para cualquier agente i , defina r ( i ) como el rango del paquete del agente i, de modo que r(i)=1 si obtuve su mejor paquete, r(i)=2 si obtuve su segundo- mejor paquete, etc. Este r es un vector de tamaño n (el número de agentes). Una asignación ordinalmente igualitaria es aquella que minimiza el elemento más grande en r. El procedimiento de demanda decreciente encuentra una asignación ordinalmente igualitaria para cualquier número de agentes con cualquier orden de paquetes.

2. Supongamos que los agentes tienen una clasificación ordinal sobre el conjunto de elementos . Dada cualquier asignación discreta o fraccionaria, para cualquier agente i y un entero positivo k , defina t ( i , k ) como la fracción total que el agente i recibe de sus k clases de indiferencia más altas. Este t es un vector de tamaño como máximo n * m , donde n es el número de agentes y m es el número de elementos. Una asignación ordinalmente igualitaria es aquella que maximiza el vector t en el orden leximin. El algoritmo de alimentación simultánea con velocidades de alimentación iguales es la única regla que devuelve una asignación ordinalmente igualitaria. ^[19]

Comparación con otros criterios de equidad

Proporcionalidad

Siempre que existe una asignación proporcional, la asignación leximin relativa es proporcional. Esto se debe a que, en una asignación proporcional, el valor relativo más pequeño de un agente es al menos 1/ n , por lo que lo mismo debe cumplirse cuando maximizamos el valor relativo más pequeño. Sin embargo, la asignación de leximina absoluta podría no ser proporcional, como se muestra en el ejemplo anterior.

Libre de envidia

1. Cuando todos los agentes tienen valoraciones idénticas con utilidades marginales distintas de cero, cualquier asignación leximin relativa es PO y EFX .

• Una mejora de leximin llamada leximin++ garantiza EFX (pero no PO) con valoraciones generales idénticas. ^[20]

2. Para dos agentes con valoraciones aditivas, cualquier asignación relativa de leximina es EF1. ^{[20] : Thm.5.5} Sin embargo:

• La asignación de leximina absoluta podría no ser EF1 incluso para dos agentes con valoraciones aditivas. Por ejemplo, supongamos que hay cuatro bienes y dos agentes que los valoran en {0,1,1,1} y {3,3,3,3}. La asignación única de leximina absoluta le da {1,1,1} al primer agente y {3} al segundo agente, pero luego el segundo agente envidia. ^{[21] : 32}
• La asignación relativa de leximina podría no ser EF1 para tres o más agentes. Por ejemplo, supongamos que hay cuatro bienes y tres agentes que los valoran en {30,0,0,0} {20,5,5,0} y {0,12,12,6}. Tenga en cuenta que las valoraciones están normalizadas (el valor total es 30). En una asignación leximin, el primer bien debe asignarse al agente 1. Luego, el segundo y tercer bien deben asignarse al agente 2, y el bien permanece para el agente 3. Pero entonces el agente 3 envidia al agente 2 incluso después de eliminar un artículo. ^{[22] : 22}

3. Cuando todos los agentes tienen valoraciones que son funciones de rango matroide (es decir, submodulares con marginales binarias), el conjunto de asignaciones de leximina absoluta es equivalente al conjunto de asignaciones de producto máximo; Todas estas asignaciones son de suma máxima y EF1. ^[21]

4. En el contexto de la asignación indivisible de tareas (elementos con utilidades negativas), con 3 o 4 agentes con valoraciones aditivas, cualquier asignación óptima de leximin es PROP1 y PO; con n agentes con valoraciones generales idénticas, cualquier asignación óptima de leximin es EFX. ^[23]

participación maximin

Cuando todos los agentes tienen valoraciones idénticas, la asignación igualitaria, por definición, le da a cada agente al menos su participación máxima.

Sin embargo, cuando los agentes tienen valoraciones diferentes, los problemas son diferentes. La asignación de acciones maximin es un problema de satisfacción: el objetivo es garantizar que cada agente reciba un valor por encima del umbral de valoraciones idénticas. Por el contrario, la asignación igualitaria es un problema de optimización: el objetivo es dar a cada agente el mayor valor posible. En algunos casos, las asignaciones resultantes pueden ser muy diferentes. Por ejemplo, supongamos que hay cuatro bienes y tres agentes que los valoran en {3,0,0,0}, {3-2 ε,ε,ε ,0} y {1-2 ε ,1,1,2 ε } (donde ε es una pequeña constante positiva). Tenga en cuenta que las valoraciones están normalizadas (el valor total es 3), por lo que la leximina absoluta y la leximina relativa son equivalentes.

• La asignación de leximin produce el perfil de utilidad (3, 2ε, 2ε ): el primer elemento debe ir al agente 1; de lo contrario, la utilidad más pequeña es 0. Luego, el segundo y tercer elemento deben ir al agente 2; de lo contrario, la siguiente utilidad más pequeña es ε o menos; entonces el agente 3 obtiene solo el último elemento.
• Los valores de participación maximina de los agentes son 0, ε , 1. Por lo tanto, una asignación de participación máxima debe darle al agente 3 uno de los primeros tres elementos; algunos perfiles de utilidad posibles en este caso son (0, 2ε , 1) o (3, ε , 1+ 2ε ).

El ejemplo se puede ampliar a 1 de k MMS para cualquier k >3. Hay k +1 bienes y tres agentes que los valoran en { k , 0, ..., 0}, { k -( k -1) ε , ε, ..., ε , 0} y {1- kε , 1, 1, ..., k ε }. El perfil de utilidad de leximin debe ser ( k , kε, kε ) mientras que el MMS 1 de k del agente 3 es 1.

Aplicación en el mundo real

La regla leximin se ha utilizado para asignar de manera justa las aulas no utilizadas en las escuelas públicas a las escuelas autónomas. ^[24]

Referencias

1. Segal-Halevi, Erel; Sziklai, Balázs R. (1 de septiembre de 2019). "Monotonicidad y equilibrio competitivo en el corte de tartas". Teoría económica . 68 (2): 363–401. arXiv : 1510.05229 . doi :10.1007/s00199-018-1128-6. ISSN  1432-0479. S2CID  179618.
2. Bouveret, Sylvain; Lemaître, Michel (1 de febrero de 2009). "Cálculo de soluciones óptimas de leximin en redes con restricciones". Inteligencia artificial . 173 (2): 343–364. doi : 10.1016/j.artint.2008.10.010 . ISSN  0004-3702.
3. Dall'Aglio, Marco; Mosca, Raffaele (2007). "Cómo asignar los caramelos duros de manera justa". Ciencias Sociales Matemáticas . 54 (3): 218. CiteSeerX 10.1.1.330.2617 . doi : 10.1016/j.mathsocsci.2007.04.008. 
4. Demko, Stephen; Colina, Theodore P. (1 de octubre de 1988). "Reparto equitativo de objetos indivisibles". Ciencias Sociales Matemáticas . 16 (2): 145-158. doi :10.1016/0165-4896(88)90047-9. ISSN  0165-4896.
5. Bansal, Nikhil; Sviridenko, Maxim (2006). "El problema de Papá Noel". Actas del trigésimo octavo simposio anual de ACM sobre teoría de la informática - STOC '06 . pag. 31. doi :10.1145/1132516.1132522. ISBN 1595931341.
6. Feige, Uriel (20 de enero de 2008). "Sobre asignaciones que maximicen la equidad". Actas del decimonoveno simposio anual ACM-SIAM sobre algoritmos discretos . Refresco '08. San Francisco, California: Sociedad de Matemáticas Industriales y Aplicadas: 287–293.
7. Asadpour, Arash; Feige, Uriel; Saberi, Amin (2008). "Papá Noel se encuentra con las coincidencias de Hypergraph". En Goel, Ashish; Jansen, Klaus; Rolim, José DP; Rubinfeld, Ronitt (eds.). Aproximación, Aleatorización y Optimización Combinatoria. Algoritmos y Técnicas . Apuntes de conferencias sobre informática. vol. 5171. Berlín, Heidelberg: Springer. págs. 10-20. doi :10.1007/978-3-540-85363-3_2. ISBN 978-3-540-85363-3.
8. Annamalai, Chidambaram; Kalaitzis, Christos; Svensson, Ola (26 de mayo de 2017). "Algoritmo combinatorio para la asignación justa máxima-mínima restringida". Transacciones ACM sobre algoritmos . 13 (3): 37:1–37:28. arXiv : 1409.0607 . doi :10.1145/3070694. ISSN  1549-6325. S2CID  14749011.
9. Davies, Sami; Rothvoss, Thomas; Zhang, Yihao (18 de julio de 2018). Un cuento de Papá Noel, hipergrafos y matroides . Actas del decimocuarto simposio anual ACM-SIAM sobre algoritmos discretos. Sociedad de Matemáticas Industriales y Aplicadas, 2020. págs. doi :10.1137/1.9781611975994.
10. Bezáková, Ivona; Dani, Varsha (2005). "Asignación de bienes indivisibles". Intercambios ACM SIGecom . 5 (3): 11. CiteSeerX 10.1.1.436.18 . doi :10.1145/1120680.1120683. S2CID  1176760. 
11. Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1 de enero de 1990). "Algoritmos de aproximación para programar máquinas paralelas no relacionadas". Programación Matemática . 46 (1): 259–271. doi :10.1007/BF01585745. ISSN  1436-4646. S2CID  52867171.
12. Asadpour, Arash; Saberi, Amin (1 de enero de 2010). "Un algoritmo de aproximación para la asignación justa máxima-mínima de bienes indivisibles". Revista SIAM de Computación . 39 (7): 2970–2989. doi : 10.1137/080723491. ISSN  0097-5397.
13. Chakrabarty, D.; Chuzhoy, J.; Khanna, S. (1 de octubre de 2009). "Sobre la asignación de bienes para maximizar la equidad". 2009 50º Simposio Anual del IEEE sobre Fundamentos de la Informática . págs. 107-116. arXiv : 0901.0205 . doi :10.1109/FOCS.2009.51. ISBN 978-1-4244-5116-6. S2CID  165160.
14. Golovin, Daniel (2005). "Asignación justa máxima-mínima de bienes indivisibles". UMC . Consultado el 27 de agosto de 2016 .
15. Woeginger, Gerhard J. (1 de febrero de 2000). "¿Cuándo garantiza una formulación de programación dinámica la existencia de un esquema de aproximación de tiempo totalmente polinomial (FPTAS)?". Revista INFORMA de Informática . 12 (1): 57–74. doi :10.1287/ijoc.12.1.57.11901. ISSN  1091-9856.
16. Goemans, Michel X.; Harvey, Nicolás JA; Iwata, Satoru; Mirrokni, Vahab (4 de enero de 2009), "Aproximación de funciones submodulares en todas partes", Actas del Simposio anual ACM-SIAM de 2009 sobre algoritmos discretos , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 535–544, doi :10.1137/ 1.9781611973068.59, hdl : 1721.1/60671 , ISBN 978-0-89871-680-1, S2CID  14308006 , consultado el 22 de noviembre de 2020
17. Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "Una encuesta de resultados de aproximabilidad e inaproximabilidad para la optimización del bienestar social en la asignación de recursos multiagente". Anales de Matemáticas e Inteligencia Artificial . 68 (1–3): 65–90. CiteSeerX 10.1.1.671.3497 . doi :10.1007/s10472-012-9328-4. S2CID  6864410. 
18. Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "Complejidad computacional y proximidad de la optimización del bienestar social en la asignación de recursos multiagente". Agentes Autónomos y Sistemas Multiagente . 28 (2): 256. doi :10.1007/s10458-013-9224-2. S2CID  442666.
19. Bogomolnaia, Anna (1 de julio de 2015). "Asignación aleatoria: redefinición de la regla serial". Revista de teoría económica . 158 : 308–318. doi :10.1016/j.jet.2015.04.008. ISSN  0022-0531.
20. 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.
21. Benabbou, Nawal; Chakraborty, Mithun; Igarashi, Ayumi; Zick, Yair (2020). "Encontrar asignaciones justas y eficientes cuando las valoraciones no cuadran". Teoría algorítmica de juegos . Apuntes de conferencias sobre informática. vol. 12283, págs. 32–46. arXiv : 2003.07060 . doi :10.1007/978-3-030-57980-7_3. ISBN 978-3-030-57979-1. S2CID  208328700.
22. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (24 de septiembre de 2019). "La justicia irrazonable del máximo bienestar de Nash". Transacciones ACM sobre Economía y Computación . 7 (3): 12:1–12:32. doi : 10.1145/3355902 . ISSN  2167-8375. S2CID  202729326.
23. Chen, Xingyu; Liu, Zijie (11 de mayo de 2020). "La equidad de Leximin en la asignación de tareas indivisibles". arXiv : 2005.04864 [cs.GT].
24. Kurokawa, David; Procaccia, Ariel D.; Shah, Nisarg (15 de junio de 2015). "Asignaciones de Leximin en el mundo real". Actas de la Decimosexta Conferencia ACM sobre Economía y Computación . CE '15. Portland, Oregon, EE.UU.: Asociación de Maquinaria de Computación. págs. 345–362. doi :10.1145/2764468.2764490. ISBN 978-1-4503-3410-5. S2CID  1060279.