El corte de pastel igualitario es un tipo de corte de pastel justo en el que el criterio de equidad es la regla igualitaria . El pastel representa un recurso continuo (como la tierra o el tiempo), que debe asignarse entre personas con diferentes valoraciones sobre partes del recurso. El objetivo del corte de pastel igualitario es maximizar el valor más pequeño de un agente; sujeto a esto, maximizar el siguiente valor más pequeño; y así sucesivamente. También se llama corte de pastel leximin , ya que la optimización se realiza utilizando el orden leximin en los vectores de utilidades.
El concepto de reparto igualitario de los beneficios fue descrito por primera vez por Dubins y Spanier , quienes lo llamaron "partición óptima". [1]
Las asignaciones óptimas de leximin existen siempre que el conjunto de asignaciones sea un espacio compacto . Este es siempre el caso cuando se asignan objetos discretos, y es fácil de demostrar cuando se asigna 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, las asignaciones de pastel óptimas de leximin siempre existen. Por esta razón, la regla de asignación de pastel de leximin a veces se denomina regla de Dubins-Spanier . [2]
Cuando las valoraciones de los agentes no están normalizadas (es decir, diferentes agentes pueden asignar un valor diferente a toda la torta), 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-máximo, y la regla leximin relativa elige una asignación en la que el perfil de utilidad relativa es leximin-máximo.
Ambas variantes de la regla leximin son óptimas en el sentido de Pareto y monótonas en términos de población . Sin embargo, difieren en otras propiedades: [3]
Ambas variantes de la regla leximin pueden dar lugar a asignaciones que no estén libres de envidia . Por ejemplo, supongamos que hay 5 agentes, que la torta es homogénea por partes con 3 regiones y que las valoraciones de los agentes son (los valores faltantes son ceros):
Todos los agentes valoran la torta entera en 15, por lo que el leximin absoluto y el leximin relativo son equivalentes. El valor mínimo posible más grande es 5, por lo que una asignación de leximin debe dar a todos los agentes al menos 5. Esto significa que la Derecha debe dividirse equitativamente entre los agentes C, D, E, y el Medio debe darse en su totalidad 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 relativa-leximin está libre de envidia. [4] : Sec.4
Weller [4] : La sección 4 mostró una asignación de torta eficiente y sin envidia que no es relativa-leximin. La torta 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 utilitarista -ó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 leximin-óptima.
Aumann, Dombb y Hassidim [5] presentan un algoritmo que, para cada e > 0, calcula una asignación con un bienestar igualitario al menos (1-e) del óptimo mediante consultas. Esto es exponencial en n , pero polinomial en el número de dígitos de precisión.
Por otra parte, demuestran que, a menos que P=NP, es imposible aproximar el valor igualitario óptimo a un factor mejor que 2, en un polinomio de tiempo en n . La prueba es por reducción a partir de emparejamiento tridimensional (3DM). Para cada instancia de emparejamiento tridimensional con m hiperaristas, construyen una instancia de corte de torta con n agentes, donde 4 m ≤ n ≤ 5 m . Demuestran que, si la instancia de 3DM admite un emparejamiento perfecto, entonces existe una asignación de torta con valor igualitario al menos 1/ m ; de lo contrario, no hay asignación de torta con valor igualitario mayor que 1/(2 m ).
