El corte de pastel utilitario (también llamado corte de pastel maxsum ) es una regla para dividir un recurso heterogéneo, como un pastel o una finca, entre varios socios con diferentes funciones de utilidad cardinales , de modo que la suma de las utilidades de los socios es lo más grande posible. Está inspirado en la filosofía utilitaria . Cortar pasteles utilitarios a menudo no es "justo"; por lo tanto, el utilitarismo está en conflicto con el corte justo de pasteles .
Ejemplo
Piense en una tarta con dos partes: chocolate y vainilla, y dos socios: Alice y George, con las siguientes valoraciones:
Pareja | Chocolate | Vainilla |
---|---|---|
Alicia | 9 | 1 |
Jorge | 6 | 4 |
La regla utilitarista otorga cada parte al socio de mayor utilidad. En este caso, la regla utilitaria 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á libre de envidia ya que George envidia a Alice.
Notación
El pastel se llama . Por lo general, se supone que es un segmento unidimensional finito, un polígono bidimensional o un subconjunto finito del plano euclidiano multidimensional..
Existen socios. Cada socio tiene una función de valor personal que mapea subconjuntos de ("piezas") a números.
tiene que ser dividido para piezas disjuntas, una pieza por socio. La pieza asignada al socio se llama , y .
Una division se llama utilitario o utilitario-máximo o maxsum si maximiza la siguiente expresión:
El concepto a menudo se generaliza asignando un peso diferente a cada socio. Una divisionse llama ponderado-utilitario-máximo (WUM) si maximiza la siguiente expresión:
donde el se les dan constantes positivas.
Maxsum y Pareto-eficiencia
Cada división WUM con pesos positivos es obviamente Pareto-eficiente . Esto se debe a que, si una división Pareto-domina una división , luego la suma ponderada de utilidades en es estrictamente más grande que en , entonces no puede ser una división WUM.
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 maxsum
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 :
- Pareto-eficiencia (PE) : la regla R devuelve solo divisiones que son Pareto-eficientes.
- Independencia División (DI) : siempre que un pastel se reparte a varios sub-tortas y cada torta se divide de acuerdo con la regla R , el resultado es el mismo que si la torta original, se repartieron de acuerdo con R .
- Independencia de la tierra inviable (IIL) : siempre que un sub-pastel se divide de acuerdo con R , el resultado no depende de las utilidades de los socios en los otros sub-tortas.
- Tratamiento positivo de iguales (PTE) : siempre que todos los socios tengan la misma función de utilidad, R recomienda al menos una división que dé una utilidad positiva a cada socio.
- Invarianza de escala (SI) : 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 un pedazo fijo de pastel, el conjunto de perfiles de servicios públicos que se asignan a una asignación específica es un conjunto cerrado bajo convergencia puntual .
Lo siguiente está probado para los socios que asignan una utilidad positiva a cada pedazo de pastel con un tamaño positivo:
- Si R es PE DI e IIL, entonces existe una secuencia de pesosde 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 desprende de la propiedad DI).
- Si R es PE DI IIL y PTE, entonces todas las divisiones recomendadas por R son utilitarias-máximas (en otras palabras, todas las divisiones deben ser WUM y todos los agentes deben tener pesos iguales. Esto se deriva 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 pesosde modo que R es una regla WUM con estos pesos (es decir, R recomienda todas y solo las divisiones WUM con estos pesos).
Encontrar divisiones de suma máxima
Piezas desconectadas
Cuando las funciones de valor son aditivas, siempre existen divisiones de suma máxima. De forma intuitiva, podemos entregar cada fracción del bizcocho al socio que más la valore, como en el ejemplo anterior . De manera similar, las divisiones de WUM se pueden encontrar dando cada fracción del pastel al socio para quien la razón es más grande.
Este proceso es fácil de realizar cuando la torta es homogénea por partes , es decir, la torta se puede dividir en un número finito de piezas de modo que la densidad de valor de cada pieza 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 "piezas" diferentes a considerar.
Las divisiones de Maxsum todavía existen. Este es un corolario del teorema de compacidad de Dubins-Spanier y también puede demostrarse utilizando el conjunto 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 sólo 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. Suponga que el algoritmo se ha detenido después de tener datos de valor sobresubconjuntos. Ahora bien, puede darse 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 puede alcanzar el algoritmo es 1. Sin embargo, es posible que en el fondo de uno de lospiezas, 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, 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 estar conectadas, el simple algoritmo de asignar cada pieza al agente que más la valora ya no funciona, incluso cuando las piezas son piezas constantes. En este caso, el problema de encontrar una división UM es NP-difícil y, además, no es posible FPTAS a menos que P = NP.
Hay un algoritmo de aproximación de 8 factores y un algoritmo manejable 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 y se puede encontrar de manera similar.
Maxsum y equidad
Una división de suma máxima no siempre es justa; vea el ejemplo anterior . Del mismo modo, una división justa no siempre es máxima.
Un enfoque para este conflicto es limitar el "precio de la equidad": calcular los límites superior e inferior de la cantidad de disminución en la suma de los servicios públicos, que se requiere para la equidad. Para obtener más detalles, consulte el precio de la equidad .
Otro enfoque para combinar eficiencia y equidad es encontrar, entre todas las posibles divisiones justas, una división justa con la mayor suma de utilidades:
Encontrar asignaciones máximas justas
Los siguientes algoritmos se pueden utilizar para encontrar un corte de pastel sin envidia con la máxima suma 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 socios con valoraciones constantes por partes : divida la torta en m regiones totalmente constantes. Resuelva un programa lineal con nm variables: cada par (agente, región) tiene una variable que determina la fracción de la región dada 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. Tenga en cuenta que la asignación producida por este procedimiento puede estar muy fraccionada.
- Para socios con valoraciones lineales por partes : para cada punto del pastel, calcule la relación entre las utilidades:. Dale al socio 1 los puntos con y asocia 2 los puntos con , dónde es un umbral calculado para 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, puede aproximarse 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 alcanza una suma que es al menos la suma máxima de una asignación de EF. Su tiempo de ejecución es polinomio en la entrada y en.
- Para socios con valoraciones generales: aproximación aditiva a la envidia y eficiencia, basada en el algoritmo de valoraciones constantes por partes.
Propiedades de las asignaciones maxsum-fair
[7] estudian lasdivisiones de pastelsin envidia (EF) y equitativas (EQ), y las relacionan con la suma máxima y la optimización de Pareto (PO). Como se explicó anteriormente, las asignaciones de suma máxima son siempre PO. Sin embargo, cuando maxsum está limitado 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 son siempre PO.
- Cuando hay tres o más agentes con valoraciones uniformes por partes , las asignaciones maxsum-EF son siempre PO (ya que EF es equivalente a proporcionalidad , que se conserva con las mejoras de Pareto). Sin embargo, es posible 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 máxima suma-EF que sean PO. Por ejemplo, considere un pastel con tres regiones y tres agentes con valores: Alice : 51/101, 50/101, 0 Bob : 50/101, 51/101, 0 Carl : 51/111, 10/111, 50/111 La regla de la suma máxima le da la región i al agente i, pero no es EF ya que Carl envidia a Alice. Usando un programa lineal, es posible encontrar la asignación única maxsum-EF y mostrar 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 beneficiarse intercambiando sus acciones en estas regiones.
- Cuando todos los agentes tienen valoraciones lineales por partes , la suma de la utilidad de una asignación máxima-suma-EF es al menos tan grande como una asignación máxima-suma-EQ. Este resultado se extiende a valoraciones generales hasta una aproximación aditiva (es decir,-Las asignaciones de EF tienen una suma de utilidad de al menos asignaciones de EQ menos ).
Ver también
- Cálculo felicífico : un intento de definir las utilidades mediante una fórmula matemática.
- Corte eficiente de pasteles
- Corte justo de pasteles
- Teorema de Weller
- División sin envidia pareto-eficiente
- Asignación máxima de rango
Referencias
- ↑ Barbanel, Julius B .; Zwicker, William S. (1997). "Dos aplicaciones de un teorema de Dvoretsky, Wald y Wolfovitz a la división de pasteles". Teoría y Decisión . 43 (2): 203. doi : 10.1023 / a: 1004966624893 . S2CID 118505359 .. Véase también el teorema de Weller . Para obtener un resultado similar relacionado con el problema de la asignación homogénea de recursos, consulte los teoremas de Varian .
- ^ Cámaras, Christopher P. (2005). "Reglas de asignación para la división de tierras". Revista de teoría económica . 121 (2): 236–258. doi : 10.1016 / j.jet.2004.04.008 .
- ^ Brams, Steven J .; Taylor, Alan D. (1996). División justa [ Del corte de pasteles a la resolución de disputas ]. pag. 48. ISBN 978-0521556446.
- ^ Ianovski, Egor (1 de marzo de 2012). "Mecanismos de corte de tartas". arXiv : 1203.0100 [ cs.GT ].
- ^ Aumann, Yonatan; Dombb, Yair; Hassidim, Avinatan (2013). Computación de divisiones de pastel socialmente eficientes . AAMAS.
- ^ Cohler, Yuga Julian; Lai, John Kwang; Parkes, David C; Procaccia, Ariel (2011). Corte de pastel óptimo sin envidia . AAAI.
- ^ Steven J. Brams; Michal Feldman ; John K. Lai; Jamie Morgenstern; Ariel D. Procaccia (2012). En las divisiones de pasteles de la feria Maxsum . Actas de la 26ª Conferencia AAAI sobre Inteligencia Artificial (AAAI-12). págs. 1285-1291 . Consultado el 6 de diciembre de 2015 .