Teoremas de Dubins-Spanier

Los teoremas de Dubins-Spanier son varios teoremas de la teoría de la división justa de la torta . Fueron publicados por Lester Dubins y Edwin Spanier en 1961. ^[1] Aunque la motivación original de estos teoremas es la división justa, en realidad son teoremas generales de la teoría de la medida .

Hay un conjunto , y un conjunto que es un álgebra sigma de subconjuntos de .${\estilo de visualización U}$${\displaystyle \mathbb {U}}$${\estilo de visualización U}$

Hay socios. Cada socio tiene una medida de valor personal . Esta función determina cuánto vale cada subconjunto para ese socio.${\estilo de visualización n}$${\estilo de visualización i}$${\displaystyle V_{i}:\mathbb {U} \a \mathbb {R} }$${\estilo de visualización U}$

Sea una partición de dos conjuntos mensurables: . Defina la matriz como la siguiente matriz:${\estilo de visualización X}$${\estilo de visualización U}$${\estilo de visualización k}$${\displaystyle U=X_{1}\sqcup \cdots \sqcup X_{k}}$$Estilo de visualización M_{X}}$${\displaystyle n\times k}$

${\displaystyle M_{X}[i,j]=V_{i}(X_{j})}$

Esta matriz contiene las valoraciones de todos los jugadores para todas las piezas de la partición.

Sea la colección de todas estas matrices (para las mismas medidas de valor, el mismo y diferentes particiones):${\displaystyle \mathbb {M} }$${\displaystyle k}$

${\displaystyle \mathbb {M} =\{M_{X}\mid X{\text{ is a }}k{\text{-partition of }}U\}}$

Los teoremas de Dubins-Spanier tratan las propiedades topológicas de .${\displaystyle \mathbb {M} }$

Si todas las medidas de valor son contablemente aditivas y no atómicas , entonces:${\displaystyle V_{i}}$

• ${\displaystyle \mathbb {M} }$es un conjunto compacto ;
• ${\displaystyle \mathbb {M} }$es un conjunto convexo .

Esto ya fue demostrado por Dvoretzky, Wald y Wolfowitz. ^[2]

