División justa entre grupos

La división justa entre grupos ^[1] (o familias ^[2] ) es una clase de problemas de división justa , en los que los recursos se asignan entre grupos de agentes, en lugar de entre agentes individuales. Después de la división, todos los miembros de cada grupo consumen la misma parte, pero pueden tener diferentes preferencias; por lo tanto, diferentes miembros del mismo grupo pueden estar en desacuerdo sobre si la asignación es justa o no. Algunos ejemplos de configuraciones de división justa entre grupos son:

• Varios hermanos han heredado algunas casas de sus padres y tienen que repartirlas. Cada hermano tiene una familia, cuyos miembros pueden tener diferentes opiniones sobre qué casa es mejor.
• Se disuelve una sociedad y sus bienes deben dividirse entre los socios. Los socios son empresas; cada empresa tiene varios accionistas, que pueden estar en desacuerdo sobre qué activo es más importante.
• La dirección de la universidad quiere repartir algunas salas de reuniones entre sus departamentos. En cada departamento hay varios profesores, con opiniones diferentes sobre qué salas son mejores.
• Dos países vecinos quieren repartirse una región en disputa. Los ciudadanos de cada país difieren sobre qué partes de la región son más importantes. Este es un obstáculo común para la resolución de disputas internacionales.
• El "grupo de agentes" también puede representar diferentes preferencias conflictivas de una sola persona. Como se observa en la economía del comportamiento , las personas a menudo cambian sus preferencias según diferentes estados de ánimo o estados de ánimo. ^[3] Estas personas pueden representarse como un grupo de agentes, cada uno de los cuales tiene una preferencia diferente.

En todos los ejemplos anteriores, los grupos se fijan de antemano. En algunas configuraciones, los grupos se pueden determinar ad hoc, es decir, se puede agrupar a las personas en función de sus preferencias. Un ejemplo de una configuración de este tipo es: ^[4]

• Unas 30 personas quieren utilizar la cancha de baloncesto local. En cada partido participan 10 jugadores con distintas preferencias sobre qué horario es mejor. Es necesario dividir el tiempo del día en 3 partes y dividir a los jugadores en 3 grupos y asignar un grupo a cada franja horaria.

Criterios de equidad

Los criterios de equidad comunes, como la proporcionalidad y la ausencia de envidia , juzgan la división desde el punto de vista de un solo agente, con una única relación de preferencia . Hay varias formas de extender estos criterios a la división justa entre grupos.

La equidad unánime exige que la asignación se considere justa a los ojos de todos los agentes de todos los grupos. Por ejemplo:

• Una división se denomina unánimemente proporcional si cada agente de cada grupo valora la parte de su grupo como al menos 1/ k del valor total, donde k es el número de grupos.
• Una división se considera libre de envidia por unanimidad si cada agente de cada grupo valora la parte de su grupo al menos tanto como la parte de cualquier otro grupo.

La imparcialidad unánime es un requisito importante y a menudo no se puede satisfacer.

La equidad agregada asigna a cada grupo una determinada función agregada, como por ejemplo: suma, producto, media aritmética o media geométrica. Requiere que la asignación se considere justa de acuerdo con esta función agregada. Por ejemplo:

• Una división se denomina proporcional promedio si, para cada grupo, la media aritmética de los valores de los agentes respecto de la participación del grupo es al menos 1/ k del valor total.
• Una división se denomina libre de envidia del producto si, para cada grupo, el producto de los valores de la participación de los agentes en el grupo es al menos el producto de sus valores de la participación de cualquier otro grupo.

La equidad democrática exige que, en cada grupo, una determinada fracción de los agentes concuerde en que la división es justa; preferiblemente, esta fracción debe ser al menos la mitad. Una situación práctica en la que tal requisito puede ser útil es cuando dos países democráticos acuerdan dividirse entre ellos una determinada tierra en disputa y el acuerdo debe ser aprobado por un referéndum en ambos países.

La justicia unánime implica justicia agregada y justicia democrática. La justicia agregada y la justicia democrática son independientes: ninguna de ellas implica a la otra. ^[2]

La eficiencia de Pareto es otro criterio importante que se requiere además de la equidad. Se define de la manera habitual: ninguna asignación es mejor para al menos un agente individual y al menos igual de buena para todos los agentes individuales.

Resultados para recursos divisibles

