Protocolo de Edmonds-Prus

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 12 de enero de 2021; la verificación requiere 1 edición .

El protocolo de Edmonds-Prus es un protocolo de corte de torta justo . Su objetivo es obtener una división parcialmente proporcional de un recurso heterogéneo entre n personas, de modo que cada participante reciba un subconjunto del pastel (pieza) que cada participante estima al menos 1/ an de la estimación total, donde es alguna constante suficientemente grande . El algoritmo es probabilístico con tiempo de ejecución O( n ) con una probabilidad de éxito cercana a 1. El protocolo fue desarrollado por Jeff Edmond y Kirk Prus, que luego mejoraron con Jaisingh Solanki. $a\geqslant 10$

Motivación

La división proporcional del pastel se puede obtener utilizando el algoritmo de bisección recursiva en el tiempo . Algunos resultados sobre la complejidad muestran que este tiempo de ejecución es óptimo en una amplia gama de supuestos. En particular, la bisección recursiva es el algoritmo más rápido para obtener la proporcionalidad total cuando las piezas deben estar conectadas, y es el algoritmo determinista más rápido posible para lograr incluso una proporcionalidad parcial e incluso si se permite cortar en piezas desconectadas. Hay un caso que no está cubierto por los resultados de complejidad, este es el caso de los algoritmos probabilísticos que garantizan solo proporcionalidad parcial y la posibilidad de piezas desconectadas . El protocolo Edmonds-Prus tiene como objetivo proporcionar un tiempo de ejecución de O( n ) solo para este caso. $O(n\log n)$

Protocolo

El esquema general, siguiendo a Edmunds y Prus, es el siguiente [1] :

Cada participante divide en privado el pastel en partes idénticas (según su evaluación subjetiva). Estas piezas se denominan piezas candidatas . $n\cdot an$
Cada participante elige 2 d piezas candidatas con igual probabilidad y retorno ( d es una constante y se definirá más adelante). Los candidatos se agrupan en d pares, que el participante informa al algoritmo. Estos emparejamientos se denominan empates de cuartos de final . $n\cdot d$
De cada paquete de cuartos de final, el algoritmo selecciona una pieza, la que tiene intersecciones con la menor cantidad de otros candidatos. Estas piezas se denominan piezas semifinales . $n\cdot d$
Para cada participante, el algoritmo selecciona una sola pieza, estas piezas se denominan finales . Las piezas finales se eligen de modo que cada punto quede cubierto por dos piezas finales como máximo (ver más abajo). Si esto tiene éxito, vaya al paso #5. Si falla, vuelva al paso 1.
Cada parte del pastel que pertenece solo a una sola pieza final se entrega al propietario de esa pieza. Cada parte del pastel que pertenece a las dos piezas finales se divide proporcionalmente mediante cualquier algoritmo de división proporcional determinista.

El algoritmo garantiza que con una alta probabilidad cada participante reciba al menos la mitad de su pieza candidata, lo que implica (si las funciones de preferencia son aditivas) que el valor será al menos . ${\tfrac{an}{2))$

Hay O( n ) piezas candidatas y O( n ) cortes adicionales en el paso 5 que toman O(1) tiempo. Por lo tanto, el tiempo total de ejecución del algoritmo es O( n ).

La tarea principal en este esquema es la elección de las piezas finales en el paso #4:

Comencemos creando un gráfico de intersección , un gráfico cuyos vértices son los fragmentos semi-finales, y existe un arco desde el fragmento I del miembro i hasta el fragmento J del miembro j si el fragmento I interseca al fragmento J del miembro j (por lo tanto, si elegimos trozo I y queremos evitar intersecciones, tenemos que seleccionar la pieza J también).

Elijamos un participante arbitrario i , que aún no ha recibido su pieza, y elijamos una pieza arbitraria I de este participante como pieza final. Luego recorremos la conexión en el gráfico de intersección y elegimos como piezas finales todas las piezas que se alcanzan desde el vértice I . Hay dos buenos escenarios: o distribuimos una pieza final a cada participante y así completamos el procedimiento, o llegamos a una pieza que no tiene enlaces salientes (lo que significa que no se cruza con otras piezas). En este último caso, simplemente seleccionamos otra pieza de uno de los miembros restantes y continuamos. El mal escenario ocurre cuando nuestro viaje conduce a dos fragmentos diferentes del mismo miembro o, de manera equivalente, a un fragmento diferente del miembro i desde el que comenzamos el viaje. Este camino que lleva de una parte del participante i a otra parte del mismo participante se llama ruta emparejada . Si el gráfico de intersección no contiene caminos emparejados, entonces el algoritmo descrito devuelve un conjunto de n piezas finales que no se superponen y tenemos el resultado deseado. Ahora queda por calcular la probabilidad de que el gráfico de intersección contenga un camino pareado.

Primero, considere el caso especial en el que todos los participantes tienen las mismas funciones de preferencia (y, por lo tanto, el mismo conjunto de piezas candidatas). En este caso, la probabilidad de un camino emparejado es fácil de calcular, ya que la probabilidad de cada arco es 1/ an y todos los bordes son independientes, por lo que la probabilidad de un camino emparejado particular de longitud k es y la probabilidad de cualquier la ruta emparejada es como máximo: ${\displaystyle {\tfrac {1}{(an)^{k))))$

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

