División equitativa entre los grupos

La división equitativa entre grupos ^{[ 1 ]} (o familias ^{[ 2 ]} ) es una clase de problemas de división equitativa en la que los recursos se asignan entre grupos de agentes, en lugar de entre agentes individuales. Tras la división, todos los miembros de cada grupo consumen la misma parte, pero pueden tener preferencias diferentes; por lo tanto, distintos miembros de un mismo grupo podrían discrepar sobre si la asignación es justa o no. Algunos ejemplos de situaciones de división equitativa entre grupos son:

• Varios hermanos heredaron casas de sus padres y deben repartirlas. Cada hermano tiene una familia, cuyos miembros pueden tener opiniones diferentes sobre qué casa es mejor.
• Una sociedad se disuelve y sus activos deben repartirse entre los socios. Los socios son empresas; cada empresa tiene varios accionistas, quienes podrían discrepar sobre qué activo es más importante.
• La dirección de la universidad quiere distribuir 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 desean dividirse una región en disputa. Los ciudadanos de cada país discrepan sobre qué partes de la región son más importantes. Este es un obstáculo común para la resolución de conflictos internacionales.
• El "grupo de agentes" también puede representar las distintas preferencias contradictorias de una misma persona. Como se observa en la economía conductual , las personas suelen cambiar sus preferencias según su estado de ánimo o sus estados de ánimo. ^{[ 3 ]} Estas personas pueden representarse como un grupo de agentes, cada uno con una preferencia diferente.

En todos los ejemplos anteriores, los grupos se fijan de antemano. En algunos casos, los grupos pueden determinarse ad hoc, es decir, las personas pueden agruparse según sus preferencias. Un ejemplo de tal situación es: ^{[ 4 ]}

• Unas 30 personas desean usar la cancha de baloncesto local. Cada partido involucra a 10 jugadores con diferentes preferencias en cuanto al horario. Es necesario dividir el día en 3 franjas horarias, dividir a los jugadores en 3 grupos y asignar un grupo a cada franja horaria.

Los criterios comunes de equidad, como la proporcionalidad y la ausencia de envidia , evalúan la división desde la perspectiva de un único agente, con una única relación de preferencia . Existen diversas maneras de extender estos criterios a una división equitativa entre grupos.

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

• Una división se denomina proporcional unánime si cada agente en cada grupo valora la parte de su grupo como al menos 1/ k del valor total, donde k es el número de grupos.
• Se dice que una división es unánimemente libre de envidia si cada agente de cada grupo valora la parte que le corresponde a su grupo al menos tanto como la parte que le corresponde a cualquier otro grupo.

La imparcialidad unánime es un requisito fundamental, y a menudo resulta imposible de satisfacer.

La equidad agregada asigna a cada grupo una determinada función agregada , como la suma, el producto, la media aritmética o la media geométrica . Requiere que la asignación se considere justa según 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 con respecto a la parte que le corresponde al grupo es al menos 1/ k del valor total.
• Se dice que una división está libre de envidia de productos si, para cada grupo, el producto de los valores que los agentes asignan a la participación del grupo es al menos igual al producto de sus valores a la participación de cualquier otro grupo.

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

La justicia unánime implica tanto justicia agregada como justicia democrática. La justicia agregada y la justicia democrática son independientes; ninguna 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 forma habitual: ninguna asignación es mejor para al menos un agente individual y al menos igual de buena para todos los agentes individuales.

En el contexto del reparto equitativo de pasteles , 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 ]}

• Equidad unánime : Las asignaciones unánimes proporcionales y unánimes libres de envidia siempre existen. Sin embargo, pueden estar desconectadas: podrían requerirse al menos n componentes conectados . Con dos grupos, n componentes siempre son suficientes. Con k > 2 grupos, O( n log k ) componentes siempre son suficientes para una asignación unánime proporcional, y O( nk ) componentes siempre son suficientes para una asignación unánime libre de envidia. Queda por determinar si n componentes son siempre suficientes.
• Equidad agregada : Las asignaciones proporcionales promedio y libres de envidia promedio siempre existen y requieren solo k componentes conexas (es decir, cada grupo puede obtener una pieza conexa). Sin embargo, no se pueden encontrar utilizando un algoritmo finito en el modelo de consulta de Robertson-Webb .
• Equidad democrática : Siempre existen asignaciones proporcionales 1/2 democráticas y libres de envidia 1/2 democráticas. Con dos grupos, existen tales asignaciones que también están conectadas y pueden hallarse en tiempo polinomial. Con k > 2 grupos, es posible que no existan asignaciones justas 1/2 democráticas conectadas, pero el número de componentes requeridos es menor que para las asignaciones proporcionales unánimes.
• Equidad 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. La ausencia de envidia 1/2 democrática es compatible con la eficiencia de Pareto para 2 grupos, pero no para 5 o más. Queda por determinar si son compatibles para 3 o 4 grupos. ^{[ 3 ]}

