Protocolo de Edmonds-Pruhs

El protocolo Edmonds-Pruhs es un protocolo para el corte justo de un pastel . Su objetivo es crear una división parcialmente proporcional de un recurso heterogéneo entre n personas, de manera que cada persona reciba un subconjunto del pastel que esa persona valore como al menos 1/ an del total, donde${\displaystyle a\geq 10}$es una constante suficientemente grande. Es un algoritmo aleatorio cuyo tiempo de ejecución es O( n ) con una probabilidad cercana a 1. El protocolo fue desarrollado por Jeff Edmonds y Kirk Pruhs , quienes posteriormente lo mejoraron en un trabajo conjunto con Jaisingh Solanki .

La división proporcional de un pastel se puede lograr utilizando el algoritmo de división recursiva por la mitad en tiempo O( n  log n ). Varios resultados de complejidad computacional demuestran que este tiempo de ejecución es óptimo bajo una amplia variedad de supuestos. En particular, la división recursiva por la mitad es el algoritmo más rápido posible para lograr una proporcionalidad completa cuando las piezas deben ser contiguas, y es el algoritmo determinista más rápido posible para lograr incluso una proporcionalidad parcial, incluso cuando se permite que las piezas estén desconectadas. Un caso que no está cubierto por los resultados de complejidad computacional es el de los algoritmos aleatorios , que garantizan solo una proporcionalidad parcial y con piezas posiblemente desconectadas . El protocolo de Edmonds-Pruhs tiene como objetivo proporcionar un algoritmo con un tiempo de ejecución O( n ) para este caso. 

El esquema general es el siguiente: ^{[ 1 ]}

1. Cada socio divide privadamente el pastel en an porciones de igual valor subjetivo. Estas n  ⋅ an porciones se denominan porciones candidatas . 
2. Cada participante elige 2d piezas candidatas al azar de forma uniforme, con reemplazo ( d es una constante que se determinará más adelante). Las candidatas se agrupan en d pares, que el participante comunica al algoritmo. Estos n⋅d pares se denominan cuadros de cuartos de final .
3. De cada cuadro de cuartos de final, el algoritmo selecciona una sola pieza: la pieza que se interseca con el menor número de otras piezas candidatas. Estas n  ⋅ d piezas se denominan piezas de semifinal . 
4. Para cada socio, el algoritmo selecciona una pieza; estas se denominan piezas finales . Las piezas finales se seleccionan de manera que cada punto del pastel quede cubierto por un máximo de dos piezas finales (véase más abajo). Si esto tiene éxito, pase al paso 5. Si falla, vuelva a empezar desde el paso 1.
5. Cada porción del pastel que pertenece a una sola pieza final se entrega al dueño de dicha pieza. Cada porción del pastel que pertenece a dos piezas finales se divide proporcionalmente mediante cualquier algoritmo de división proporcional determinista.

El algoritmo garantiza que, con alta probabilidad, cada socio recibe al menos la mitad de una de sus piezas candidatas, lo que implica (si los valores son aditivos) un valor de al menos  1/2 an .

Hay O( n ) piezas candidatas y O( n ) divisiones adicionales en el paso #5, cada una de las cuales toma O(1) tiempo. Por lo tanto, el tiempo total de ejecución del algoritmo es  O( n ).

El principal desafío de este esquema es seleccionar las piezas finales en el paso #4:

Comience creando el grafo de implicación : un grafo cuyos nodos son las piezas semifinales, y existe una arista desde la pieza I del socio i a la pieza J del socio j si la pieza I interseca la otra pieza del socio j (por lo tanto, si seleccionamos la pieza I y queremos evitar la intersección, también debemos seleccionar la pieza J ).

Seleccione un socio arbitrario i que aún no haya recibido una pieza y seleccione una pieza arbitraria I de ese socio como pieza final. Luego, recorra los enlaces en el grafo de implicación y seleccione como piezas finales todas las piezas que sean alcanzables desde I. Hay dos escenarios favorables: o asignamos una sola pieza final a cada socio y terminamos, o llegamos a una pieza sin enlaces salientes (lo que implica que no intersecta con otras piezas). En este último caso, simplemente elegimos otra pieza de uno de los socios restantes y continuamos. El escenario desfavorable es que nuestro recorrido nos lleve a dos piezas diferentes del mismo socio, o equivalentemente a la otra pieza del socio i desde la que comenzamos. Dicho camino, que lleva de una pieza del socio i a otra pieza del mismo socio, se llama camino de pares . Si el grafo de implicación no contiene caminos de pares, entonces el algoritmo de selección descrito anteriormente devuelve una colección de n piezas finales no superpuestas y terminamos. Ahora queda calcular la probabilidad de que el grafo de implicación contenga un camino de pares.

