Corte de pastel utilitario

El reparto utilitario de la torta (también llamado reparto de la torta de suma máxima ) es una regla para dividir un recurso heterogéneo, como una torta o una finca, entre varios socios con diferentes funciones de utilidad cardinal , de modo que la suma de las utilidades de los socios sea lo más grande posible. Es un caso especial de la regla de elección social utilitaria . El reparto utilitario de la torta a menudo no es "justo"; por lo tanto, el utilitarismo a menudo está en conflicto con el reparto justo de la torta .

Ejemplo

Consideremos un pastel con dos partes: chocolate y vainilla, y dos socios: Alicia y Jorge, con las siguientes valoraciones:

La regla utilitaria otorga cada parte al socio que tenga la mayor utilidad. En este caso, la regla utilitaria otorga todo el chocolate a Alicia y toda la vainilla a Jorge. La suma máxima es 13.

La división utilitaria no es justa: no es proporcional ya que George recibe menos de la mitad del valor total del pastel, y no está libre de envidia ya que George envidia a Alice.

Notación

La torta se llama . Generalmente se supone que es un segmento unidimensional finito, un polígono bidimensional o un subconjunto finito del plano euclidiano multidimensional . ${\displaystyle C}$ ${\displaystyle \mathbb {R} ^{d}}$

Hay socios. Cada socio tiene una función de valor personal que asigna subconjuntos de ("piezas") a números. ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle V_{i}}$ ${\displaystyle C}$

${\displaystyle C}$debe dividirse en partes disjuntas, una pieza por compañero. La pieza asignada al compañero se llama , y . ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle X_{i}}$ ${\displaystyle C=X_{1}\sqcup ...\sqcup X_{n}}$

Una división se llama utilitaria o utilitarista-maximal o maxsum si maximiza la siguiente expresión: ${\displaystyle X}$

${\displaystyle \sum _{i=1}^{n}{V_{i}(X_{i})}}$

El concepto suele generalizarse asignando un peso diferente a cada socio. Una división se denomina utilitarista ponderada máxima (WUM) si maximiza la siguiente expresión: ${\displaystyle X}$

${\displaystyle \sum _{i=1}^{n}{\frac {V_{i}(X_{i})}{w_{i}}}}$

donde se dan constantes positivas. ${\displaystyle w_{i}}$

Maxsum y eficiencia de Pareto

Obviamente, toda división WUM con ponderaciones positivas es eficiente en el sentido de Pareto . Esto se debe a que, si una división domina en el sentido de Pareto a una división , entonces la suma ponderada de utilidades en es estrictamente mayor que en , por lo que no puede ser una división WUM. ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle X}$

Lo que es más sorprendente es que cada división Pareto-eficiente es WUM para alguna selección de pesos. ^[1]

Caracterización de la regla utilitarista

Christopher P. Chambers propone una caracterización de la regla WUM. ^[2] La caracterización se basa en las siguientes propiedades de una regla de división R :

• Eficiencia de Pareto (EP) : la regla R solo devuelve divisiones que son eficientes en el sentido de Pareto.
• Independencia de división (DI) : siempre que una torta se divide en varias subtortas y cada torta se divide según la regla R , el resultado es el mismo que si la torta original se dividiera según R.
• Independencia de las tierras inviables (IIL) : siempre que una subtorta se divida según R , el resultado no depende de las utilidades de los socios en las otras subtortas.
• Trato positivo entre iguales (PTE) : siempre que todos los socios tengan la misma función de utilidad, R recomienda al menos una división que proporcione una utilidad positiva a cada socio.
• Invariancia de escala (IS) : siempre que las funciones de utilidad de los socios se multiplican por constantes (una constante posiblemente diferente para cada socio), las recomendaciones dadas por R no cambian.
• Continuidad (CO) : para una porción fija de pastel, el conjunto de perfiles de utilidad que corresponden a una asignación específica es un conjunto cerrado bajo convergencia puntual .

Lo siguiente queda demostrado para los socios que asignan utilidad positiva a cada trozo de tarta de tamaño positivo:

• Si R es PE DI y IIL, entonces existe una secuencia de pesos tales que todas las divisiones recomendadas por R son WUM con estos pesos (se sabe que cada división PE es WUM con algunos pesos; la novedad es que todas las divisiones recomendadas por R son WUM con los mismos pesos. Esto se desprende de la propiedad DI). ${\displaystyle w_{1},\dots ,w_{n}}$
• Si R es PE DI IIL y PTE, entonces todas las divisiones recomendadas por R son utilitaristas-maximales (en otras palabras, todas las divisiones deben ser WUM y todos los agentes deben tener pesos iguales. Esto se desprende de la propiedad PTE).
• Si R es PE DI IIL y SI, entonces R es una regla dictatorial: le da todo el pastel a un solo socio.
• Si R es PE DI IIL y CO, entonces existe una secuencia de pesos tal que R es una regla WUM con estos pesos (es decir, R recomienda todas y solo las divisiones WUM con estos pesos). ${\displaystyle w_{1},\dots ,w_{n}}$

Encontrar divisiones utilitarias

