El protocolo Robertson-Webb es un protocolo para cortar la torta sin envidias que también es casi exacto . Tiene las siguientes propiedades:
El protocolo fue desarrollado por Jack M. Robertson y William A. Webb. Se publicó por primera vez en 1997 [1] y más tarde en 1998. [2] : 128–133
Una torta C debe ser repartida entre n agentes. Cada agente i tiene:
La suma de todos los w i es 1. Si todos los agentes tienen los mismos derechos, entonces w i = 1/ n para todos los i , pero en general los pesos pueden ser diferentes.
Se requiere particionar C en n subconjuntos, no necesariamente conexos, tales que, para cada dos agentes i y h :
Así que no envidio a J cuando se toman en cuenta sus diferentes derechos. [3]
La principal dificultad para diseñar un procedimiento libre de envidia para n > 2 agentes es que el problema no es "divisible", es decir, si dividimos la mitad de la torta entre n /2 agentes de una manera libre de envidia, no podemos simplemente dejar que los otros n /2 agentes dividan la otra mitad de la misma manera, porque esto podría causar que el primer grupo de n /2 agentes sienta envidia (por ejemplo, es posible que A y B crean que obtuvieron la mitad de su mitad, que es 1/4 de toda la torta; C y D también creen de la misma manera; pero, A cree que C en realidad obtuvo la mitad entera mientras que D no obtuvo nada, por lo que A envidia a C).
El protocolo Robertson-Webb resuelve esta dificultad al exigir que la división no sólo esté libre de envidias, sino que también sea casi exacta. La parte recursiva del protocolo es la siguiente subrutina.
Una partición de X en partes X 1 , …, X m , asignadas a los m jugadores activos, tales que:
Por lo tanto, el agente i no envidia al agente h al tomar en cuenta sus diferentes derechos. [3]
Nota: la presentación que se presenta aquí es informal y simplificada. En el libro se ofrece una presentación más precisa. [2]
Utilice un procedimiento de división casi exacto en X y obtenga una partición que todos los n jugadores ven como ε-casi exacta con pesos w 1 , …, w m .
Deje que uno de los jugadores activos (por ejemplo, A 1 ) corte las piezas de manera que la división sea exacta para él, es decir, para cada j : V 1 ( X j )/ V 1 ( X ) = w j .
Si todos los demás jugadores activos están de acuerdo con el cortador, entonces simplemente se le da la pieza X i al jugador activo A i . Esta división no genera envidia entre los jugadores activos, por lo que hemos terminado.
De lo contrario, existe alguna pieza P sobre la cual hay desacuerdo entre los jugadores activos. Si es necesario, cortando P en piezas más pequeñas, podemos limitar el desacuerdo de modo que todos los jugadores estén de acuerdo en que: V ( P )/ V ( X ) < ε.
Dividamos a los jugadores activos en dos bandos: los "optimistas", que piensan que P es más valioso, y los "pesimistas", que piensan que P es menos valioso. Sea δ la diferencia entre los valores, de modo que para cada optimista i y cada pesimista j : V i ( P )/ V i ( X ) – V j ( P )/ V j ( X ) > δ .
Divida el pastel restante, X − P , en los trozos Q y R , de modo que la división sea casi exacta entre los n jugadores.
Asignemos P ∪ Q a los optimistas. Puesto que creen que P es valioso, necesariamente creen que P ∪ Q es lo suficientemente valioso como para cubrir con creces su parte correspondiente.
Asignemos R a los pesimistas. Como creen que P es menos valioso, necesariamente creen que el resto, R , es lo suficientemente valioso como para cubrir con creces su parte correspondiente.
En este punto hemos dividido a los jugadores activos en dos bandos, cada uno de los cuales reclama colectivamente porciones complementarias del pastel y cada bando está más que satisfecho con su porción colectiva.
Queda por repartir cada porción de la torta entre los jugadores de su bando. Esto se hace mediante dos aplicaciones recursivas del procedimiento:
En ambas aplicaciones, el factor de casi exactitud debería ser como máximo δ. Como la distribución resultante es casi exacta entre los n jugadores, la distribución entre los optimistas no genera envidia entre los pesimistas y viceversa. Por lo tanto, la distribución general no genera envidia y es casi exacta.