Primero, consideremos el caso especial en el que todos los socios tienen la misma función de valor (y, por lo tanto, la misma colección de piezas candidatas). En este caso, la probabilidad de un camino de pares es fácil de calcular: dado que la probabilidad de cada arista es 1/ an , y todas las aristas son independientes, la probabilidad de un camino de pares específico de longitud k es  1/( an ) ^k , y la probabilidad de cualquier camino de pares es como máximo:

${\displaystyle \sum _{k}{\frac {(2dn)!}{(2dn-k)!(an)^{k}}}=O\left({\frac {1}{a^{2}}}\right)}$

Al seleccionar d = 1 y un valor de a suficientemente grande, es posible reducir esta probabilidad tanto como queramos. Esto es cierto incluso si omitimos la fase de selección de semifinales (n.º 3) y simplemente consideramos todas las piezas de cuartos de final como semifinalistas.

Cabe destacar que este caso es análogo al modelo de bolas en contenedores . Demuestra que, si se seleccionan d contenedores al azar para cada bola, entonces es posible elegir un contenedor para cada bola de manera que todos los contenedores sean distintos (la carga máxima es 1).

En el modelo general de pastel, donde las funciones de valor son diferentes, las probabilidades de las aristas en el grafo de implicación son dependientes. Pero gracias a la fase de selección semifinal, podemos demostrar que la probabilidad de que el grafo de implicación contenga un camino de pares de longitud al menos 3 es como máximo${\displaystyle {\frac {32d^{5}}{a^{2}\cdot (a-4d^{2})}}}$.

Queda por manejar rutas de pares de longitud 2. Desafortunadamente, la probabilidad de tener tales rutas de pares en el grafo de implicación no es despreciable. Sin embargo, con alta probabilidad es posible particionar los socios en dos grupos, de modo que en cada grupo no haya ninguna ruta de pares de longitud 2. Por lo tanto, podemos ejecutar el algoritmo de selección de piezas finales dos veces: una para cada grupo. La intersección solo puede ocurrir entre piezas finales de diferentes grupos; por lo tanto, la superposición en cada punto del pastel es como máximo 2. La probabilidad de que tal partición de 2 no sea posible es como máximo${\displaystyle {\frac {16d^{3}}{a^{3}}}+{\frac {8d^{2}}{a^{2}}}}$.

Sumando las dos expresiones anteriores y estableciendo d  =  2, obtenemos que la probabilidad de falla sigue siendo${\displaystyle O\left({\frac {1}{a^{2}}}\right)}$. Recuerde que a es la razón de proporcionalidad: cuanto más valor queramos garantizar a cada socio, más probable será que la división fracase y tengamos que volver a empezar desde el paso #1.

El mismo algoritmo funciona también cuando los cortes son aproximados, es decir, los socios no saben marcar las piezas con el mismo valor exacto; podrían marcar una pieza con un valor p por ciento por encima o por debajo del valor requerido, donde el error exacto se elige al azar. ^{[ 1 ]}

Es posible reducir aún más la probabilidad de fallo utilizando el siguiente esquema: ^{[ 2 ]}

• Realice dos ejecuciones independientes del protocolo original.
• En cada ejecución, elimine a cada compañero que aparezca al principio de una ruta de pares y asigne las piezas finales solo a los compañeros restantes, como en el protocolo original.
• Si para cada compañero hay al menos una secuencia en la que no se elimina, entonces hemos terminado, ya que cada compañero ahora tiene al menos una pieza final.

La probabilidad de eliminar a un socio específico en cada ejecución es${\displaystyle O\left({\frac {1}{n}}\right)}$. La probabilidad de eliminar a un socio específico en ambas ejecuciones es${\displaystyle O\left({\frac {1}{n^{2}}}\right)}$Por lo tanto, la probabilidad de falla es${\displaystyle O\left({\frac {n}{n^{2}}}\right)=O\left({\frac {1}{n}}\right)}$, que tiende a 0 cuando n aumenta, incluso cuando la razón de proporcionalidad parcial a se mantiene constante.

El modelo de pastel puede considerarse una generalización del modelo de bolas en contenedores . Este modelo ha encontrado amplias aplicaciones en áreas como el balanceo de carga . En estas situaciones, una bola representa una tarea que puede asignarse a varios contenedores/máquinas. En términos generales, el balanceo de carga de máquinas idénticas es a las bolas y los contenedores lo que el balanceo de carga en máquinas no relacionadas es al corte de un pastel. Por lo tanto, es razonable que el modelo de pastel y el protocolo de Edmonds-Pruhs tengan aplicaciones interesantes en entornos que implican el balanceo de carga en máquinas no relacionadas. ^{[ 1 ]}