Asignación equitativa de artículos

La asignación igualitaria de elementos , también llamada asignación max-min, 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ínimo de un agente sea lo más grande posible. En caso de que haya dos o más asignaciones con el mismo valor mínimo, entonces el objetivo es seleccionar, entre estas asignaciones, aquella en la que el segundo valor mínimo sea lo más grande posible, y así sucesivamente (según el orden leximin ). Por lo tanto, una asignación igualitaria de elementos a veces se denomina asignación leximin de elementos .

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

Algunos problemas relacionados son:

• La partición de números en múltiples categorías con el objetivo max-min 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-difícil en general.
• La planificación de máquinas no relacionadas es un problema dual, cuyo objetivo es minimizar el valor máximo .
• La asignación de artículos mediante el método Maximin Share 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 superior a un determinado umbral.

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 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 como 1,1,1,1 y George como 3,3,3,3, entonces la regla leximin absoluta daría tres elementos a Alice y uno 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 se normaliza a 1, es (0,5,0,5), que es óptimo.

Aunque el problema general es NP-difícil, los casos pequeños pueden resolverse con exactitud mediante técnicas de programación con 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 de elementos max-min como un caso especial.
• Dall'Aglio y Mosca ^{[ 3 ]} dieron un algoritmo exacto de ramificación y acotación para dos agentes, basado en una adaptación del procedimiento del ganador ajustado .

Demko y Hill ^{[ 4 ]} presentan un algoritmo aleatorio que logra una asignación de elementos igualitaria en promedio.

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 una${\displaystyle O(\log {\log {n}}/\log {\log {\log {n}}})}$-algoritmo de aproximación, basado en el redondeo de un programa lineal .
• Feige ^{[ 6 ]} demostró que existe un algoritmo de aproximación de factor constante en tiempo polinomial , pero la demostración utilizó el lema local de Lovász y no fue constructiva.
• Asadpour, Feige y Saberi ^{[ 7 ]} demostraron que la brecha de integralidad del programa lineal de configuración es 1/4. Esto implica un algoritmo de aproximación de 1/4, utilizando el emparejamiento de hipergrafos . Sin embargo, no pudieron demostrar que el algoritmo converge en un número polinomial de pasos.
• Polacek y Svensson ^{[ 8 ]} dieron un algoritmo de aproximación 4 en tiempo cuasipolinomial .
• Annamalai, Kalaitzis y Svensson ^{[ 9 ]} dieron un algoritmo de aproximación 13 en tiempo polinomial.
• Davies, Rothvoss y Zhang ^{[ 10 ]} mejoraron el factor de aproximación a 4 introduciendo restricciones de matroide en el programa lineal básico .

En el caso general, para agentes con valoraciones aditivas :

• Bezakova y Dani ^{[ 11 ]} presentaron dos algoritmos. El primero da un${\displaystyle (m-n+1)}$-aproximación de factor al valor igualitario óptimo. El segundo encuentra una asignación que es igualitaria salvo 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 anterior de Lenstra, Shmoys y Tardos, ^{[ 12 ]} que esencialmente encuentra una asignación que es igualitaria salvo 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 tal manera que cada agente pierde como máximo un bien, o gana como máximo una tarea.
• Asadpour y Saberi ^{[ 13 ]} dieron una${\displaystyle O({\sqrt {n}}\cdot \log ^{3}n)}$-algoritmo de aproximación. Su algoritmo utiliza un método iterativo para redondear una coincidencia fraccionaria en un árbol . También proporciona mejores límites cuando se permite excluir a una pequeña fracción de personas del problema.
• Chakrabarty, Chuzoy y Khanna ^{[ 14 ]} dieron una${\displaystyle O(m^{\varepsilon })}$-algoritmo de aproximación con un tiempo de ejecución de${\displaystyle O(m^{1/\varepsilon })}$, para cualquier${\displaystyle \varepsilon \in \Omega \left({\frac {\log \log m}{\log m}}\right)}$Para el caso especial en el que cada elemento tiene una utilidad distinta de cero para como máximo dos agentes, proporcionaron un algoritmo de aproximación de 2 factores y demostraron que es difícil aproximarlo a cualquier factor mejor.
• Golovin ^{[ 15 ]} dio un algoritmo mediante el cual, para cada entero${\displaystyle k}$, a${\displaystyle (1-1/k)}$fracción de los agentes recibe utilidad al menos${\displaystyle OPT/k}$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${\displaystyle O({\sqrt {n}})}$-algoritmo de aproximación para el caso especial con dos clases de bienes.
• Cuando el número de agentes es constante, existe un FPTAS que utiliza la técnica de Woeginger . ^{[ 16 ]}

Para agentes con funciones de utilidad submodulares :

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

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 cestas . Dada cualquier asignación discreta, para cualquier agente i , definimos r ( i ) como la clasificación de la cesta del agente i, de modo que r(i)=1 si i obtuvo su mejor cesta, r(i)=2 si obtuvo su segunda mejor cesta, 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 cestas.

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 , definimos t ( i , k ) como la fracción total que el agente i recibe de sus k clases de indiferencia superiores. 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. ^{[ 20 ]}

En la modalidad en línea, los artículos llegan uno por uno. Cada artículo debe asignarse inmediatamente al llegar.

Kawase y Sumita ^{[ 21 ]} estudian dos variantes: para la variante adversarial, dan un algoritmo con una razón competitiva de 1/n y demuestran que es el mejor posible. Para la variante i.i.d., dan un algoritmo casi óptimo.

La regla leximin se ha utilizado para asignar equitativamente las aulas no utilizadas en las escuelas públicas a las escuelas chárter. ^{[ 26 ]}