En el contexto de un reparto justo de los votos , se conocen los siguientes resultados (donde k es el número de grupos y n es el número de agentes en todos los grupos juntos). ^[2]

• Justicia unánime : siempre existen asignaciones unánimes-proporcionales y unánimes-libres de envidia. Sin embargo, pueden estar desconectadas: pueden requerirse al menos n componentes conectados . Con dos grupos, n componentes son siempre suficientes. Con k >2 grupos, O( n log k ) componentes son siempre suficientes para una asignación unánime-proporcional, y O( nk ) componentes son siempre suficientes para una asignación unánime-libre de envidia. Es una pregunta abierta si n componentes son siempre suficientes o no.
• Justicia agregada : las asignaciones proporcionales promedio y libres de envidia promedio siempre existen y requieren solo k componentes conectados (es decir, cada grupo puede obtener una pieza conectada). Sin embargo, no se pueden encontrar utilizando un algoritmo finito en el modelo de consulta de Robertson-Webb .
• Justicia democrática : siempre existen asignaciones proporcionales democráticas a medias y asignaciones libres de envidia democráticas a medias. Con dos grupos, existen asignaciones que también están conectadas y se pueden encontrar en tiempo polinomial. Con k >2 grupos, es posible que no existan asignaciones justas democráticas a medias conectadas, pero el número de componentes requeridos es menor que para las asignaciones proporcionales unánimes.
• Justicia y eficiencia : Las tres variantes de proporcionalidad son compatibles con la eficiencia de Pareto para cualquier número de grupos. La ausencia de envidia unánime es compatible con la eficiencia de Pareto para 2 grupos, pero no para 3 o más grupos. La ausencia de envidia democrática 1/2 es compatible con la eficiencia de Pareto para 2 grupos, pero no para 5 o más grupos. No está claro si son compatibles para 3 o 4 grupos. ^[3]

El problema de la división es más sencillo cuando los agentes pueden agruparse ad hoc en función de sus preferencias. En este caso, existe una asignación conectada unánime y sin envidia para cualquier número de grupos y cualquier número de agentes en cada grupo. ^[4]

Proporcionalidad unánime y división exacta

En una división exacta (también llamada división por consenso ), hay n agentes y el objetivo es dividir la torta en k partes de modo que todos los agentes valoren todas las partes exactamente en 1/ k . Se sabe que siempre existe una división exacta con n ( k -1). Sin embargo, incluso para k = 2, encontrar una división exacta con n cortes es FIXP-hard, y encontrar una división exacta aproximada con n cortes es PPA-complete (ver división exacta para más información). Se puede demostrar que la proporcionalidad unánime es equivalente a la división por consenso en el siguiente sentido: ^[2]

• Para cada n y k , una solución a la división proporcional unánime entre n ( k -1)+1 agentes agrupados en k familias implica una solución a la división por consenso entre n agentes con k partes. En particular, implica que la división proporcional unánime requiere al menos n -1 cortes ( n componentes), encontrar una división proporcional unánime con n -1 cortes es FIXP-hard, y encontrar una división proporcional unánime aproximada con n -1 cortes es PPA-hard.
• Para cada n y k , una solución a la división exacta entre n agentes y k piezas implica una solución a la división unánime-proporcional entre n+1 agentes agrupados en k familias. En particular, implica que la división unánime-proporcional exacta se puede hacer con ( n -1)( k -1) cortes, y que encontrar una división unánime-proporcional aproximada está en PPA. El número de cortes es ajustado para k = 2 familias pero no para k > 2. ^[5]

Resultados para elementos indivisibles

En el contexto de la asignación justa de artículos , se conocen los siguientes resultados.

Equidad máxima aproximada unánime : ^[6]

• Cuando hay dos grupos , se puede garantizar una aproximación multiplicativa positiva a la equidad de MMS si y solo si la cantidad de agentes en los grupos es (1, n -1) o (2,2) o (2,3). Los resultados positivos se pueden lograr mediante algoritmos de tiempo polinomial. En todos los demás casos, hay instancias en las que al menos un agente con un MMS positivo obtiene un valor cero en todas las asignaciones.
• Cuando hay tres o más grupos , se puede lograr una aproximación multiplicativa positiva a la equidad MMS si k -1 grupos contienen un solo agente; por el contrario, si todos los grupos contienen 2 agentes y un grupo contiene al menos 5 agentes, entonces no es posible una aproximación positiva.

