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.

The two rules are equivalent when the agents' valuations are already normalized, that is, all agents assign the same value to the set of all items. However, they may differ with non-normalized valuations. For example, if there are four items, Alice values them at 1,1,1,1 and George values them at 3,3,3,3, then the absolute-leximin rule would give three items to Alice and one item to George, since the utility profile in this case is (3,3), which is optimal. In contrast, the relative-leximin rule would give two items to each agent, since the normalized utility profile in this case, when the total value of both agents is normalized to 1, is (0.5,0.5), which is optimal.

Although the general problem is NP-hard, small instances can be solved exactly by constraint programming techniques.

• Bouveret and Lemaître present five different algorithms for finding leximin-optimal solutions to discrete constraint-satisfaction problems.^[2] They present max-min item allocation as a special case.
• Dall'Aglio and Mosca^[3] gave an exact, branch-and-bound algorithm for two agents, based on an adaptation of the Adjusted winner procedure.

Demko and Hill^[4] present a randomized algorithm that attains an egalitarian item allocation in expectation.

Below, n is the number of agents and m is the number of items.

For the special case of the santa claus problem:

• Bansal and Sviridenko^[5] gave a ${\displaystyle O(\log {\log {n}}/\log {\log {\log {n}}})}$-approximation algorithm, based on rounding a linear program.
• Feige^[6] proved that a polynomial-time constant-factor approximation algorithm exists, but the proof used Lovász local lemma and was non-constructive.
• Asadpour, Feige and Saberi^[7] proved that the integrality gap of the configuration linear program is 1/4. The implies a 1/4-approximation algorithm, using hypergraph matching. However, they could not prove that the algorithm converges in a polynomial number of steps.
• Polacek and Svensson^[8] gave a Quasi-polynomial time 4-approximation algorithm.
• Annamalai, Kalaitzis and Svensson^[9] gave a polynomial-time 13-approximation algorithm.
• 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 utilizando 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 ]}