División fuertemente proporcional

Una división fuertemente proporcional ^[1] (a veces llamada división superproporcional ) es un tipo de división justa . Es una división de recursos entre n socios, en la que el valor recibido por cada socio es estrictamente mayor que su parte correspondiente de 1/ n del valor total. Formalmente, en una división fuertemente proporcional de un recurso C entre n socios, cada socio i , con una medida de valor V _i , recibe una parte X _i tal que

${\displaystyle V_{i}(X_{i})>V_{i}(C)/n}$.

Obviamente, no existe una división fuertemente proporcional cuando todos los socios tienen la misma medida de valor. La mejor condición que siempre se puede garantizar es , que es la condición para una división proporcional simple . Sin embargo, se puede esperar que, cuando diferentes agentes tienen diferentes valoraciones, sea posible utilizar este hecho en beneficio de todos los jugadores y dar a cada uno de ellos estrictamente más de lo que les corresponde. ${\displaystyle V_{i}(X_{i})\geq V_{i}(C)/n}$

Existencia

En 1948, Hugo Steinhaus conjeturó la existencia de una división superproporcional de un pastel : ^[2]

Se puede afirmar incidentalmente que si hay dos (o más) socios con diferentes estimaciones, existe una división que da a cada uno más de lo que le corresponde ( Knaster ); este hecho refuta la opinión común de que las diferencias en las estimaciones hacen difícil una división justa.

En 1961, Dubins y Spanier demostraron que la condición necesaria para la existencia también es suficiente, es decir, siempre que las valoraciones de los socios sean aditivas y no atómicas, y haya al menos dos socios cuya función de valor sea incluso ligeramente diferente, entonces hay una división superproporcional en la que todos los socios reciben más de 1/ n .

La prueba fue un corolario del teorema de convexidad de Dubins-Spanier . Se trataba de una prueba puramente existencial basada en argumentos de convexidad.

Algoritmos

En 1986, Douglas R. Woodall publicó el primer protocolo para encontrar una división superproporcional. ^[3]

Sea C el pastel entero. Si las valoraciones de los agentes son diferentes, entonces debe haber un testigo de ello: un testigo es un trozo específico de pastel, digamos X ⊆ C , que es valorado de manera diferente por algunos dos socios, digamos Alice y Bob. Sea Y  := C \ X. Sea a _x = V _Alice (X) y b _x = V _Bob (X) y a _y = V _Alice (Y) y b _y = V _Bob (Y) , y supongamos que:

b _x > a _x , lo que implica: b _y < a _y .

La idea es particionar X e Y por separado: al particionar X , le daremos un poco más a Bob y un poco menos a Alice; al particionar Y , le daremos un poco más a Alice y un poco menos a Bob.

Protocolo de Woodall para dos agentes

Encuentra un número racional entre b _x y a _x , digamos p/q tal que b _x > p/q > a _x . Esto implica que b _y < (qp)/q < a _y . Pídele a Bob que divida X en p partes iguales y que divida Y en qp partes iguales.

Según nuestras suposiciones, Bob valora cada parte de X en b _x /p > 1/ q , y cada parte de Y en b _y /(qp) < 1/ q . Pero para Alice, al menos una parte de X (digamos X ₀ ) debe tener un valor menor que 1/ q y al menos una parte de Y (digamos Y ₀ ) debe tener un valor mayor que 1/ q .

Así que ahora tenemos dos piezas, X ₀ e Y ₀ , tales que:

V _Bob (X ₀ )>V _Alice (X ₀ )

V _Bob (Y ₀ )<V _Alice (Y ₀ )

Dejemos que Alice y Bob dividan el resto C \ X ₀ \ Y ₀ entre ellos de manera proporcional (por ejemplo, usando dividir y elegir ). Agreguemos Y ₀ a la parte de Alice y agreguemos X ₀ a la parte de Bob.

Ahora, cada socio piensa que su asignación es estrictamente mejor que la del otro, por lo que su valor es estrictamente mayor que 1/2.

Protocolo de Woodall paranortefogonadura

La extensión de este protocolo a n socios se basa en el protocolo "Lone Chooser" de Fink .

Supongamos que ya tenemos una división fuertemente proporcional entre i -1 socios (para i≥3 ). Ahora entra en la fiesta el socio n.° i y debemos darle una pequeña porción de cada uno de los primeros i -1 socios, de modo que la nueva división siga siendo fuertemente proporcional.

Consideremos, por ejemplo, al socio n.° 1. Sea d la diferencia entre el valor actual del socio n.° 1 y (1/( i -1)). Como la división actual es fuertemente proporcional, sabemos que d>0 .

Elija un entero positivo q tal que: ${\displaystyle d>{\frac {1}{(i-1)i(q(i-1)-1)}}}$

Pídale al socio #1 que divida su parte en pedazos que considere de igual valor y deje que el nuevo socio elija los pedazos que considere más valiosos. ${\displaystyle qi-1}$ ${\displaystyle q}$

El socio n.° 1 se queda con un valor de de su valor anterior, que era (por definición de d ). El primer elemento se convierte en y d se convierte en ; al sumarlos, se obtiene que el nuevo valor es mayor que: de todo el pastel. ${\displaystyle {\frac {(qi-1)-q}{qi-1}}={\frac {q(i-1)-1}{qi-1}}}$ ${\displaystyle {\frac {1}{i-1}}+d}$ ${\displaystyle {\frac {q(i-1)-1}{(i-1)(qi-1)}}}$ ${\displaystyle {\frac {1}{i(i-1)(qi-1)}}}$ ${\displaystyle {\frac {(qi-1)(i-1)}{(i-1)i(qi-1)}}={\frac {1}{i}}}$

