Corte de pastel utilitario

El reparto utilitarista de un recurso (también llamado reparto de máxima utilidad ) es una regla para dividir un recurso heterogéneo, como un pastel o una propiedad, entre varios socios con diferentes funciones de utilidad cardinales , de manera 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 utilitarista . El reparto utilitarista a menudo no es "justo"; por lo tanto, el utilitarismo suele estar en conflicto con el reparto justo .

Ejemplo

Consideremos un pastel con dos partes: chocolate y vainilla, y dos socios: Alice y George, con las siguientes valoraciones:

La regla utilitarista asigna cada parte al socio con la mayor utilidad. En este caso, la regla utilitarista le da todo el chocolate a Alice y toda la vainilla a George. 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á exenta de envidia, puesto que George envidia a Alice.

Notación

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

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

$C$ tiene que dividirse en $n$ piezas disjuntas, una pieza por socio. La pieza asignada al socio $i$ se llama $X_{i}$ , y $C=X_{1}\sqcup ...\sqcup X_{n}$ .

Una división $X$ Se denomina utilitario , utilitario-maximal o maxsum si maximiza la siguiente expresión:

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

El concepto se suele generalizar asignando un peso diferente a cada socio. Una división $X$ Se denomina ponderado-utilitario-maximal (WUM) si maximiza la siguiente expresión:

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

donde el $w_{i}$ se les dan constantes positivas.

Suma máxima y eficiencia de Pareto

Cada división WUM con pesos positivos es obviamente Pareto-eficiente . Esto se debe a que, si una división $Y$ Pareto domina una división $X$ , entonces la suma ponderada de utilidades en $Y$ es estrictamente más grande que en $X$ , entonces $X$ no puede ser una división de WUM.

Lo 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 sugiere 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 devuelve solo las divisiones que son eficientes en el sentido de Pareto.
Independencia de división (DI) : siempre que un pastel se divide en varios subpasteles y cada pastel se divide según la regla R , el resultado es el mismo que si el pastel original se hubiera dividido según R.
Independencia de tierras inviables (IIL) : siempre que una subtarta se divide según R , el resultado no depende de las utilidades de los socios en las otras subtartas.
Tratamiento positivo de iguales (TPI) : 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 (IE) : siempre que las funciones de utilidad de los socios se multipliquen 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 se corresponden con una asignación específica es un conjunto cerrado bajo convergencia puntual .

Se demuestra lo siguiente para socios que asignan una utilidad positiva a cada trozo de pastel de tamaño positivo:

Si R es PE DI e IIL, entonces existe una secuencia de pesos $w_{1},\dots,w_{n}$ De tal manera 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 deduce de la propiedad DI).
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 deduce 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 $w_{1},\dots,w_{n}$ de tal manera que R sea una regla WUM con estos pesos (es decir, R recomienda todas y solo las divisiones WUM con estos pesos).

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 del pastel al socio que más lo valora, como en el ejemplo anterior . De manera similar, las divisiones WUM se pueden encontrar dando cada fracción del pastel al socio para quien la proporción $V_{i}/w_{i}$ es el más grande.

Este proceso es fácil de llevar a cabo cuando el pastel es homogéneo por partes , es decir, el pastel se puede dividir en un número finito de trozos de tal manera que la densidad de valor de cada trozo sea constante para todos los socios.

Cuando el pastel no es homogéneo por partes, el algoritmo anterior no funciona, ya que hay un número infinito de "partes" diferentes a considerar.

Las divisiones Maxsum aún existen. Esto 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 valor solo sobre un número finito de piezas. Es decir, solo hay un número finito de subconjuntos del pastel, para los cuales el algoritmo conoce las valoraciones de los socios. Supongamos que el algoritmo se ha detenido después de tener datos de valor sobre $k$ subconjuntos. Ahora bien, puede darse el caso de que todos los socios respondieran a 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 el fondo de uno de los $k$ piezas, hay un subconjunto que dos socios valoran de manera diferente. En este caso, existe una división superproporcional , en la que cada socio recibe un valor de más de $1/n$ , por lo que la suma de utilidades es estrictamente mayor que 1. Por lo tanto, la división devuelta por el algoritmo finito no es maxsum.

Piezas conectadas

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

Existe un algoritmo de aproximación de 8 factores y un algoritmo tratable de parámetros fijos que es exponencial en el número de jugadores. ^{[ 5 ]}

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

Suma máxima y equidad

Una división por suma máxima no siempre es justa; véase el ejemplo anterior . Del mismo modo, una división justa no siempre es por suma máxima.

Una forma de abordar este conflicto es establecer límites al "precio de la equidad": calcular límites superiores e inferiores para la disminución de la suma de utilidades necesaria para lograr la equidad. Para más detalles, consulte el apartado sobre el precio de la equidad .

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

Encontrar asignaciones utilitarias justas

Los siguientes algoritmos pueden utilizarse para encontrar un corte de pastel sin envidia con suma máxima de utilidades, para un pastel que es un intervalo unidimensional, cuando cada persona puede recibir piezas desconectadas y las funciones de valor son aditivas: ^{[ 6 ]}

