Reparto de pastel igualitario

El reparto igualitario de un pastel es una variante del reparto equitativo en la que el criterio de equidad es la regla de igualdad . El pastel representa un recurso continuo (como tierra o tiempo) que debe distribuirse entre personas con diferentes valoraciones sobre partes de dicho recurso. El objetivo del reparto igualitario es maximizar el valor mínimo de un agente; sujeto a este, maximizar el siguiente valor mínimo; y así sucesivamente. También se denomina reparto leximin , ya que la optimización se realiza utilizando el orden leximin en los vectores de utilidades.

El concepto de reparto igualitario de un pastel fue descrito por primera vez por Dubins y Spanier , quienes lo denominaron "partición óptima". ^{[ 1 ]}

Las asignaciones óptimas leximin existen siempre que el conjunto de asignaciones sea un espacio compacto . Esto siempre se cumple al asignar objetos discretos y es fácil de demostrar al asignar un número finito de recursos homogéneos continuos. Dubins y Spanier demostraron que, con un recurso heterogéneo continuo (" pastel "), el conjunto de asignaciones es compacto. ^{[ 1 ]} Por lo tanto, siempre existen asignaciones óptimas leximin de pastel. Por esta razón, la regla de asignación leximin de pastel a veces se denomina regla de Dubins-Spanier . ^{[ 2 ]}

Cuando las valoraciones de los agentes no están normalizadas (es decir, distintos agentes pueden asignar un valor diferente al conjunto), existe una diferencia entre el perfil de utilidad absoluta de una asignación (donde el elemento i es simplemente la utilidad del agente i ) y su perfil de utilidad relativa (donde el elemento i es la utilidad del agente i dividida por el valor total para el agente i ). La regla leximin absoluta elige una asignación en la que el perfil de utilidad absoluta es leximin-maximal, y la regla leximin relativa elige una asignación en la que el perfil de utilidad relativa es leximin-maximal.

Ambas variantes de la regla leximin son Pareto-óptimas y monótonas en términos de población . Sin embargo, difieren en otras propiedades: ^{[ 3 ]}

• La regla leximin absoluta es monótona en cuanto a recursos , pero no proporcional ;
• La regla leximin relativa es proporcional pero no monótona con respecto a los recursos.

Ambas variantes de la regla leximin pueden generar asignaciones que no están libres de envidia . Por ejemplo, supongamos que hay 5 agentes, el pastel es homogéneo por partes con 3 regiones y las valoraciones de los agentes son (los valores faltantes son ceros):

Todos los agentes valoran el pastel completo en 15, por lo que leximin absoluto y leximin relativo son equivalentes. El valor mínimo posible más grande es 5, por lo que una asignación leximin debe dar a todos los agentes al menos 5. Esto significa que la parte derecha debe dividirse equitativamente entre los agentes C, D y E, y la parte central debe asignarse por completo al agente B. Pero entonces A envidia a B. ^{[ 3 ]}

Dubins y Spanier ^{[ 1 ]} demostraron que, cuando todas las medidas de valor son estrictamente positivas, toda asignación leximin relativa está libre de envidia. ^{[ 4 ] : Sec.4}

Weller ^{[ 4 ] : La sección 4} mostró una asignación de pastel libre de envidia y eficiente que no es leximin relativa. El pastel es [0,1], hay tres agentes y sus medidas de valor son distribuciones triangulares centradas en 1/4, 1/2 y 3/4 respectivamente. La asignación ([0,3/8],[3/8,5/8],[5/8,1]) tiene un perfil de utilidad (3/8,7/16,7/16). Es libre de envidia y utilitariamente óptima, por lo tanto Pareto-eficiente. Sin embargo, hay otra asignación ([0,5/16],[5/16,11/16],[11/16,1]) con un perfil de utilidad leximin-mejor.

Dall'aglio ^{[ 2 ]} presenta un algoritmo para calcular una asignación de recursos óptima en términos de leximin .

Aumann, Dombb y Hassidim ^{[ 5 ]} presentan un algoritmo que, para cada e >0, calcula una asignación con bienestar igualitario al menos (1-e) del óptimo utilizando${\displaystyle 2^{n}\cdot n\cdot \log _{2}(n/\epsilon )}$consultas. Esto es exponencial en n , pero polinómico en el número de dígitos de precisión.

Por otro lado, demuestran que, a menos que P=NP, es imposible aproximar el valor igualitario óptimo a un factor mejor que 2, en tiempo polinomial en n . La demostración es por reducción a partir del emparejamiento tridimensional (3DM). Para cada instancia de emparejamiento 3DM con m hiperaristas, construyen una instancia de corte de pastel con n agentes, donde 4 m ≤ n ≤ 5 m . Demuestran que, si la instancia 3DM admite un emparejamiento perfecto , entonces existe una asignación de pastel con un valor igualitario de al menos 1/ m ; de lo contrario, no existe ninguna asignación de pastel con un valor igualitario mayor que 1/(2 m ).

• Reparto equitativo de la tarta : una asignación que otorga a cada agente la misma utilidad. A menudo, la asignación igualitaria coincide con la equitativa, ya que si las utilidades son diferentes, la utilidad menor puede mejorarse transfiriendo parte de la tarta del agente con mayor utilidad.
• Equivalencia igualitaria : un concepto similar en el contexto de la asignación homogénea de recursos.