Piezas desconectadas

Cuando las funciones de valor son aditivas, siempre existen divisiones de suma máxima. Intuitivamente, podemos dar cada fracción de la torta al socio que la valora más, como en el ejemplo anterior. De manera similar, las divisiones de suma máxima se pueden encontrar dando cada fracción de la torta al socio para quien la proporción es mayor. ${\displaystyle V_{i}/w_{i}}$

Este proceso es fácil de llevar a cabo cuando la torta es homogénea en partes , es decir, la torta se puede dividir en un número finito de partes tales que la densidad de valor de cada parte sea constante para todos los socios.

Cuando la torta no es homogénea en todas sus partes, el algoritmo anterior no funciona ya que hay un número infinito de "partes" diferentes a considerar.

Todavía existen divisiones Maxsum. Este es un corolario del teorema de compacidad de Dubins-Spanier y también se puede demostrar utilizando el conjunto de Radon-Nikodym .

Sin embargo, ningún algoritmo finito puede encontrar una división de suma máxima. Prueba : ^{[3] [4] : ​​Cor.2} Un algoritmo finito tiene datos de valores solo sobre un número finito de piezas. Es decir, solo hay un número finito de subconjuntos de la tarta, para los que el algoritmo conoce las valoraciones de los socios. Supongamos que el algoritmo se ha detenido después de tener datos de valores sobre subconjuntos. Ahora, puede ser el caso de que todos los socios respondieran todas las consultas como si tuvieran la misma medida de valor. En este caso, el mayor valor utilitario posible que el algoritmo puede alcanzar es 1. Sin embargo, es posible que en lo profundo de una de las piezas, haya un subconjunto que dos socios valoren de forma diferente. En este caso, existe una división superproporcional , en la que cada socio recibe un valor de más de , por lo que la suma de utilidades es estrictamente mayor que 1. Por tanto, la división devuelta por el algoritmo finito no es de suma máxima. ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 1/n}$

Piezas conectadas

Cuando la torta es unidimensional y las piezas deben estar conectadas, el algoritmo simple de asignar cada pieza al agente que la valora más ya no funciona, incluso con valoraciones constantes por partes . En este caso, el problema de encontrar una división UM es NP-hard y, además, no es posible ninguna FPTAS a menos que P=NP.

Hay un algoritmo de aproximación de 8 factores y un algoritmo manejable con parámetros fijos que es exponencial en el número de jugadores. ^[5]

Para cada conjunto de pesos positivos, existe una división WUM y se puede encontrar de manera similar.

Máxima suma y equidad

Una división de suma máxima no siempre es justa; vea el ejemplo anterior. De manera similar, una división justa no siempre es de suma máxima.

Una forma de abordar este conflicto es limitar el "precio de la justicia": calcular límites superiores e inferiores para la cantidad de disminución de la suma de utilidades que se requiere para que haya justicia. Para más detalles, véase precio de la justicia .

Otro enfoque para combinar eficiencia y equidad es encontrar, entre todas las divisiones justas posibles, una división justa con la mayor suma de utilidades:

Encontrar asignaciones utilitaristas justas

Los siguientes algoritmos se pueden utilizar para encontrar un corte de pastel sin envidia con una suma máxima de utilidades, para un pastel que es un intervalo unidimensional, cuando cada persona puede recibir pedazos desconectados y las funciones de valor son aditivas: ^[6]

1. Para socios con valoraciones constantes por partes : dividir la torta en m regiones totalmente constantes. Resolver un programa lineal con nm variables: cada par (agente, región) tiene una variable que determina la fracción de la región que se le da al agente. Para cada región, hay una restricción que dice que la suma de todas las fracciones de esta región es 1; para cada par (agente, agente), hay una restricción que dice que el primer agente no envidia al segundo. Nótese que la asignación producida por este procedimiento puede estar altamente fraccionada. ${\displaystyle n}$
2. Para socios con valoraciones lineales por partes : para cada punto del pastel, calcule la relación entre las utilidades: . Dé al socio 1 los puntos con y al socio 2 los puntos con , donde es un umbral calculado de modo que la división esté libre de envidia. En general, no se puede calcular porque podría ser irracional, pero en la práctica, cuando las valoraciones son lineales por partes, se puede aproximar mediante un algoritmo de aproximación de "búsqueda irracional". Para cualquier , el algoritmo encuentra una asignación que es -EF (el valor de cada agente es al menos el valor de cada otro agente menos ), y obtiene una suma que es al menos la suma máxima de una asignación EF. Su tiempo de ejecución es polinomial en la entrada y en . ${\displaystyle 2}$ ${\displaystyle r=u_{1}/u_{2}}$ ${\displaystyle r\geq r^{*}}$ ${\displaystyle r<r^{*}}$ ${\displaystyle r^{*}}$ ${\displaystyle r^{*}}$ ${\displaystyle r^{*}}$ ${\displaystyle \epsilon >0}$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$ ${\displaystyle \log(1/\epsilon )}$
3. Para socios con valoraciones generales: aproximación aditiva a la envidia y la eficiencia, basada en el algoritmo de valoraciones constantes por partes. ${\displaystyle n}$