En cuanto al nuevo socio, después de haber tomado q piezas de cada uno de los primeros i -1 socios, su valor total es al menos: de todo el pastel. ${\displaystyle {\frac {q}{qi-1}}>{\frac {1}{i}}}$

Esto demuestra que la nueva división también es fuertemente proporcional.

Protocolo de Barbanel

Julius Barbanel ^[1] extendió el algoritmo de Woodall a agentes con diferentes derechos , incluidos los derechos irracionales. En este contexto, el derecho de cada agente i está representado por un peso , con . Una asignación fuertemente proporcional es aquella en la que, para cada agente i : ${\displaystyle w_{i}}$ ${\displaystyle W:=\sum _{i}w_{i}}$

${\displaystyle V_{i}(X_{i})>w_{i}\cdot V_{i}(C)/W}$.

Protocolo Janko-Joo

Janko y Joo ^[4] presentaron un algoritmo más simple para agentes con diferentes derechos. De hecho, mostraron cómo reducir un problema de división fuertemente proporcional (con derechos iguales o diferentes) en dos problemas de división proporcional con diferentes derechos :

• Para la pieza X , cambie el derecho de Alice a y el derecho de Bob a . Como b _x > a _{x ,} la suma de los nuevos derechos es estrictamente menor que , por lo que la suma de todos los n derechos (dentados por W _X ) es estrictamente menor que W. ${\displaystyle w_{A}-1/a_{x}}$ ${\displaystyle w_{B}+1/b_{x}}$ ${\displaystyle w_{A}+w_{B}}$
• Para la pieza Y , cambie el derecho de Alice a y el derecho de Bob a . Aquí también, dado que _y < a _{y ,} la nueva suma de todos los derechos (dentada por W _Y ) es estrictamente menor que W . ${\displaystyle w_{A}+1/a_{y}}$ ${\displaystyle w_{B}-1/b_{y}}$
• El valor de Alice es al menos $${\displaystyle {\begin{aligned}&(w_{A}-1/a_{x})\cdot a_{x}/W_{X}+(w_{A}+1/b_{y})\cdot b_{x}/W_{Y}=\\=&(w_{A}a_{x}-1)/W_{X}+(w_{A}a_{y}+1)/W_{Y}\\>&(w_{A}a_{x}-1)/W+(w_{A}a_{y}+1)/W\\=&w_{A}V_{A}(C)/W\end{aligned}}}$$
• De manera similar, el valor de Bob es al menos $${\displaystyle {\begin{aligned}&(w_{B}+1/b_{x})\cdot b_{x}/W_{X}+(w_{B}-1/b_{y})\cdot b_{y}/W_{Y}=\\=&(w_{B}b_{x}+1)/W_{X}+(w_{B}b_{y}-1)/W_{Y}\\>&(w_{B}b_{x}-1)/W+(w_{B}b_{y}+1)/W\\=&w_{B}V_{B}(C)/W\end{aligned}}}$$
• El valor de cada otro agente i es al menos Por lo que la división es fuertemente proporcional. $${\displaystyle {\begin{aligned}&w_{i}\cdot V_{i}(X)/W_{X}+w_{i}\cdot V_{i}(Y)/W_{Y}\\>&w_{i}\cdot V_{i}(X)/W+w_{i}\cdot V_{i}(Y)/W\\=&w_{i}V_{i}(C)/W\end{aligned}}}$$

Conceptos relacionados

Una asignación se considera fuertemente libre de envidia si para cada dos socios i , j :

${\displaystyle V_{i}(X_{i})>V_{i}(X_{j})}$.

Una asignación se denomina súper libre de envidia si para cada dos socios i , j :

${\displaystyle V_{i}(X_{i})>1/n>V_{i}(X_{j})}$.

La súper ausencia de envidia implica una fuerte ausencia de envidia, lo que implica una fuerte proporcionalidad. ^[5]

Referencias

1. Barbanel, Julius (1996). "Algoritmos de teoría de juegos para una división justa y fuertemente justa de la torta con derechos". Colloquium Mathematicum . 1 (69): 59–73. doi : 10.4064/cm-69-1-59-73 . ISSN  0010-1354.
2. Steinhaus, Hugo (1948). "El problema de la división justa". Econometrica . 16 (1): 101–4. JSTOR  1914289.
3. Woodall, DR (1986). "Una nota sobre el problema de la división de la torta". Journal of Combinatorial Theory, Serie A . 42 (2): 300–301. doi : 10.1016/0097-3165(86)90101-9 .
4. Jankó, Zsuzsanna; Joó, Atila (11 de marzo de 2022). "Cortar un pastel para una infinidad de invitados". La Revista Electrónica de Combinatoria . 29 : P1.42. arXiv : 2109.05269 . doi : 10.37236/10897 . ISSN  1077-8926.
5. Barbanel, Julius B. (1 de enero de 1996). "División de tortas súper libre de envidia e independencia de medidas". Revista de análisis matemático y aplicaciones . 197 (1): 54–60. doi : 10.1006/S0022-247X(96)90006-2 . ISSN  0022-247X.