El problema de la división se simplifica cuando los agentes pueden agruparse ad hoc según sus preferencias. En este caso, existe una asignación conectada unánime y libre de envidia para cualquier número de grupos y cualquier número de agentes en cada grupo. ^{[ 4 ]}

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

Equidad unánime aproximada de participación maximin : ^{[ 6 ]}

• Cuando hay dos grupos , se puede garantizar una aproximación multiplicativa positiva a la equidad MMS si y solo si el número de agentes en los grupos es (1, n -1), (2,2) o (2,3). Los resultados positivos se pueden obtener mediante algoritmos de tiempo polinomial. En todos los demás casos, existen 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 alcanzar 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 ninguna aproximación positiva.
• Los resultados sobre la aproximación ordinal de la participación maximin son más positivos. ^{[ 7 ]}

Ausencia aproximada unánime de envidia : ^{[ 8 ]}

• Cuando hay dos grupos de agentes con valoraciones aditivas binarias , existe una asignación EF1 unánime si los tamaños de los grupos son (1,5) o (2,3), pero podría no existir si los tamaños de los grupos son (1,6) o (2,4) o (3,3). En general, podría no existir una asignación EF c si los tamaños de los grupos son${\displaystyle ({2c+1 \choose c+1},{2c+1 \choose c+1})}$Nótese que, con valoraciones binarias, EF1 es equivalente a EFX, pero más débil que EFX0. Una asignación unánime de 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 siempre existe una asignación de EFX0 incluso para valoraciones monótonas. ^{[ 9 ]}
  • Es un problema NP-difícil decidir si una instancia dada admite una asignación EF1 unánime.
• Cuando hay dos grupos de agentes con valoraciones receptivas (un superconjunto de valoraciones aditivas ), existe una asignación equilibrada EF1 unánime si los tamaños de los grupos son (1,2). Si se cumple una conjetura sobre los grafos de Kneser , también existe una asignación equilibrada EF1 unánime para tamaños de grupo (1,4), (2,3) y valoraciones monótonas arbitrarias. Es posible que no exista una asignación EFX unánime si los tamaños de los grupos son (1,2).
• Para dos grupos ad hoc , con cualquier número de agentes y valoraciones monótonas arbitrarias, existe una asignación EF1 unánime. También existe una partición equilibrada de los agentes y una asignación equilibrada EF1 unánime de los bienes. La asignación 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ánimemente PROP*1.
• Para n agentes divididos arbitrariamente en k grupos, siempre existe una asignación que está libre de envidia hasta c elementos, donde${\displaystyle O({\sqrt {n}})\geq c\geq \Omega ({\sqrt {n/k^{3}}})}$. Lo mismo es cierto para la proporcionalidad hasta c elementos. Para la división por consenso, los límites son${\displaystyle O({\sqrt {n}})\geq c\geq \Omega ({\sqrt {n/k}})}$Todos los límites son asintóticamente ajustados cuando el número de grupos es constante. Las demostraciones utilizan la teoría de la discrepancia . ^{[ 10 ]}

Ausencia unánime de envidia con alta probabilidad : ^{[ 11 ]}

• Cuando todos los k grupos 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${\displaystyle \Omega (n\log n)}$y se puede lograr mediante un algoritmo voraz que maximiza la suma de las utilidades.
  • Los resultados pueden extrapolarse a dos grupos de tamaños diferentes.
  • También existe un mecanismo veraz que logra una asignación prácticamente 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.

Equidad democrática : ^{[ 12 ]}

