Asignación igualitaria de artículos

Problema de asignación justa de elementos

La asignación igualitaria de elementos , también llamada asignación máxima-mínima de elementos , es un problema de asignación justa de elementos , 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 el orden leximin ). Por lo tanto, una asignación igualitaria de elementos a veces se denomina asignación de elementos leximin .

El caso especial en el que el valor de cada artículo j para cada agente es 0 o una constante v _j se llama el problema de Santa Claus : Santa Claus tiene un conjunto fijo de regalos y quiere distribuirlos entre los niños de modo que el niño menos feliz sea lo más feliz posible.

Algunos problemas relacionados son:

• La partición de números multidireccional 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 partición , que corresponde al caso de dos agentes. Incluso este caso especial es NP-hard 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 con máxima participación es un problema diferente, en el que el objetivo no es alcanzar una solución óptima, sino más bien encontrar una solución en la que cada agente reciba un valor por encima de un cierto umbral.

Normalización

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

• igualitarismo 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: el valor del paquete dividido por el valor de todos los artículos.

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 elementos. Sin embargo, pueden diferir con 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 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 cambio, la regla leximin relativa daría dos elementos a cada agente, ya que el perfil de utilidad normalizado en este caso, cuando el valor total de ambos agentes está normalizado a 1, es (0,5,0,5), que es óptimo.

Algoritmos exactos

Aunque el problema general es NP-hard, las instancias pequeñas se pueden resolver con exactitud mediante técnicas de programación de restricciones .

• Bouveret y Lemaître presentan cinco algoritmos diferentes para encontrar soluciones leximin -óptimas a problemas de satisfacción de restricciones discretas. ^[2] Presentan la asignación máxima-mínima de elementos como un caso especial.
• Dall'Aglio y Mosca ^[3] proporcionaron un algoritmo exacto de ramificación y acotación 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 de ítems igualitaria en expectativa.

Algoritmos de aproximación

A continuación, n es el número de agentes y m es el número de elementos.

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 la 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 al introducir restricciones matroidales en el 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 como máximo un solo artículo. Su algoritmo se basa en un algoritmo previo de Lenstra, Shmoys y Tardos ^[11] , que esencialmente encuentra una asignación que es igualitaria hasta una tarea . Ambos algoritmos se basan en una idea similar. Encuentran una solución factible básica 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] desarrollaron un algoritmo de aproximación. Su algoritmo utiliza un método iterativo para redondear una coincidencia fraccionaria en un árbol . También brindan mejores límites cuando se permite excluir una pequeña fracción de personas del problema. ${\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 dos agentes como máximo, 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] propuso un algoritmo por el cual, por cada entero , una fracción de los agentes recibe una utilidad de al menos . 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 propuso 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 existe 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 ordinalmente igualitarias

La regla igualitaria estándar requiere que cada agente asigne un valor numérico a cada objeto. A menudo, los agentes solo tienen utilidades ordinales . Existen dos generalizaciones de la regla igualitaria para 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 i obtuvo su mejor paquete, r(i)=2 si i obtuvo 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 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 exista una asignación proporcional, la asignación relativa-leximin será 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 suceder cuando maximizamos el valor relativo más pequeño. Sin embargo, la asignación absoluta-leximin 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 a leximin es EF1. ^{[20] : Teoría 5.5} Sin embargo:

• La asignación absoluta-leximin 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 absoluta-leximin única otorga {1,1,1} al primer agente y {3} al segundo agente, pero luego el segundo agente envidia. ^{[21] : 32}
• La asignación relativa-leximin 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}. Nótese 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 el 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 leximin absoluto es equivalente al conjunto de asignaciones de máximo producto; todas esas asignaciones son de máxima suma y EF1. ^[21]

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

Maximizar la cuota

Cuando todos los agentes tienen valoraciones idénticas, la asignación igualitaria, por definición, otorga a cada agente al menos su parte maximin.

Sin embargo, cuando los agentes tienen valoraciones diferentes, los problemas son diferentes. La asignación maximin-share es un problema de satisfacción: el objetivo es garantizar que cada agente reciba un valor por encima del umbral de valoraciones idénticas. En contraste, la asignación igualitaria es un problema de optimización: el objetivo es dar a cada agente el valor más alto 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 constante positiva pequeña). Nótese que las valoraciones están normalizadas (el valor total es 3), por lo que el leximin absoluto y el leximin relativo son equivalentes.

• La asignación leximin produce el perfil de utilidad (3, 2ε, 2ε ): el primer artículo debe ir al agente 1; de lo contrario, la utilidad más pequeña es 0. Luego, el segundo y tercer artículo deben ir al agente 2; de lo contrario, la siguiente utilidad más pequeña es ε o menor; por lo que el agente 3 solo obtiene el último artículo.
• Los valores de participación máxima de los agentes son 0, ε , 1. Por lo tanto, una asignación de participación máxima debe dar 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 extender 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 leximin debe ser ( k , kε, kε ) mientras que el 1-de- k MMS 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 concertadas. ^[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; Hill, Theodore P. (1988-10-01). "Distribución equitativa 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 Santa Claus". Actas del trigésimo octavo simposio anual de la ACM sobre teoría de la computación - STOC '06 . p. 31. doi :10.1145/1132516.1132522. ISBN 1595931341.
6. Feige, Uriel (20 de enero de 2008). "Sobre asignaciones que maximizan la equidad". Actas del decimonoveno simposio anual ACM-SIAM sobre algoritmos discretos . SODA '08. San Francisco, California: Society for Industrial and Applied Mathematics: 287–293.
7. Asadpour, Arash; Feige, Uriel; Saberi, Amin (2008). "Santa Claus Meets Hypergraph Matchings". 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 clase en 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 asignación justa máxima-mínima restringida". ACM Transactions on Algorithms . 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. 2748–2757. doi :10.1137/1.9781611975994.
10. Bezáková, Ivona; Dani, Varsha (2005). "Asignación de bienes indivisibles". ACM SIGecom Exchanges . 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 (1990-01-01). "Algoritmos de aproximación para la planificación de 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 de máximos y mínimos de bienes indivisibles". Revista SIAM de informática . 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 IEEE sobre fundamentos de la informática . pp. 107–116. arXiv : 0901.0205 . doi :10.1109/FOCS.2009.51. ISBN. 978-1-4244-5116-6.S2CID 165160  .
14. Golovin, Daniel (2005). "Max-min fair mapping of indivisible goods" (Asignación justa máxima-mínima de bienes indivisibles). CMU . 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 temporal completamente polinomial (FPTAS)?". INFORMS Journal on Computing . 12 (1): 57–74. doi :10.1287/ijoc.12.1.57.11901. ISSN  1091-9856.
16. Goemans, Michel X.; Harvey, Nicholas 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). "Un estudio de los 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 aproximabilidad 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: redefiniendo 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, 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.
21. Benabbou, Nawal; Chakraborty, Mithun; Igarashi, Ayumi; Zick, Yair (2020). "Encontrar asignaciones justas y eficientes cuando las valoraciones no cuadran". Teoría de juegos algorítmicos . Apuntes de clase en 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. Número de identificación del sujeto  208328700.
22. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (24 de septiembre de 2019). "La justicia irrazonable del bienestar máximo de Nash". ACM Transactions on Economics and Computation . 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 de la ACM sobre economía y computación . EC '15. Portland, Oregón, EE. UU.: Association for Computing Machinery. págs. 345–362. doi :10.1145/2764468.2764490. ISBN 978-1-4503-3410-5.S2CID1060279  .​