Algoritmo de corte de torta sin envidia de Robertson-Webb
El protocolo Robertson-Webb es un protocolo para cortar pasteles sin envidia 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 luego en 1998. [2] : 128–133
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 conectados, de manera que, por cada dos agentes i y h :
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 del pastel entre n /2 agentes sin envidia, no podemos 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 para ser envidiosos (p. ej., es posible que A y B crean que obtuvieron la mitad de su mitad, que es 1/4 de todo el pastel; C y D también creen lo mismo; pero A cree que C en realidad obtuvo la mitad completa mientras que D no obtuvo nada, por lo que A envidia a C).