Propiedades de las asignaciones utilitaristas-justas

Brams, Feldman, Lai, Morgenstern y Procaccia ^[7] estudian las asignaciones de tortas tanto sin envidia (EF) como equitativas (EQ), y las relacionan con la máxima suma y la óptima de Pareto (PO). Como se explicó anteriormente, las asignaciones de máxima suma siempre son PO. Sin embargo, cuando la máxima suma está limitada por la equidad, esto no es necesariamente cierto. Demuestran lo siguiente:

• Cuando hay dos agentes, las asignaciones maxsum-EF, maximum-EQ y maximum-EF-EQ siempre son PO.
• Cuando hay tres o más agentes con valoraciones uniformes por partes , las asignaciones maxsum-EF siempre son PO (ya que EF es equivalente a la proporcionalidad , que se conserva en virtud de las mejoras de Pareto). Sin embargo, puede que no haya asignaciones maxsum-EQ y maxsum-EQ-EF que sean PO.
• Cuando hay tres o más agentes con valoraciones constantes por partes , es posible que ni siquiera haya asignaciones de EF de suma máxima que sean PO. Por ejemplo, considere una torta con tres regiones y tres agentes con valores:

La regla de suma máxima otorga la región i al agente i, pero no es EF ya que Carl envidia a Alice. Mediante un programa lineal, es posible encontrar la asignación única de suma máxima-EF y demostrar que debe compartir tanto la región 1 como la región 2 entre Alice y Bob. Sin embargo, dicha asignación no puede ser PO ya que Alice y Bob podrían ganar si intercambian sus participaciones en estas regiones.

• Cuando todos los agentes tienen valoraciones lineales por partes , la suma de utilidad de una asignación de suma máxima-EF es al menos tan grande como una asignación de suma máxima-EQ. Este resultado se extiende a valoraciones generales hasta una aproximación aditiva (es decir, las asignaciones ε -EF tienen una suma de utilidad de al menos asignaciones EQ − ε ).

Propiedades de monotonía del corte de pastel utilitario

Cuando las piezas pueden desconectarse , la regla utilitarista absoluta (que maximiza la suma de utilidades no normalizadas) es monótona respecto de los recursos y de la población . La regla utilitarista relativa (que maximiza la suma de utilidades normalizadas) es monótona respecto de la población, pero no respecto de los recursos. ^[8]

Esto ya no es válido cuando las piezas están conectadas. ^[9]

Véase también

• Corte de pastel eficiente
• Corte de pastel justo
• Teorema de Weller
• División libre de envidia y eficiencia de Pareto
• Asignación de rango máximo
• Voto utilitario : el principio utilitario en un contexto diferente.

Referencias

1. Barbanel, Julius B.; Zwicker, William S. (1997). "Dos aplicaciones de un teorema de Dvoretsky, Wald y Wolfovitz a la división de tortas". Teoría y decisión . 43 (2): 203. doi :10.1023/a:1004966624893. S2CID  118505359.Véase también el teorema de Weller . Para un resultado similar relacionado con el problema de la asignación homogénea de recursos, véanse los teoremas de Varian .
2. Chambers, Christopher P. (2005). "Reglas de asignación para la división de tierras". Journal of Economic Theory . 121 (2): 236–258. doi :10.1016/j.jet.2004.04.008.
3. Brams, Steven J.; Taylor, Alan D. (1996). Fair Division [ Del corte de la torta a la resolución de disputas ]. p. 48. ISBN 978-0521556446.
4. Ianovski, Egor (1 de marzo de 2012). "Mecanismos de corte de tortas". arXiv : 1203.0100 [cs.GT].
5. Aumann, Yonatan; Dombb, Yair; Hassidim, Avinatan (2013). Cálculo de divisiones de pasteles socialmente eficientes. AAMAS.
6. Cohler, Yuga Julian; Lai, John Kwang; Parkes, David C; Procaccia, Ariel (2011). Corte de pastel óptimo sin envidia. AAAI.
7. Steven J. Brams; Michal Feldman ; John K. Lai; Jamie Morgenstern; Ariel D. Procaccia (2012). On Maxsum Fair Cake Divisions. Actas de la 26.ª Conferencia AAAI sobre Inteligencia Artificial (AAAI-12). págs. 1285–1291 . Consultado el 6 de diciembre de 2015 .
8. Segal-Halevi, Erel; Sziklai, Balázs R. (1 de septiembre de 2019). "Monotonicidad y equilibrio competitivo en el corte de tartas". Teoría Económica . 68 (2): 363–401. arXiv : 1510.05229 . doi :10.1007/s00199-018-1128-6. ISSN  1432-0479. S2CID  179618.
9. Segal-Halevi, Erel; Sziklai, Balázs R. (1 de septiembre de 2018). "Monotonicidad de recursos y monotonicidad de población en el corte de pasteles conectado". Ciencias Sociales Matemáticas . 95 : 19–30. arXiv : 1703.08928 . doi :10.1016/j.mathsocsci.2018.07.001. ISSN  0165-4896. S2CID  16282641.