Los teoremas de Dubins-Spanier son varios teoremas de la teoría del corte de torta justo . Fueron publicados por Lester Dubins y Edwin Spanier en 1961. [1] Aunque la motivación original de estos teoremas es la división justa, de hecho son teoremas generales en la teoría de la medida .
Configuración
Hay un conjunto y un set que es un sigma-álgebra de subconjuntos de.
Existen socios. Cada socio tiene una medida de valor personal . Esta función determina cuánto cada subconjunto de vale la pena para ese socio.
Dejar una partición de a conjuntos medibles: . Definir la matriz como el seguiente matriz:
Esta matriz contiene las valoraciones de todos los jugadores para todas las piezas de la partición.
Dejar ser la colección de todas esas matrices (para las mismas medidas de valor, la misma y diferentes particiones):
Los teoremas de Dubins-Spanier tratan de las propiedades topológicas de .
Declaraciones
Si todos los valores miden son contablemente aditivos y no atómicos , entonces:
- es un conjunto compacto ;
- es un conjunto convexo .
Esto ya lo demostraron Dvoretzky, Wald y Wolfowitz. [2]
Corolarios
Partición de consenso
Una partición de pastel a k piezas se le llama partición de consenso con pesos(también llamada división exacta ) si:
Es decir, existe un consenso entre todos los socios de que el valor de la pieza j es exactamente.
Supongamos, de ahora en adelante, que son pesos cuya suma es 1:
y las medidas de valor se normalizan de modo que cada socio valora todo el pastel exactamente como 1:
La parte de convexidad del teorema de DS implica que: [1] : 5
- Si todas las medidas de valor son contablemente aditivas y no atómicas,
- entonces existe una partición de consenso.
PRUEBA: Para cada , define una partición como sigue:
En la partición , todos los socios valoran -th pieza como 1 y todas las demás piezas como 0. Por lo tanto, en la matriz , hay unos en el -ésima columna y ceros en todas partes.
Por convexidad, hay una partición. tal que:
En esa matriz, el -th columna contiene solo el valor . Esto significa que, en la partición, todos los socios valoran -th pieza exactamente .
Nota: este corolario confirma una afirmación anterior de Hugo Steinhaus . También da una respuesta afirmativa al problema del Nilo siempre que haya solo un número finito de alturas de inundación.
División superproporcional
Una partición de pastel a n piezas (una pieza por socio) se llama una división súper proporcional con los pesos Si:
Es decir, la pieza asignada al socio es estrictamente más valioso para él de lo que se merece. El siguiente enunciado es el teorema de Dubins-Spanier sobre la existencia de una división superproporcional : 6
Teorema : con estas notaciones, dejemos ser pesos cuya suma es 1, suponga que el punto es un punto interior del símplex (n-1) -dimensional con coordenadas por pares diferentes, y suponga que el valor mide están normalizados de manera que cada socio valora la torta completa exactamente como 1 (es decir, son medidas de probabilidad no atómicas). Si al menos dos de las medidas no son iguales ), entonces existen divisiones superproporcionales.
La hipótesis de que el valor mide no son idénticos es necesario. De lo contrario, la suma conduce a una contradicción.
Es decir, si todas las medidas de valor son contablemente aditivas y no atómicas, y si hay dos socios tal que , entonces existe una división superproporcional, es decir, la condición necesaria también es suficiente.
Boceto de prueba
Supongamos que wlog . Luego hay un trozo del pastel, tal que . Dejar ser el complemento de ; luego. Esto significa que. Sin emabargo,. Por lo tanto, o o . Supongamos que wlog y son verdaderas.
Defina las siguientes particiones:
- : la partición que da al socio 1, al socio 2, y nada a todos los demás.
- (por ): la partición que le da todo el pastel al socio y nada a todos los demás.
Aquí, solo nos interesan las diagonales de las matrices , que representan las valoraciones de los socios a sus propias piezas:
- En , la entrada 1 es , la entrada 2 es y las otras entradas son 0.
- En (por ), entrada es 1 y los demás enteros son 0.
Por convexidad, para cada juego de pesos hay una partición tal que:
Es posible seleccionar los pesos tal que, en la diagonal de , las entradas están en las mismas proporciones que los pesos . Dado que asumimos que, es posible demostrar que , entonces es una división superproporcional.
División utilitaria-óptima
Una partición de pastel a n piezas (una pieza por socio) se llama utilitaria -optimal si se maximiza la suma de los valores. Es decir, maximiza:
Las divisiones utilitaristas óptimas no siempre existen. Por ejemplo, supongaes el conjunto de números enteros positivos. Hay dos socios. Ambos valoran todo el conjuntocomo 1. El socio 1 asigna un valor positivo a cada número entero y el socio 2 asigna un valor cero a cada subconjunto finito. Desde un punto de vista utilitario, es mejor darle al socio 1 un subconjunto finito grande y darle el resto al socio 2. Cuando el conjunto dado al socio 1 se vuelve cada vez más grande, la suma de valores se acerca cada vez más a 2 , pero nunca se acerca a 2. Por lo tanto, no existe una división utilitarista-óptima.
El problema con el ejemplo anterior es que la medida del valor del socio 2 es finitamente aditiva pero no numerablemente aditiva .
La parte compacta del teorema de DS implica inmediatamente que: [1] : 7
- Si todas las medidas de valor son contablemente aditivas y no atómicas,
- entonces existe una división utilitarista-óptima.
En este caso especial, no se requiere la no atomicidad: si todas las medidas de valor son contablemente aditivas, entonces existe una partición utilitaria óptima. [1] : 7
División óptima de Leximin
Una partición de pastel a n piezas (una pieza por socio) se llama leximin -optimal con pesossi maximiza el vector de valores relativos ordenado lexicográficamente. Es decir, maximiza el siguiente vector:
donde los socios están indexados de manera que:
Una partición óptima de leximina maximiza el valor del socio más pobre (en relación con su peso); sujeto a eso, maximiza el valor del próximo socio más pobre (en relación con su peso); etc.
La parte compacta del teorema de DS implica inmediatamente que: [1] : 8
- Si todas las medidas de valor son contablemente aditivas y no atómicas,
- entonces existe una división óptima de leximina.
Nuevos desarrollos
- El criterio de leximina-optimalidad, introducido por Dubins y Spanier, se ha estudiado extensamente más tarde. En particular, en el problema del corte de la torta, fue estudiado por Marco Dall'Aglio. [3]
Ver también
Referencias
- ^ a b c d e Dubins, Lester Eli ; Spanier, Edwin Henry (1961). "Cómo cortar un pastel de forma justa". The American Mathematical Monthly . 68 (1): 1-17. doi : 10.2307 / 2311357 . JSTOR 2311357 .
- ^ Dvoretzky, A .; Wald, A .; Wolfowitz, J. (1951). "Relaciones entre ciertos rangos de medidas vectoriales" . Pacific Journal of Mathematics . 1 : 59–74. doi : 10.2140 / pjm.1951.1.59 .
- ^ Dall'Aglio, Marco (2001). "El problema de optimización de Dubins-Spanier en la teoría de la división justa" . Revista de Matemática Computacional y Aplicada . 130 (1–2): 17–40. Código bibliográfico : 2001JCoAM.130 ... 17D . doi : 10.1016 / S0377-0427 (99) 00393-3 .
- ^ Neyman, J (1946). "Un théorèm dʼexistence". CR Acad. Sci . 222 : 843–845.