Aproximación unánime de ausencia de envidia : ^[7]

• Cuando hay dos grupos de agentes con valoraciones aditivas binarias , existe una asignación unánime-EF1 si los tamaños de grupo son (1,5) o (2,3), pero podría no existir si los tamaños de grupo son (1,6) o (2,4) o (3,3). En general, una asignación EF c podría no existir si los tamaños de grupo son . Nótese que, con valoraciones binarias, EF1 es equivalente a EFX, pero más débil que EFX0. Una asignación unánime-EFX0 podría no existir si los tamaños de grupo son (1,2); esto contrasta con la situación con agentes individuales, es decir, tamaños de grupo (1,1), donde una asignación EFX0 siempre existe incluso para valoraciones monótonas. ^[8] ${\displaystyle ({2c+1 \choose c+1},{2c+1 \choose c+1})}$
  • Es NP-difícil decidir si una instancia dada admite una asignación unánimemente EF1.
• Cuando hay dos grupos de agentes con valoraciones reactivas (un superconjunto de valoraciones aditivas ), existe una asignación equilibrada unánimemente EF1 si los tamaños de los grupos son (1,2). Si una determinada conjetura sobre los gráficos de Kneser es cierta, entonces también existe una asignación equilibrada unánimemente EF1 para los tamaños de grupo (1,4), (2,3) y valoraciones monótonas arbitrarias. Una asignación unánimemente EFX podría no existir si los tamaños de los grupos son (1,2).
• Para dos grupos ad hoc , con cualquier número de agentes con valoraciones monótonas arbitrarias, existe una asignación unánimemente EF1. También existe una partición equilibrada de los agentes y una asignación equilibrada unánimemente EF1 de los bienes. La EF1 no puede reforzarse a EFX ni siquiera con valoraciones aditivas.
• Para k grupos ad-hoc , con cualquier número de agentes con valoraciones aditivas, existe una asignación unánime PROP*1.
• Para n agentes divididos arbitrariamente en k grupos, siempre existe una asignación libre de envidia hasta c elementos, donde . Lo mismo es cierto para la proporcionalidad hasta c elementos. Para la división por consenso, los límites son . Todos los límites son asintóticamente estrictos cuando el número de grupos es constante. Las pruebas utilizan la teoría de la discrepancia . ^[9] ${\displaystyle O({\sqrt {n}})\geq c\geq \Omega ({\sqrt {n/k^{3}}})}$ ${\displaystyle O({\sqrt {n}})\geq c\geq \Omega ({\sqrt {n/k}})}$

Ausencia unánime de envidia con alta probabilidad : ^[10]

• Cuando todos los grupos k contienen el mismo número de agentes y sus valoraciones se extraen al azar, existe una asignación libre de envidia con alta probabilidad si el número de bienes está en , y puede lograrse mediante un algoritmo codicioso que maximice la suma de utilidades. ${\displaystyle \Omega (n\log n)}$
  • Los resultados pueden extenderse a dos grupos con diferentes tamaños.
  • Existe también un mecanismo veraz que logra una asignación aproximadamente libre de envidia con alta probabilidad.
• Si el número de bienes es menor que n , entonces con alta probabilidad no existe una asignación libre de envidia.

Justicia democrática : ^[11]

• Para dos grupos con valoraciones aditivas binarias (con cualquier número de agentes), siempre existe una asignación democrática 1/2 libre de envidia excepto 1. La constante 1/2 es estricta incluso si permitimos la asignación libre de envidia excepto c para cualquier constante c . Lo mismo es cierto también para la proporcionalidad excepto c . Una noción de equidad diferente, que se puede garantizar a más de 1/2 de los agentes en cada grupo, es la aproximación ordinal maximin-share . Para cada entero c , existe una asignación democrática 1-de- c MMS-justa. Estas asignaciones se pueden encontrar de manera eficiente utilizando una variante de asignación de ítems round-robin , con votación de aprobación ponderada dentro de cada grupo. El límite superior de la fracción de agentes a los que se les puede garantizar 1 de sus mejores ítems c (una propiedad más débil que 1-de- c MMS) es . Para , el límite inferior para la asignación 1-de-mejor- c se puede mejorar de 1/2 a 3/5; Es una cuestión abierta si el límite superior de 3/4 siempre se puede alcanzar. ${\displaystyle (1-1/2^{c-1})}$ ${\displaystyle (1-1/2^{c})}$ ${\displaystyle c=2}$
  • Es NP-difícil decidir si una instancia dada admite una asignación que le dé a cada agente una utilidad positiva.
