El teorema de Weller [1] es un teorema en economía . Dice que un recurso heterogéneo ("pastel") se puede dividir entre n socios con diferentes valoraciones de una manera que es tanto Pareto-eficiente (PE) como libre de envidia (EF). Por lo tanto, es posible dividir un pastel de manera justa sin comprometer la eficiencia económica.
Además, el teorema de Weller dice que existe un precio tal que la asignación y el precio son un equilibrio competitivo (CE) con ingresos iguales (EI). Por lo tanto, conecta dos campos de investigación que antes no estaban relacionados: el corte justo y el equilibrio general .
Fondo
El corte justo de pasteles se ha estudiado desde la década de 1940. Existe un recurso heterogéneo divisible, como un pastel o una finca. Hay n socios, cada uno de los cuales tiene una función de densidad de valor personal sobre el pastel. El valor de una pieza para un socio es la integral de su densidad de valor sobre esa pieza (esto significa que el valor es una medida no atómica sobre el pastel). El problema de cortar el pastel sin envidia es dividir el pastel en n piezas separadas, una pieza por agente, de modo que para cada agente, el valor de su pieza es débilmente mayor que los valores de todas las demás piezas (por lo que ningún agente envidia el de otro agente). Cuota).
Un corolario del teorema de la convexidad de Dubins-Spanier (1961) es que siempre existe una "partición de consenso", una partición del pastel en n trozos, de modo que cada agente valora cada trozo como exactamente. Una partición de consenso es, por supuesto, EF, pero no es PE. Además, otro corolario del teorema de la convexidad de Dubins-Spanier es que, cuando al menos dos agentes tienen medidas de valor diferentes, existe una división que da a cada agente estrictamente más de. Esto significa que la partición de consenso no es ni siquiera débilmente PE.
La ausencia de envidia, como criterio para la asignación justa, se introdujo en la economía en la década de 1960 y se estudió intensamente durante la década de 1970. Los teoremas de Varian lo estudian en el contexto de la división de bienes homogéneos . Bajo restricciones leves en las funciones de utilidad de los agentes, existen asignaciones que son tanto PE como EF. La prueba utiliza un resultado anterior sobre la existencia de un equilibrio competitivo de ingresos iguales (CEEI). David Gale demostró un resultado de existencia similar para agentes con utilidades lineales .
Cortar la torta es más desafiante que una buena asignación homogénea, ya que una torta es heterogénea. En cierto sentido, un pastel es un continuo de bienes: cada punto del pastel es un bien diferente. Este es el tema del teorema de Weller.
Notación
El pastel se denota por . El número de socios se denota por.
Una partición de pastel , denotada por, es una n- tupla de subconjuntos de ; es la pieza entregada a la pareja .
Una partición se llama PEEF si cumple las siguientes dos condiciones:
- Eficiencia de Pareto : ninguna otra división es débilmente mejor para todos los socios y estrictamente mejor para al menos uno de los socios.
- Sin envidia : ningún socio prefiere estrictamente una pieza asignada a otro agente.
Una partición y una medida de precio en se denominan CEEI si cumplen las dos condiciones siguientes (donde es agente medida del valor y es la medida del precio):
- Equilibrio competitivo : para cada agente i , cada rebanada positivay cada rebanada positiva : .
- Igualdad de ingresos: para cada agente i: .
CEEI es mucho más fuerte que PEEF: cada asignación de CEEI es PEEF, pero hay muchas asignaciones de PEEF que no son CEEI.
El teorema de Weller prueba la existencia de una asignación de CEEI, lo que implica la existencia de una asignación de PEEF.
Boceto de prueba
La presentación a continuación se basa en el artículo de Weller y en parte en [2] : 341–351 .
La prueba de Weller se basa en divisiones de pastel ponderadas-utilitarias-máximas (WUM) . Una división WUM es una división que maximiza una función de la siguiente forma:
dónde es un índice de un agente, es agente medida de valor, es la pieza entregada a , y es un peso positivo.
Un corolario del teorema de compacidad de Dubins-Spanier es que, para cada vector de peso, Existen asignaciones WUM. Intuitivamente, cada pequeño trozo de pastel debe ser entregado a la persona para quien es más grande. Si hay dos o más personas para quienes este valor es el mismo, entonces cada división arbitraria de esa pieza entre ellos da como resultado una división WUM (las asignaciones WUM también se pueden definir usando el conjunto Radon-Nikodym . Cada vector de peso, como un punto en el -unidad simplex dimensional , define una partición de ese simplex. Esta partición induce una asignación del conjunto Radon-Nikodym del pastel, lo que induce una o más asignaciones del pastel) .
Cada división de WUM es obviamente PE. Sin embargo, una división WUM puede ser muy injusta; por ejemplo, si es muy grande, entonces el agente podría obtener solo una pequeña fracción del pastel (el vector de peso está muy cerca del agente vértice de la unidad simplex, lo que significa que obtendrá solo puntos del conjunto Radon-Nikodym que estén muy cerca de su vértice) . Por el contrario, si es muy pequeño, entonces el agente podría conseguir todo el pastel.
Weller prueba que existe un vector de pesos para el cual la división WUM también es EF. Esto se hace definiendo varias funciones:
1. La función : para cada vector de peso positivo , es el conjunto de particiones WUM con pesos . La funciónes una función de valor establecido desde el interior de la unidad simplex hacia el espacio de los conjuntos de particiones de torta de PE.
2. La función : para cada partición , es un vector proporcional a los valores de los socios: . La función mapea el espacio de las particiones de la torta en la unidad simplex.
3. La función : por cada vector de peso positivo , es un conjunto de nuevos vectores de peso. Esta es una función con valores establecidos desde el interior de la unidad simplex hacia el conjunto de subconjuntos de la unidad simplex. Los vectores en son, en cierto sentido, opuestos a : Si es pequeño, entonces las particiones en dar agente un gran valor y su peso en es largo. Por el contrario, si es grande entonces las particiones en dar agente un valor pequeño y su peso en es largo. Esto sugiere que, si tiene un punto fijo, entonces este punto fijo corresponde a la partición PEEF que buscamos.
Para demostrar que la función tiene un punto fijo, nos gustaría utilizar el teorema de punto fijo de Kakutani . Sin embargo, hay un problema técnico que debe resolverse: la funciónse define solo en el interior de la unidad simplex, mientras que su rango es toda la unidad simplex. Afortunadamente, es posible ampliaral límite de la unidad simplex, de manera que se garantice que ningún punto fijo NO estará en el límite. [2] : 343–344 La función extendida,, es de hecho una función de la unidad simplex a subconjuntos de la unidad simplex. satisface los requisitos del teorema del punto fijo de Kakutani, ya que: [2] : 345–349
- Es un mapeo punto a conjunto de la unidad simplex, que es un subconjunto compacto y convexo del espacio euclidiano;
- Es semicontinuo superior ;
- Para cada en la unidad simplex, no está vacío y es cerrado y convexo;
Por lo tanto, tiene un punto fijo - un vector en la unidad simplex tal que . Por la construcción de, es posible demostrar que el punto fijo debe estar en la unidad-simplex-interior, donde . Por eso:
Por definición de , , entonces existe una partición tal que:
es claramente PE ya que es WUM (con vector de peso W). También es EF, ya que:
- implica que X maximiza la suma ponderada con pesos . Esto significa que cada fracción de torta se le da a un agente para quien la densidad de valor ponderada es máxima. Por lo tanto, por cada dos agentes:
- .
- implica que la relación entre los valores de cada dos agentes es igual a la relación de sus pesos:
- .
La combinación de las dos últimas desigualdades da, por cada dos agentes :
que es exactamente la definición de ausencia de envidia.
Calcular la medida del precio
Una vez que tengamos una asignación de PEEF , una medida de precio se puede calcular de la siguiente manera:
- Por cada pieza que está en manos del agente ,
- Para cada pieza dividida entre varios agentes, el precio es la suma de los precios de sus subconjuntos mantenidos por estos agentes.
Es posible probar que la pareja Satisfacer las condiciones de equilibrio competitivo con ingresos iguales (CEEI). Específicamente, los ingresos de cada agente, bajo la medida de precio, es exactamente 1, ya que:
Ejemplo
Como ilustración, consideremos un pastel 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 |
Como hay dos agentes, el vector se puede representar con un solo número: la relación entre el peso de Alice y el peso de George:
- Si la proporción es menor de 1: 4, entonces una división WUM debería darle todo el pastel a Alice. La proporción de valores disfrutados por la gente será infinita (o 1: 0), por lo que, por supuesto, no se encontrará un punto fijo en este rango.
- Si la proporción es exactamente 1: 4, entonces se le debe dar todo el chocolate a Alice, pero la vainilla se puede dividir arbitrariamente entre Alice y George. La relación de valores de las divisiones WUM varía entre 1: 0 y 9: 4. Este rango no contiene la relación 1: 4, por lo tanto, el punto fijo no está aquí.
- Si la proporción está entre 1: 4 y 9: 6, entonces toda la vainilla debe entregarse a George y todo el chocolate debe entregarse a Alice. La relación de valores es 9: 4, que no está en el rango, por lo que aún no se ha encontrado el punto fijo.
- Si la proporción es exactamente 9: 6, entonces toda la vainilla debe entregarse a George, pero el chocolate se puede dividir arbitrariamente entre Alice y George. La relación de valores de las divisiones WUM varía entre 9: 4 y 0: 1. Vemos que 9: 6 está en el rango, por lo que tenemos un punto fijo. Se puede lograr dándole a George toda la vainilla y 1/6 del chocolate (por un valor total de 5) y dándole a Alice los 5/6 restantes del chocolate (por un valor total de 7,5). Esta división es PEEF.
Generalizaciones y extensiones
Berliant, Thomson y Dunz [3] introdujeron el criterio de ausencia de envidia grupal , que generaliza tanto la eficiencia de Pareto como la ausencia de envidia. Demostraron la existencia de asignaciones grupales sin envidia con utilidades aditivas. Posteriormente, Berliant y Dunz [4] estudiaron algunas funciones de utilidad naturales no aditivas, motivadas por el problema de la división de la tierra. Cuando los servicios públicos no son aditivos, ya no se garantiza que exista una asignación de CEEI, pero existe bajo ciertas restricciones.
Se pueden encontrar más resultados relacionados en Corte eficiente de pasteles y Corte de pasteles utilitario .
Algoritmos
El teorema de Weller es puramente existencial. Algunos trabajos posteriores estudiaron los aspectos algorítmicos de encontrar una partición CEEI. Estos trabajos generalmente asumen que las medidas de valor son constantes por partes , es decir, la torta se puede dividir en regiones homogéneas en las que la densidad de valor de cada agente es uniforme.
El primer algoritmo para encontrar una partición CEEI en este caso fue desarrollado por Reijnierse y Potters. [5]
Aziz y Ye desarrollaron un algoritmo más eficiente desde el punto de vista computacional. [6]
De hecho, cada partición de torta de CEEI maximiza el producto de los servicios públicos y viceversa: cada partición que maximiza el producto de los servicios públicos es un CEEI. [7] Por lo tanto, se puede encontrar un CEEI resolviendo un programa convexo maximizando la suma de los logaritmos de las utilidades.
Para dos agentes, el procedimiento de ganador ajustado se puede utilizar para encontrar una asignación de PEEF que también sea equitativa (pero no necesariamente un CEEI).
Todos los algoritmos anteriores se pueden generalizar a medidas de valor que son Lipschitz continuas . Dado que tales funciones pueden aproximarse como funciones constantes por partes "tan cerca como queramos", los algoritmos anteriores también pueden aproximar una asignación PEEF "tan cerca como queramos". [5]
Limitaciones
En el tabique CEEI garantizado por Weller se podrá desconectar la pieza asignada a cada socio. En lugar de una sola pieza contigua, cada socio puede recibir una pila de "migajas". De hecho, cuando las piezas deben estar conectadas, es posible que las particiones CEEI no existan. Considere las siguientes valoraciones constantes a trozos:
Alicia | 2 | 2 | 2 | 2 | 2 | 2 |
Jorge | 1 | 1 | 4 | 4 | 1 | 1 |
La condición CE implica que todos los segmentos periféricos deben tener el mismo precio (digamos, p ) y ambos segmentos centrales deben tener el mismo precio (digamos q ). La condición EI implica que el precio total del pastel debe ser 2, por lo que. La condición de EI nuevamente implica que, en cualquier división de CEEI conectada, el pastel se corta por la mitad. Tanto Alice como George reciben dos cortes periféricos y un corte central. La condición CE para Alice implica que pero la condición de CE sobre George implica que , que es una contradicción.
Si bien la condición de CEEI puede ser inalcanzable con piezas conectadas, la condición de PEEF más débil siempre se puede lograr cuando hay dos socios. Esto se debe a que, con dos socios, la ausencia de envidia equivale a la proporcionalidad, y la proporcionalidad se conserva en las mejoras de Pareto. Sin embargo, cuando hay tres o más socios, incluso la condición PEEF más débil puede ser inalcanzable. Considere las siguientes valoraciones constantes por partes: [8] : Ejemplo 5.1
Alicia | 2 | 0 | 3 | 0 | 2 | 0 | 0 |
Beto | 0 | 0 | 0 | 0 | 0 | 7 | 0 |
Carl | 0 | 2 | 0 | 2 | 0 | 0 | 3 |
EF implica que Bob recibe al menos parte de su porción de valor 7 (PE implica entonces que la recibe toda).
Por conectividad, hay tres opciones:
- La pieza de Carl está a la derecha de la pieza de Bob. Entonces Carl obtiene el corte más a la derecha y su valor es 3. PE implica que Alice obtiene los cinco cortes a la izquierda de la pieza de Bob, que valen 4 para Carl. Entonces Carl envidia a Alice.
- La pieza de Carl está a la izquierda de la pieza de Bob, y él obtiene sus dos piezas de 2 valores. Entonces, el valor de Alice es como máximo 2 y la pieza de Carl vale 3 para Alice. Entonces Alice envidia a Carl.
- La pieza de Carl está a la izquierda de la pieza de Bob, y él obtiene como máximo una pieza de 2 valores. Entonces, la asignación no es PE, ya que Carl puede aumentar su valor a 3 moviéndose a la derecha de Bob sin dañar a nadie.
Por lo tanto, ninguna asignación es PEEF.
En el ejemplo anterior, si consideramos que el pastel es un "pastel" (es decir, si se permite que un trozo pase alrededor del límite del pastel hasta el otro límite), entonces existe una asignación de PEEF; sin embargo, Stromquist [9] mostró un ejemplo más sofisticado donde una asignación de PEEF no existe ni siquiera en un pastel.
Ver también
- División sin envidia paretoeficiente : el problema análogo de los bienes divisibles homogéneos.
Referencias
- ^ Weller, Dietrich (1985). "División justa de un espacio medible". Revista de Economía Matemática . 14 : 5–17. doi : 10.1016 / 0304-4068 (85) 90023-0 .
- ^ a b c Barbanel, Julius B .; con una introducción de Alan D. Taylor (2005). La geometría de una división justa eficiente . Cambridge: Cambridge University Press. doi : 10.1017 / CBO9780511546679 . ISBN 0-521-84248-4. Señor 2132232 . El resumen breve está disponible en: Barbanel, J. (2010). "Un enfoque geométrico de la división justa". The College Mathematics Journal . 41 (4): 268. doi : 10.4169 / 074683410x510263 .
- ^ Berliant, M .; Thomson, W .; Dunz, K. (1992). "Sobre la justa división de una mercancía heterogénea". Revista de Economía Matemática . 21 (3): 201. doi : 10.1016 / 0304-4068 (92) 90001-n .
- ^ Berliant, Marcus; Dunz, Karl (2004). "Una base de la teoría de la ubicación: existencia de equilibrio, los teoremas de bienestar y núcleo". Revista de Economía Matemática . 40 (5): 593. doi : 10.1016 / s0304-4068 (03) 00077-6 .
- ^ a b Reijnierse, JH; Potter, JAM (1998). "Sobre la búsqueda de una división óptima de Pareto sin envidia". Programación matemática . 83 (1-3): 291-311. doi : 10.1007 / bf02680564 .
- ^ Ye, Chun; Aziz, Haris (14 de diciembre de 2014). Algoritmos de corte de torta para valoraciones constantes por partes y uniformes por partes . Economía Web e Internet . Apuntes de conferencias en Ciencias de la Computación. 8877 . Springer, Cham. págs. 1-14. CiteSeerX 10.1.1.743.9056 . doi : 10.1007 / 978-3-319-13129-0_1 . ISBN 978-3-319-13128-3.
- ^ Sziklai, Balázs R .; Segal-Halevi, Erel (26 de mayo de 2018). "Monotonicidad y equilibrio competitivo en la tarta". Teoría económica . 68 (2): 363–401. arXiv : 1510.05229 . doi : 10.1007 / s00199-018-1128-6 . ISSN 0938-2259 .
- ^ Segal-Halevi, Erel; Sziklai, Balázs R. (1 de septiembre de 2018). "Monotonicidad de recursos y población-monotonicidad en corte de pastel conectado". Ciencias Sociales Matemáticas . 95 : 19-30. arXiv : 1703.08928 . doi : 10.1016 / j.mathsocsci.2018.07.001 . ISSN 0165-4896 .
- ^ Stromquist, Walter (2007). "Un pastel que no se puede cortar de manera justa" (PDF) . Actas del seminario Dagstuhl .