Protocolo de Robertson-Webb

El protocolo de Robertson-Webb es un protocolo de corte de torta envidioso que también es casi preciso . El protocolo tiene las siguientes propiedades:

Funciona para cualquier número ( n ) de participantes.
Funciona para cualquier conjunto de pesos que representen las distintas apuestas debidas a los participantes.
Las piezas que se pasan a los participantes no están necesariamente conectadas, es decir, cada participante puede recibir un conjunto de pequeñas “migas”.
El número de solicitudes es finito, pero no se conoce; no se sabe de antemano cuántas solicitudes se requerirán.

El protocolo fue desarrollado por Jack M. Robertson y William A. Webb. Fue publicado en 1997 por Robertson [1] y posteriormente en 1998 por Robertson y Webb [2] .

Detalles

La principal dificultad para desarrollar un procedimiento para obtener una división sin envidia entre los agentes es que la tarea no es "descomponible". Es decir, si compartimos la mitad del pastel entre n /2 agentes en ausencia de envidia, no podemos compartir la otra mitad del pastel entre otros n /2 agentes, ya que los miembros del primer grupo pueden ponerse celosos (por ejemplo, puede suceder que A y B piensen que obtuvieron 1/2 de su mitad, que es 1/4 de todo el pastel. C y D podrían pensar de la misma manera, pero A pensaría que C obtuvo la mitad entera y D no obtuvo ninguno, por lo que A estaría celoso de C). $norte > 2$

El protocolo de Robertson-Webb intenta resolver esta dificultad exigiendo que no solo no haya envidia en la división, sino que también sea casi exacta. A continuación se muestra la parte recursiva del protocolo.

Iniciar sesión

Cualquier pedazo de pastel X ;
cualquiera ; $\varepsilon >0$
n participantes, ; $A_{1},\puntos,A_{n}$
m<n participantes que son aceptados como "jugadores activos" (otros participantes son aceptados como "observadores"); ${\displaystyle A_{1},\puntos,A_{m))$ $Nuevo Méjico$
Cualquier conjunto de m pesos positivos ; ${\displaystyle w_{1},\puntos,w_{m))$

Salir

Dividir X en partes asignadas a los m jugadores activos tal que ${\displaystyle X_{1},\puntos,X_{m))$

No hay envidia en la partición por los pesos dados entre los m participantes activos. Es decir, para cualquier pareja de jugadores activos y el jugador cree que el valor de su pieza , dividido por el valor de otra pieza , no es menor que . $Ai}$ $A_{j}$ $Ai}$ $X_{yo}$ $X_{j}$ ${\tfrac{w_{i}}{w_{j}}}$
La partición es casi exacta para pesos dados entre los n jugadores, tanto activos como inactivos. $\varepsilon$

Procedimiento

Nota: La descripción del procedimiento aquí no es formal y está simplificada. Una descripción más precisa se da en el libro de Robertson y Webb [2] .

Usamos el procedimiento de división casi exacta para X y obtenemos un corte que todos los n jugadores ven como casi exacto con pesos . $\varepsilon$ ${\displaystyle w_{1},\puntos w_{m))$

Deje que uno de los jugadores activos (que sea ) corte piezas de tal manera que la partición sea exactamente para él, es decir, para cualquier . $A_{1}$ ${\displaystyle j:{\tfrac {V_{1}(X_{j})}{V_{1}(X)))=w_{j))$

Si todos los demás jugadores están de acuerdo con tal corte, simplemente le damos la pieza al jugador activo . No habrá envidia en esta división, así que obtuvimos lo que queríamos. $X_{yo}$ $Ai}$

De lo contrario, hay alguna pieza de P , sobre la cual hay desacuerdo entre los jugadores activos. Al cortar P en pedazos más pequeños, si es necesario, podemos limitar el desacuerdo para que todos los jugadores estén de acuerdo en que . ${\tfrac {V(P)}{V(X)}}<\varepsilon$

Dividamos a los jugadores activos en dos campos: "optimistas", que creen que P es más valioso, y "pesimistas", que creen que P es menos valioso. Sea tal la diferencia entre las estimaciones, que para cualquier optimista i y cualquier pesimista j , . $\delta$ ${\tfrac {V_{i}(P)}{V_{i}(X)))-{\tfrac {V_{j}(P)}{V_{j}(X)))>\ delta$

Dividamos el resto del pastel en partes Q y R para que la partición sea casi exacta para todos los n jugadores. ${\ estilo de visualización XP}$

Démoslo a los optimistas. Dado que creen que P es más valioso, necesariamente creerán que P es lo suficientemente valioso para cubrir sus acciones. $P\taza Q$ $P\taza Q$

Demos R a los pesimistas. Dado que creen que P es menos valioso, necesariamente supondrán que el resto de R es lo suficientemente valioso como para cubrir su parte.

En este punto, hemos dividido a los jugadores activos en dos campos, cada campo cree que las partes del pastel que se les asigna (para todo el campo) los satisfarán (colectivamente).

Queda por dividir cada una de estas porciones de la torta dentro del campamento. Esto se hace aplicando recursivamente el procedimiento anterior:

Dividimos recursivamente la parte entre los optimistas (es decir, los optimistas están activos, el resto solo observa). $P\taza Q$
Divide recursivamente la parte R entre los pesimistas.

En ambas aplicaciones, el parámetro de precisión cercana no debe exceder . Dado que la partición resultante es casi exacta para todos los n jugadores, la división entre optimistas no despertará envidia entre los pesimistas y viceversa. Así, la envidia no estará presente en la división final y será casi exacta. $\delta$ $\delta$

Véase también

El protocolo Brahms-Taylor es otro protocolo de división envidioso con fragmentos desconectados y un tiempo de ejecución ilimitado y finito. No garantiza una precisión cercana.
Los protocolos de Simmons-Su son un protocolo de división envidioso que garantiza la conexión de las piezas, pero el tiempo de ejecución puede ser infinito. La división de precisión cercana no está garantizada.

Notas

↑ Robertson, Webb, 1997 , pág. 97–108.
↑ 12 Robertson , Webb, 1998 , pág. 128–133.

Literatura

Jack M. Robertson, William A. Webb. División de pasteles casi exacta y sin envidias // Ars Combinatoria. - 1997. - T. 45 .
Jack Robertson, William Webb. Algoritmos de corte de torta: Sea justo si puede .. - Natick, Massachusetts: AK Peters, 1998. - ISBN 978-1-56881-076-8 .