• Para dos grupos con valoraciones generales monótonas, siempre existe una asignación democrática de 1/2 libre de envidia excepto 1, y se puede encontrar mediante un algoritmo eficiente.
• Para tres o más grupos con valoraciones aditivas binarias, siempre existe una asignación democrática libre de envidia excepto 1 1/ k ; con valoraciones monótonas generales, siempre existe una asignación democrática libre de envidia excepto 2 1/ k . El factor 1/ k es ajustado para la asignación libre de envidia excepto c para cualquier constante c . Si la ausencia de envidia se relaja a la proporcionalidad o a la participación maximin, entonces se pueden lograr garantías similares utilizando un algoritmo de tiempo polinomial. Para grupos con valoraciones aditivas, se puede utilizar una variante de asignación de ítems round-robin para encontrar una asignación democrática 1/3-1 de los mejores k .

División justa grupal de artículos y dinero

En el contexto de la armonía en el alquiler (división de habitaciones y alquiler sin envidias), se conocen los siguientes resultados. ^[12]

• La ausencia de envidia unánime (denominada ausencia de envidia fuerte en el artículo) puede no existir cuando la política de reparto de costos es igual o proporcional, pero siempre existe con una política de reparto de costos libre. Además, una asignación unánime sin envidia con reparto de costos libre que maximice la renta total se puede encontrar en tiempo polinomial.
  • En los grupos ad hoc existe unanimidad en cuanto a la ausencia de envidias, incluso con una política de reparto de costos igualitario.
• La ausencia promedio de envidia (denominada en el documento ausencia de envidia agregada ) siempre existe cuando la política de reparto de costos es igual, proporcional o gratuita.

Reparto justo de loterías de billetes

Una aplicación práctica de la distribución equitativa entre grupos es la distribución de entradas para parques u otras actividades con capacidad limitada. A menudo, las entradas se distribuyen al azar. Cuando la gente llega sola, una simple lotería aleatoria uniforme entre todos los candidatos es una solución justa. Pero la gente suele venir en familias o grupos de amigos que quieren participar juntos. Esto lleva a diversas consideraciones sobre cómo diseñar exactamente la lotería. Se conocen los siguientes resultados:

• En el caso de que todos los miembros del grupo estén identificados de antemano, el mecanismo de lotería de grupos ordena los grupos de manera uniforme y aleatoria y los procesa secuencialmente mientras haya capacidad disponible. Este mecanismo natural puede ser injusto e ineficiente; existen algunas alternativas mejores. ^[13]
• Si los agentes pueden solicitar múltiples tickets sin identificar a los miembros de su grupo, el mecanismo de lotería individual ordena a los agentes de manera uniforme y aleatoria y les otorga a cada uno su pedido mientras haya capacidad disponible. Este mecanismo común podría producir resultados arbitrariamente injustos e ineficientes. La lotería individual ponderada es un mecanismo alternativo en el que el orden de procesamiento está sesgado para favorecer a los agentes con pedidos más pequeños. Es aproximadamente justo y aproximadamente eficiente. ^[13]
• El algoritmo de Maximización de Probabilidad Iterativa encuentra una lotería que maximiza la utilidad más pequeña (basada en la regla igualitaria y el orden leximin ). Es a prueba de estrategias grupales y logra una aproximación de 1/2 factor de la utilización máxima. También es Pareto-eficiente , libre de envidia y anónimo . Sus propiedades son máximas en el sentido de que es imposible mejorar una propiedad sin dañar otra. ^[14]

Conceptos relacionados

• La ausencia de envidias grupales es un criterio de equidad para la distribución justa entre agentes individuales . Dice que, después de que cada agente individual obtiene su parte privada, ninguna coalición de agentes envidia a otra coalición del mismo tamaño.
• Un bien de club es un recurso que consumen simultáneamente todos los miembros de un mismo grupo ("club"), pero que queda excluido de los miembros de otros grupos. En el problema de división equitativa de grupos, todos los bienes asignados son bienes de club en el grupo al que están asignados.
• Un subconjunto agradable es un subconjunto de elementos que todas las personas de un determinado grupo consideran al menos tan bueno como su complemento.