Una partición de torta en k partes se denomina partición de consenso con pesos (también llamada división exacta ) si:${\displaystyle X}$${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$

${\displaystyle \forall i\in \{1,\dots ,n\}:\forall j\in \{1,\dots ,k\}:V_{i}(X_{j})=w_{j}}$

Es decir, hay consenso entre todos los socios de que el valor de la pieza j es exactamente .${\displaystyle w_{j}}$

Supongamos, a partir de ahora, que son pesos cuya suma es 1:${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$

${\displaystyle \sum _{j=1}^{k}w_{j}=1}$

y las medidas de valor se normalizan de tal manera que cada socio valora el pastel entero exactamente como 1:

${\displaystyle \forall i\in \{1,\dots ,n\}:V_{i}(U)=1}$

La parte de convexidad del teorema 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 , defina una partición de la siguiente manera:${\displaystyle j\in \{1,\dots ,k\}}$${\displaystyle X^{j}}$

${\displaystyle X_{j}^{j}=U}$

${\displaystyle \forall r\neq j:X_{r}^{j}=\emptyset }$

En la partición , todos los socios valoran la pieza -ésima como 1 y todas las demás piezas como 0. Por lo tanto, en la matriz , hay unos en la columna -ésima y ceros en todas partes.${\displaystyle X^{j}}$${\displaystyle j}$${\displaystyle M_{X^{j}}}$${\displaystyle j}$

Por convexidad, existe una partición tal que:${\displaystyle X}$

${\displaystyle M_{X}=\sum _{j=1}^{k}w_{j}\cdot M_{X^{j}}}$

En esa matriz, la columna -ésima contiene únicamente el valor . Esto significa que, en la partición , todos los socios valoran la parte -ésima exactamente como .${\displaystyle j}$${\displaystyle w_{j}}$${\displaystyle X}$${\displaystyle j}$${\displaystyle w_{j}}$

Nota: este corolario confirma una afirmación anterior de Hugo Steinhaus . También da una respuesta afirmativa al problema del Nilo , siempre que haya un número finito de alturas de inundación.

Una división de torta en n pedazos (un pedazo por pareja) se llama división superproporcional con pesos si:${\displaystyle X}$${\displaystyle w_{1},w_{2},...,w_{n}}$

${\displaystyle \forall i\in 1\dots n:V_{i}(X_{i})>w_{i}}$

Es decir, la parte asignada a su compañero es estrictamente más valiosa para él que lo que le corresponde. El siguiente enunciado es el teorema de Dubins-Spanier sobre la existencia de la división superproporcional ^{: 6}${\displaystyle i}$

Es necesaria la hipótesis de que las medidas de valor no son idénticas, de lo contrario la suma conduce a una contradicción.${\displaystyle V_{1},...,V_{n}}$${\displaystyle \sum _{i=1}^{n}V_{i}(X_{i})=\sum _{i=1}^{n}V_{1}(X_{i})>\sum _{i=1}^{n}w_{i}=1}$

Es decir, si todas las medidas de valor son contablemente aditivas y no atómicas, y si hay dos socios tales que , entonces existe una división superproporcional, es decir, la condición necesaria también es suficiente.${\displaystyle i,j}$${\displaystyle V_{i}\neq V_{j}}$

Supóngase que . Entonces hay una porción del pastel, , tal que . Sea el complemento de ; entonces . Esto significa que . Sin embargo, . Por lo tanto, o bien . Supóngase que y son verdaderas.${\displaystyle V_{1}\neq V_{2}}$${\displaystyle Z\subseteq U}$${\displaystyle V_{1}(Z)>V_{2}(Z)}$${\displaystyle {\overline {Z}}}$${\displaystyle Z}$${\displaystyle V_{2}({\overline {Z}})>V_{1}({\overline {Z}})}$${\displaystyle V_{1}(Z)+V_{2}({\overline {Z}})>1}$${\displaystyle w_{1}+w_{2}\leq 1}$${\displaystyle V_{1}(Z)>w_{1}}$${\displaystyle V_{2}({\overline {Z}})>w_{2}}$${\displaystyle V_{1}(Z)>V_{2}(Z)}$${\displaystyle V_{1}(Z)>w_{1}}$

Defina las siguientes particiones:

• ${\displaystyle X^{1}}$:la partición que le da al socio 1, al socio 2 y nada a todos los demás.${\displaystyle Z}$${\displaystyle {\overline {Z}}}$
• ${\displaystyle X^{i}}$(para ): la partición que le da todo el pastel al socio y nada a todos los demás.${\displaystyle i\geq 2}$${\displaystyle i}$

Aquí nos interesan únicamente las diagonales de las matrices , que representan las valoraciones de los socios respecto de sus propias piezas:${\displaystyle M_{X^{j}}}$

• En , la entrada 1 es , la entrada 2 es y las otras entradas son 0.${\displaystyle {\textrm {diag}}(M_{X^{1}})}$${\displaystyle V_{1}(Z)}$${\displaystyle V_{2}({\overline {Z}})}$
• En (para ), la entrada es 1 y los otros enteros son 0.${\displaystyle {\textrm {diag}}(M_{X^{i}})}$${\displaystyle i\geq 2}$${\displaystyle i}$

Por convexidad, para cada conjunto de pesos existe una partición tal que:${\displaystyle z_{1},z_{2},...,z_{n}}$${\displaystyle X}$

${\displaystyle M_{X}=\sum _{j=1}^{n}{z_{j}\cdot M_{X^{j}}}.}$

Es posible seleccionar los pesos de manera que, en la diagonal de , las entradas estén en la misma proporción que los pesos . Como asumimos que , es posible demostrar que , por lo que es una división superproporcional.${\displaystyle z_{i}}$${\displaystyle M_{X}}$${\displaystyle w_{i}}$${\displaystyle V_{1}(Z)>w_{1}}$${\displaystyle \forall i\in 1\dots n:V_{i}(X_{i})>w_{i}}$${\displaystyle X}$

Una división de la torta en n porciones (una porción por socio) se llama utilitarista -óptima si maximiza la suma de valores, es decir, maximiza:${\displaystyle X}$

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

Las divisiones utilitaristas óptimas no siempre existen. Por ejemplo, supongamos que el conjunto de números enteros positivos es 1. Hay dos socios. Ambos valoran todo el conjunto como 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 utilitarista, es mejor dar al socio 1 un subconjunto finito grande y dar el resto al socio 2. Cuando el conjunto dado al socio 1 se hace 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 hay una división utilitarista óptima.${\displaystyle U}$${\displaystyle U}$

El problema con el ejemplo anterior es que la medida del valor del socio 2 es finitamente aditiva pero no contablemente aditiva .

La parte de compacidad del teorema 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 no atomicidad: si todas las medidas de valor son contablemente aditivas, entonces existe una partición utilitarista-óptima. ^{[1] : 7}

Una partición de torta en n partes (una parte por pareja) se llama leximin -óptima con pesos si maximiza el vector de valores relativos ordenado lexicográficamente, es decir, maximiza el siguiente vector:${\displaystyle X}$${\displaystyle w_{1},w_{2},...,w_{n}}$

${\displaystyle {V_{1}(X_{1}) \over w_{1}},{V_{2}(X_{2}) \over w_{2}},\dots ,{V_{n}(X_{n}) \over w_{n}}}$

donde los socios están indexados de tal manera que:

${\displaystyle {V_{1}(X_{1}) \over w_{1}}\leq {V_{2}(X_{2}) \over w_{2}}\leq \dots \leq {V_{n}(X_{n}) \over w_{n}}}$

Una partición leximin-óptima maximiza el valor del socio más pobre (en relación con su peso); sujeto a eso, maximiza el valor del socio siguiente más pobre (en relación con su peso); etc.

La parte de compacidad del teorema DS implica inmediatamente que: ^{[1] : 8}

Si todas las medidas de valor son contablemente aditivas y no atómicas,

Entonces existe una división leximin-óptima.

• El criterio de optimalidad leximin, introducido por Dubins y Spanier, ha sido estudiado extensamente posteriormente. En particular, en el problema del corte de la torta, fue estudiado por Marco Dall'Aglio. ^[3]

• Teorema de medida vectorial de Lyapunov ^[4]
• Teorema de Weller