En el contexto de una tarta justa , una división superproporcional es una división en la que cada socio recibe estrictamente más de 1 / n del recurso por su propia valoración subjetiva ().
Una división superproporcional es mejor que una división proporcional , en la que se garantiza que cada socio recibirá al menos 1 / n (). Sin embargo, a diferencia de la división proporcional, no siempre existe una división superproporcional. Cuando todos los socios tienen exactamente las mismas funciones de valor, lo mejor que podemos hacer es darle a cada socio exactamente 1 / n .
Una condición necesaria para la existencia de una división superproporcional es, por tanto, que no todos los socios tengan la misma medida de valor.
Un dato sorprendente es que, cuando las valoraciones son aditivas y no atómicas, esta condición también es suficiente. Es decir, cuando hay al menos dos socios cuya función de valor es incluso ligeramente diferente, entonces hay una división superproporcional en la que todos los socios reciben más de 1 / n .
Conjetura
La existencia de una división superproporcional se conjeturó por primera vez en 1948: [1]
- A propósito, se puede afirmar que si hay dos (o más) socios con estimaciones diferentes, existe una división que da a todos más de lo que les corresponde ( Knaster ); este hecho refuta la opinión común de que las estimaciones de diferencias dificultan la división justa.
Prueba de existencia
La primera prueba publicada de la existencia de una división superproporcional fue un corolario del teorema de la convexidad de Dubins-Spanier . Esta fue una prueba puramente existencial basada en argumentos de convexidad.
Protocolo
En 1986 se presentó un protocolo para encontrar una división superproporcional [2].
Pieza única de desacuerdo
Sea C el pastel completo. El protocolo comienza con un pedazo de pastel específico, digamos X ⊆ C , que es valorado de manera diferente por dos socios. Llame a estos socios Alice y Bob.
Sea a = V Alice (X) y b = V Bob (X) y suponga wlog que b> a .
Dos piezas de desacuerdo
Encontrar un número racional entre b y un , digamos p / q tal que b> p / q> a . Pregunta a Bob a división X a p partes iguales y se dividen C \ X a qp partes iguales.
Según nuestras suposiciones, Bob valora cada parte de X como más de 1 / q y cada parte de C \ X como menos de 1 / q . Pero para Alice, al menos una parte de X (digamos, Y ) debe tener un valor de menos de 1 / q y al menos una parte de C \ X (digamos, Z ) debe tener un valor de más de 1 / q .
Entonces ahora tenemos dos piezas, Y y Z , tales que:
- V Bob (Y)> V Bob (Z)
- V Alice (Y)
Alice (Z)
División superproporcional para dos socios
Deje que Alice y Bob dividan el resto C \ Y \ Z entre ellos de manera proporcional (por ejemplo, usando dividir y elegir ). Agregue Z a la pieza de Alice y agregue Y a la pieza de Bob.
Ahora cada socio piensa que su asignación es estrictamente mejor que la otra asignación, por lo que su valor es estrictamente más de 1/2.
División superproporcional para n socios
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 superproporcional a i -1 socios (para i≥3 ). Ahora el socio # i entra en la fiesta y debemos darle una pequeña parte de cada uno de los primeros i -1 socios, de modo que la nueva división siga siendo superproporcional.
Considere, por ejemplo, el socio n. ° 1. Sea d la diferencia entre el valor actual del socio # 1 y (1 / ( i -1)). Debido a que la división actual es superproporcional, sabemos que d> 0 .
Elija un número entero positivo q tal que:
Pídale al socio # 1 que divida su parte entre piezas que considere de igual valor y deje que el nuevo socio elija el piezas que él considera más valiosas.
El socio n. ° 1 permanece con un valor de de su valor anterior, que era (por definición de d ). El primer elemento se convierte eny la d se convierte en; resumirlos da que el nuevo valor es más que: de todo el pastel.
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.
Esto prueba que la nueva división también es superproporcional.