El protocolo Edmonds-Pruhs es un protocolo para dividir el pastel de manera justa . Su objetivo es crear una división parcialmente proporcional de un recurso heterogéneo entre n personas, de modo que cada persona reciba un subconjunto del pastel que esa persona valore como al menos 1/ an del total, donde 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 luego lo mejoraron en un trabajo conjunto con Jaisingh Solanki.
Se puede lograr una división proporcional de una torta usando el algoritmo de reducción a la mitad recursivo en un tiempo O( n log n ). Varios resultados de dureza muestran que este tiempo de ejecución es óptimo bajo una amplia variedad de suposiciones. En particular, la reducción a la mitad recursiva es el algoritmo más rápido posible para lograr una proporcionalidad total cuando las piezas deben ser contiguas, y es el algoritmo determinista más rápido posible para lograr una proporcionalidad parcial e incluso cuando se permite que las piezas estén desconectadas. Un caso que no está cubierto por los resultados de dureza es el caso de algoritmos aleatorios , que garantizan solo una proporcionalidad parcial y con piezas posiblemente desconectadas . El protocolo 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]
El algoritmo garantiza que, con alta probabilidad, cada socio reciba 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 ) fragmentos candidatos y O( n ) divisiones adicionales en el paso n.° 5, cada una de las cuales lleva O(1) tiempo. Por lo tanto, el tiempo total de ejecución del algoritmo es O( n ).
El principal desafío en este esquema es seleccionar las piezas finales en el paso 4:
Comience por crear el gráfico de implicación : un gráfico cuyos nodos son las piezas semifinales, y hay una arista desde la pieza I del socio i hasta 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 gráfico de implicación y seleccione como piezas finales todas las piezas que sean alcanzables desde I. Hay dos buenos escenarios: o asignamos una única pieza final a cada socio y terminamos, o llegamos a una pieza sin enlaces salientes (lo que implica que no intersecta otras piezas). En el último caso, simplemente elegimos otra pieza de uno de los socios restantes y continuamos. El mal escenario 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. Tal camino, que lleva de una pieza del socio i a otra pieza del mismo socio, se llama camino de pares . Si el gráfico de implicación no contiene caminos de pares, entonces el algoritmo de selección que se acaba de describir devuelve una colección de n piezas finales que no se superponen y terminamos. Ahora queda calcular la probabilidad de que el gráfico de implicación contenga un camino de pares.
En primer lugar, considere 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 par 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 par específico de longitud k es 1/( an ) k , y la probabilidad de cualquier camino de par es como máximo:
Si seleccionamos d = 1 y a lo suficientemente grande, es posible hacer que esta probabilidad sea tan pequeña como queramos. Esto es así incluso si omitimos la fase de selección de semifinales (#3) y simplemente tomamos todas las piezas de cuartos de final como semifinales.
Obsérvese que este caso es análogo al modelo de bolas en contenedores . Demuestra que, si se eligen d contenedores al azar para cada bola, entonces es posible seleccionar un contenedor para cada bola de modo que todos los contenedores sean distintos (la carga máxima es 1).
En el modelo general de la torta, donde las funciones de valor son diferentes, las probabilidades de los bordes en el gráfico de implicación son dependientes, pero gracias a la fase de selección semifinal, podemos demostrar que la probabilidad de que el gráfico de implicación contenga un par de caminos con una longitud de al menos 3 es como máximo .
Queda por manejar pares de caminos de longitud 2. Desafortunadamente, la probabilidad de tener tales pares de caminos en el gráfico de implicación no es despreciable. Sin embargo, con alta probabilidad es posible dividir los socios en dos grupos, de modo que en cada grupo no haya un par de caminos 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 de la torta es como máximo 2. La probabilidad de que tal división en dos no sea posible es como máximo .
Sumando las dos expresiones anteriores y estableciendo d = 2, obtenemos que la probabilidad de fracaso sigue siendo . Recordemos que a es la razón de proporcionalidad: cuanto mayor sea el valor que queramos garantizar a cada socio, más probable será que la división fracase y tengamos que empezar de nuevo en el paso n.° 1.
El mismo algoritmo funciona también cuando los cortes son aproximados, es decir, los socios no saben marcar piezas con exactamente el mismo valor; pueden marcar una pieza con un valor de 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]
La probabilidad de eliminar a un socio específico en cada ejecución es . La probabilidad de eliminar a un socio específico en ambas ejecuciones es . Por lo tanto, la probabilidad de fracaso es , que tiende a 0 cuando n aumenta, incluso cuando la razón de proporcionalidad parcial a se mantiene constante.
El modelo de la torta puede verse como una generalización del modelo de bolas en contenedores . Este modelo ha encontrado amplias aplicaciones en áreas como el equilibrio de carga . En estas situaciones, una bola representa un trabajo que se puede asignar a varios contenedores/máquinas. En términos generales, el equilibrio de carga de máquinas idénticas es para las bolas y los contenedores, lo que el equilibrio de carga en máquinas no relacionadas es para el corte de una torta. Por lo tanto, es razonable que el modelo de la torta y el protocolo de Edmonds-Pruhs tengan aplicaciones interesantes en entornos que involucran el equilibrio de carga en máquinas no relacionadas. [1]