Referencias

1. Suksompong, Warut (2018). Asignación de recursos y toma de decisiones para grupos (Tesis). OCLC  1050345365.
2. Segal-Halevi, Erel; Nitzan, Shmuel (diciembre de 2019). "Corte justo de la torta entre familias" (PDF) . Elección social y bienestar . 53 (4): 709–740. doi :10.1007/s00355-019-01210-9. S2CID  1602396.
3. Bade, Sophie; Segal-Halevi, Erel (1 de septiembre de 2023). "Justicia para agentes multi-yo". Juegos y comportamiento económico . 141 : 321–336. arXiv : 1811.06684 . doi :10.1016/j.geb.2023.06.004. ISSN  0899-8256.
4. Segal-Halevi, Erel; Suksompong, Warut (2 de enero de 2021). "Cómo cortar un pastel de manera justa: una generalización a los grupos". The American Mathematical Monthly . 128 (1): 79–83. arXiv : 2001.03327 . doi :10.1080/00029890.2021.1835338. S2CID  210157034.
5. Segal-Halevi, Erel; Nitzan, Shmuel (diciembre de 2019). "Corte justo de la torta entre familias" (PDF) . Elección social y bienestar . 53 (4): 709–740. doi :10.1007/s00355-019-01210-9. S2CID  1602396.
6. Suksompong, Warut (1 de marzo de 2018). "Cuotas maximin aproximadas para grupos de agentes". Ciencias Sociales Matemáticas . 92 : 40–47. arXiv : 1706.09869 . doi :10.1016/j.mathsocsci.2017.09.004. S2CID  3720438.
7. Kyropoulou, Maria; Suksompong, Warut; Voudouris, Alexandros A. (12 de noviembre de 2020). "Casi sin envidia en la asignación de recursos grupales" (PDF) . Ciencias Informáticas Teóricas . 841 : 110–123. doi :10.1016/j.tcs.2020.07.008. S2CID  220546580.
8. Plaut, Benjamin; Roughgarden, Tim (enero de 2020). "Casi sin envidia con valoraciones generales". Revista SIAM de Matemáticas Discretas . 34 (2): 1039–1068. arXiv : 1707.04769 . doi :10.1137/19M124397X. S2CID  216283014.
9. Manurangsi, Pasin; Suksompong, Warut (2022). "Casi ausencia de envidia para grupos: límites mejorados mediante la teoría de la discrepancia". Ciencias de la Computación Teórica . 930 : 179–195. arXiv : 2105.01609 . doi :10.1016/j.tcs.2022.07.022. S2CID  233714947.
10. Manurangsi, Pasin; Suksompong, Warut (1 de septiembre de 2017). "Existencia asintótica de divisiones justas para grupos". Ciencias sociales matemáticas . 89 : 100–108. arXiv : 1706.08219 . doi :10.1016/j.mathsocsci.2017.05.006. S2CID  47514346.
11. Segal-Halevi, Erel; Suksompong, Warut (diciembre de 2019). "Asignación justa y democrática de bienes indivisibles". Inteligencia artificial . 277 : 103167. arXiv : 1709.02564 . doi :10.1016/j.artint.2019.103167. S2CID  203034477.
12. Ghodsi, Mohammad; Latifian, Mohamad; Mohammadi, Arman; Moradian, Sadra; Seddighin, Masoud (2018). "División de renta entre grupos". Optimización combinatoria y aplicaciones . Apuntes de clase en informática. Vol. 11346. págs. 577–591. doi :10.1007/978-3-030-04651-4_39. ISBN 978-3-030-04650-7.
13. Arnosti, Nick; Bonet, Carlos (2022). "Loterías para experiencias compartidas". Actas de la 23.ª Conferencia de la ACM sobre Economía y Computación . págs. 1179–1180. arXiv : 2205.10942 . doi :10.1145/3490486.3538312. ISBN 978-1-4503-9150-4.S2CID248986158  .​
14. Arbiv, Tal; Aumann, Yonatan (28 de junio de 2022). "Loterías de regalo justas y veraces". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 36 (5): 4785–4792. doi : 10.1609/aaai.v36i5.20405 . S2CID  250288879.