Para $n$ Socios con valoraciones constantes por partes : divide el pastel en m regiones totalmente constantes. Resuelve un programa lineal con nm variables: cada par (agente, región) tiene una variable que determina la fracción de la región asignada al agente. Para cada región, existe una restricción que establece que la suma de todas las fracciones de esta región es 1; para cada par (agente, agente), existe una restricción que establece que el primer agente no envidia al segundo. Ten en cuenta que la asignación producida por este procedimiento podría estar muy fraccionada.
Para $2$ socios con valoraciones lineales por partes : para cada punto del pastel, calcule la relación entre las utilidades: $r=u_{1}/u_{2}$ . Dale al compañero 1 los puntos con $r\geq r^{*}$ y socio 2 los puntos con $r<r^{*}$ , dónde $r^{*}$ es un umbral calculado de manera que la división esté libre de envidia. En general $r^{*}$ no se puede calcular porque podría ser irracional, pero en la práctica, cuando las valoraciones son lineales por partes, $r^{*}$ puede aproximarse mediante un algoritmo de aproximación de "búsqueda irracional". Para cualquier $\epsilon >0$ , El algoritmo encuentra una asignación que es $\epsilon$ -EF (el valor de cada agente es al menos el valor de cada otro agente menos $\epsilon$ ), y alcanza una suma que es al menos la suma máxima de una asignación de EF. Su tiempo de ejecución es polinomial en la entrada y en $\log(1/\epsilon)$ .
Para $n$ Socios con valoraciones generales: aproximación aditiva a la envidia y la eficiencia, basada en el algoritmo de valoraciones constantes por partes.

Propiedades de las asignaciones utilitaristas justas

Brams, Feldman, Lai, Morgenstern y Procaccia ^{[ 7 ]} estudian las divisiones de pasteles libres de envidia (EF) y equitativas (EQ), y las relacionan con la suma máxima y la optimalidad de Pareto (PO). Como se explicó anteriormente, las asignaciones de suma máxima siempre son PO. Sin embargo, cuando la suma máxima está restringida 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 bajo mejoras de Pareto). Sin embargo, puede que no existan asignaciones maxsum-EQ ni maxsum-EQ-EF que sean PO.
Cuando hay tres o más agentes con valoraciones constantes por partes , puede que incluso no haya asignaciones maxsum-EF que sean PO. Por ejemplo, consideremos un pastel con tres regiones y tres agentes con valores:

La regla maxsum asigna 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 única asignación maxsum-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 tanto Alice como Bob podrían beneficiarse intercambiando sus participaciones en estas regiones.

Cuando todos los agentes tienen valoraciones lineales por partes , la suma de utilidad de una asignación maxsum-EF es al menos tan grande como una asignación maxsum-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 las asignaciones EQ − $ε$ ).

Propiedades de monotonicidad del corte de pasteles utilitario

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

Esto ya no se cumple cuando las piezas están conectadas. ^{[ 9 ]}

Véase también

Corte de pastel eficiente
Corte de pastel de feria
Teorema de Weller
División libre de envidia y eficiente según Pareto
asignación de rango máximo
Voto utilitarista : el principio utilitarista en un contexto diferente.

Referencias

↑ Barbanel, Julius B.; Zwicker, William S. (1997). "Dos aplicaciones de un teorema de Dvoretsky, Wald y Wolfovitz a la división de pasteles". Theory and Decision . 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 .
↑ 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 .
↑ Brams, Steven J.; Taylor, Alan D. (1996). División justa [ De la división de bienes a la resolución de disputas ] . pág. 48. ISBN 978-0521556446.
↑ Ianovski, Egor (2012-03-01). "Mecanismos de corte de pasteles". arXiv : 1203.0100 [ cs.GT ].
↑ Aumann, Yonatan; Dombb, Yair; Hassidim, Avinatan (2013). Cálculo de divisiones de pasteles socialmente eficientes . AAMAS.
↑ Cohler, Yuga Julian; Lai, John Kwang; Parkes, David C; Procaccia, Ariel (2011). Corte óptimo de pastel sin envidia . AAAI.
↑ Steven J. Brams; Michal Feldman ; John K. Lai; Jamie Morgenstern ; Ariel D. Procaccia (2012). Sobre las divisiones de pasteles justos de suma máxima . Actas de la 26.ª Conferencia AAAI sobre Inteligencia Artificial (AAAI-12). págs. 1285–1291 . Recuperado el 6 de diciembre de 2015 .
^ 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 .
^ 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 .

[1] Barbanel, Julius B.; Zwicker, William S. (1997). "Dos aplicaciones de un teorema de Dvoretsky, Wald y Wolfovitz a la división de pasteles". Theory and Decision . 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 .

[Chambers-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 .

[bt96-3] Brams, Steven J.; Taylor, Alan D. (1996). División justa [ De la división de bienes a la resolución de disputas ] . pág. 48. ISBN 978-0521556446.

[4] Ianovski, Egor (2012-03-01). "Mecanismos de corte de pasteles". arXiv : 1203.0100 [ cs.GT ].

[adh13-5] Aumann, Yonatan; Dombb, Yair; Hassidim, Avinatan (2013). Cálculo de divisiones de pasteles socialmente eficientes . AAMAS.

[clpp11-6] Cohler, Yuga Julian; Lai, John Kwang; Parkes, David C; Procaccia, Ariel (2011). Corte óptimo de pastel sin envidia . AAAI.

[7] Steven J. Brams; Michal Feldman ; John K. Lai; Jamie Morgenstern ; Ariel D. Procaccia (2012). Sobre las divisiones de pasteles justos de suma máxima . Actas de la 26.ª Conferencia AAAI sobre Inteligencia Artificial (AAAI-12). págs. 1285–1291 . Recuperado 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 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]