• Para dos grupos con valoraciones aditivas binarias (con cualquier número de agentes), siempre existe una asignación 1/2-democrática libre de envidia excepto 1. La constante 1/2 es ajustada incluso si permitimos una 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 puede garantizarse a más de 1/2 de los agentes en cada grupo, es la aproximación de participación maximin ordinal . Para cada entero c , existe una${\displaystyle (1-1/2^{c-1})}$-Asignación democrática 1 de c MMS justa. Estas asignaciones se pueden encontrar de manera eficiente utilizando una variante de asignación de elementos round-robin , con votación de aprobación ponderada dentro de cada grupo. El límite superior en la fracción de agentes a los que se les puede garantizar 1 de sus mejores c elementos (una propiedad más débil que 1 de c MMS) es${\displaystyle (1-1/2^{c})}$. Para${\displaystyle c=2}$El límite inferior para la asignación 1 de los mejores c se puede mejorar de 1/2 a 3/5; es una cuestión abierta si siempre se puede alcanzar el límite superior de 3/4.
  • Es un problema 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 monótonas generales, siempre existe una asignación 1/2 democrática 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 proporcionalidad o participación maximin, entonces se pueden obtener garantías similares utilizando un algoritmo de tiempo polinomial. Para grupos con valoraciones aditivas, se puede utilizar una variante de la asignación de elementos round-robin para encontrar una asignación democrática 1/3 de 1 de los k mejores .

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

• La ausencia unánime de envidia (denominada ausencia fuerte de envidia en este artículo) puede no existir cuando la política de reparto de costes es igualitaria o proporcional, pero siempre existe con una política de reparto de costes gratuita. Además, se puede encontrar en tiempo polinomial una asignación unánimemente libre de envidia con reparto de costes gratuito que maximice la renta total.
  • En los grupos ad hoc, existe una ausencia unánime de envidia incluso con una política de reparto de costes equitativo.
• La ausencia promedio de envidia (denominada ausencia agregada de envidia en este documento) siempre existe cuando la política de reparto de costes es igualitaria, proporcional o gratuita.

Una aplicación práctica de la distribución equitativa entre grupos es la asignación de entradas para parques o atracciones con capacidad limitada. A menudo, las entradas se distribuyen al azar. Cuando las personas llegan solas, un sorteo simple y aleatorio entre todos los candidatos es una solución justa. Sin embargo, con frecuencia las personas acuden en familias o grupos de amigos que desean entrar juntos. Esto plantea diversas consideraciones sobre cómo diseñar el sorteo. 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 forma uniforme y aleatoria, y los procesa secuencialmente mientras haya capacidad disponible. Este mecanismo natural podría ser injusto e ineficiente; existen algunas alternativas mejores. ^{[ 14 ]}
• Si los agentes pueden solicitar varios boletos sin identificar a los miembros de su grupo, el mecanismo de Lotería Individual ordena a los agentes de forma aleatoria y uniforme, y les asigna a cada uno su solicitud siempre que haya capacidad disponible. Este mecanismo común podría generar resultados arbitrariamente injustos e ineficientes. La Lotería Individual Ponderada es un mecanismo alternativo en el que el orden de procesamiento favorece a los agentes con solicitudes más pequeñas. Es aproximadamente justo y aproximadamente eficiente. ^{[ 14 ]}
• El algoritmo de Maximización Iterativa de la Probabilidad encuentra una lotería que maximiza la utilidad mínima (basada en la regla igualitaria y el orden leximin ). Es inmune a la manipulación de estrategias grupales y alcanza una aproximación de 1/2 factor de la utilización máxima. Además, 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 perjudicar otra. ^{[ 15 ]}

• La ausencia de envidia grupal es un criterio de equidad para una distribución justa entre los agentes individuales . Establece que, después de que cada agente individual reciba su parte, 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 está excluido de los miembros de otros grupos. En el problema de la división equitativa entre grupos, todos los bienes asignados son bienes de club dentro del grupo al que se asignan.
• Un subconjunto aceptable es un subconjunto de elementos que todas las personas de un grupo determinado consideran que es al menos tan bueno como su complemento.

• Una distribución de pastel entre grupos que comparten. ^{[ 16 ]}