Al elegir d = 1 y un a suficientemente grande , esta probabilidad puede hacerse arbitrariamente pequeña. Esto es cierto incluso si omitimos la fase de selección de semifinales (#3) y consideramos a todos los cuartofinalistas como semifinalistas.

Tenga en cuenta que este caso es similar al modelo de bolas en urnas . Esto prueba que si se eligen arbitrariamente urnas para cada bola, entonces se puede elegir una urna para cada bola de manera que todas las urnas sean diferentes (el número máximo de bolas es 1).

En el modelo de pastel general, cuando las funciones de preferencia son diferentes, las probabilidades de borde en el gráfico de intersección son dependientes, pero gracias a la fase de selección de semifinalistas, podemos mostrar que la probabilidad de que el gráfico de intersección contenga un camino pareado de longitud en menos 3 no excede . ${\frac {32d^{5}}{a^{2}\cdot (a-4d^{2})))$

Queda por considerar caminos emparejados de longitud 2. Desafortunadamente, la probabilidad de obtener tal camino emparejado en el gráfico de intersección no es despreciable. Sin embargo, con una alta probabilidad, es posible dividir a los participantes en dos grupos, cada uno de los cuales no tiene caminos emparejados de longitud 2. Por lo tanto, podemos ejecutar el algoritmo para elegir las piezas finales dos veces, una para cada grupo. Una intersección solo puede ocurrir entre las piezas finales de diferentes grupos, por lo tanto, la superposición en cada punto del pastel no excede 2. La probabilidad de que tal partición en 2 sea imposible no excede . ${\frac {16d^{3}}{a^{3}}}+{\frac {8d^{2}}{a^{2}}}$

Luego de sumar las dos expresiones anteriores y tomando d = 2, obtenemos que la probabilidad de falla permanece en . Recuerde que a es una relación de proporcionalidad: cuanto mayor sea el valor que queremos garantizar a cada participante, más probable es que la división falle y deba comenzar desde el paso n.º 1. $O\left({\frac {1}{a^{2))}\right)$

Algunos algoritmos también funcionan si los cortes son aproximados, es decir, los participantes no saben si las piezas marcadas son iguales. Pueden marcar una pieza con un valor de p por ciento por encima o por debajo del valor requerido, y el error exacto se elige al azar [1] .

Protocolo de alta confianza

Puede reducir aún más la posibilidad de falla utilizando el siguiente esquema [2] :

Ejecutamos el protocolo original dos veces.
En cada ejecución, eliminamos a todos los participantes que están al comienzo de la ruta emparejada y distribuimos las piezas finales solo entre los participantes restantes, como en el algoritmo original.
Si no se eliminó cada miembro en ninguna ejecución, obtuvimos lo que necesitábamos, ya que cada miembro ahora tiene una pieza final.

La probabilidad de eliminar a un participante en particular en cada pase es . La probabilidad de eliminar a un participante en particular en ambas carreras es igual a . Por lo tanto, la probabilidad de falla es , y tiende a 0 a medida que n aumenta, incluso si la relación de proporcionalidad parcial a se mantiene constante. $O\izquierda({\frac {1}{n}}\derecha)$ $O\left({\frac {1}{n^{2))}\right)$ $O\left({\frac {n}{n^{2}}}\right)=O\left({\frac {1}{n}}\right)$

Cuestiones relacionadas

El modelo de la torta se puede considerar como una generalización del modelo del problema de la pelota . Este modelo encuentra una amplia aplicación en áreas como el equilibrio de carga . En estas situaciones, la pelota representa un trabajo que se puede asignar a varias máquinas (en nuestra terminología, urnas). En términos generales, la distribución de la carga de máquinas idénticas es bolas y urnas, y la distribución de la carga de máquinas desiguales es cortar el pastel. Por lo tanto, es bastante claro que el modelo de pastel y el protocolo de Edmonds-Prus deberían tener aplicaciones interesantes en términos de distribución de carga en máquinas diferentes [1] .

Notas

↑ 1 2 3 Edmonds, Pruhs, 2006 , pág. 623.
↑ Edmonds, Pruhs, Solanki, 2008 , pág. 155–164.

Literatura

Jeff Edmonds, Kirk Pruhs. Asignaciones equilibradas de Cake // 2006 47º Simposio anual de IEEE sobre fundamentos de informática (FOCS'06). - 2006. - ISBN 978-0-7695-2720-8 . -doi : 10.1109/ focs.2006.17 .
Jeff Edmonds, Kirk Pruhs, Jaisingh Solanki. Cortar con confianza un pastel en trozos aproximadamente justos // Aspectos algorítmicos en información y gestión. - 2008. - T. 5034. - (Apuntes de cátedra en Informática). - ISBN 978-3-540-68865-5 . -doi : 10.1007 / 978-3-540-68880-8_16 .