Protocolo Even-Paz

El algoritmo Even-Paz es un algoritmo computacionalmente eficiente para dividir la torta de manera justa . Implica un determinado recurso heterogéneo y divisible, como una torta de cumpleaños, y n socios con diferentes preferencias sobre distintas partes de la torta. Permite que las n personas logren una división proporcional .

Historia

El primer algoritmo publicado para la división proporcional de una torta fue el último algoritmo reductor , publicado en 1948. Su complejidad en tiempo de ejecución era O( n ^2 ). En 1984, Shimon Even y Azaria Paz publicaron su algoritmo mejorado, cuya complejidad en tiempo de ejecución es solo O( n log n ). ^[1]

Descripción

El algoritmo utiliza una estrategia de divide y vencerás, es posible lograr una división proporcional en el tiempo O( n log n ).

A cada uno de los participantes se le pide que dibuje una línea que divida la torta en una parte derecha y otra izquierda de manera que crea que la razón es ⌊ n /2⌋:⌈ n /2⌉. Los cortes deben ser sin intersecciones; una forma sencilla de garantizar esto es permitir solo líneas horizontales o solo líneas verticales.
El algoritmo ordena las n líneas en orden creciente y corta el pastel en la mediana de las líneas, es decir, en la línea ⌊ n /2⌋. Por ejemplo, si hay 5 socios que dibujan líneas en x = 1, x = 3, x = 5, x = 8 y x = 9, entonces el algoritmo corta el pastel verticalmente en x = 5.
El algoritmo asigna a cada una de las dos partes los socios cuya línea está dentro de esa parte, es decir, los socios que dibujaron las primeras ⌊ n /2⌋ líneas se asignan a la parte izquierda, los demás a la parte derecha. Por ejemplo, los socios que dibujaron líneas en x = 1, x = 3 y x = 5 se asignan a la parte izquierda y los demás socios se asignan a la parte derecha. Cada parte se divide recursivamente entre los socios que se le asignan.

Es posible demostrar por inducción que a cada compañero que juega según las reglas se le garantiza una pieza con un valor de al menos 1/ n , independientemente de lo que hagan los otros compañeros.

Gracias a la estrategia de divide y vencerás, el número de iteraciones es solo O(log n ), en contraste con O( n ) en el procedimiento Last Diminisher. En cada iteración, cada participante debe hacer una sola marca. Por lo tanto, el número total de marcas requeridas es O( n log n ).

Optimalidad

Varios años después de la publicación del algoritmo Even-Paz, se demostró que todo procedimiento de división proporcional determinista o aleatorio que asigne a cada persona una pieza contigua debe utilizar Ω( n log n ) acciones. ^[2]

Además, todo procedimiento de división proporcional determinista debe utilizar Ω( n log n ) acciones, incluso si se permite que el procedimiento asigne a cada socio una parte no contigua, e incluso si se permite que el procedimiento solo garantice una imparcialidad aproximada . ^[3]

Estos resultados de dureza implican que el algoritmo Even-Paz es el algoritmo más rápido posible para lograr una proporcionalidad total con piezas contiguas, y es el algoritmo determinista más rápido posible para lograr una proporcionalidad parcial e incluso con piezas desconectadas. El único caso en el que se puede mejorar es con algoritmos aleatorios que garanticen una proporcionalidad parcial con piezas desconectadas; véase el algoritmo de Edmonds-Pruhs .

Versión aleatoria

Es posible utilizar la aleatorización para reducir el número de marcas. La siguiente versión aleatoria del procedimiento de reducción recursiva a la mitad logra una división proporcional utilizando solo O( n ) consultas de marcas en promedio. ^[1] La idea es que, en cada iteración, en lugar de pedir a todos los socios que hagan una marca de medio valor, solo se pide a algunos socios que hagan tales marcas, mientras que los otros socios solo eligen qué mitad prefieren. Los socios son enviados al oeste o al este según sus preferencias, hasta que el número de socios en cada lado sea n /2. Luego se hace un corte, y cada grupo de n /2 socios divide su mitad recursivamente. ^[4]

En el peor de los casos, todavía necesitamos n -1 puntos por iteración, por lo que el número de puntos requeridos en el peor de los casos es O( n log n ). Sin embargo, en promedio, solo se requieren O(log n ) puntos por iteración; al resolver una fórmula de recurrencia, es posible demostrar que el número promedio de puntos requeridos es O( n ).

Téngase en cuenta que el número total de consultas sigue siendo O( n log n ), ya que cada socio tiene que seleccionar la mitad.

Referencias

^ ab Even, S.; Paz, A. (1984). "Una nota sobre el corte de la torta". Matemáticas Aplicadas Discretas . 7 (3): 285. doi : 10.1016/0166-218x(84)90005-2 .
^ Sgall, Jiří; Woeginger, Gerhard J. (2007). "Sobre la complejidad del corte de la torta". Optimización discreta . 4 (2): 213–220. doi : 10.1016/j.disopt.2006.07.003 .
^ Edmonds, Jeff (2006). "Cortar la torta no es realmente tarea fácil". Actas del decimoséptimo simposio anual ACM-SIAM sobre algoritmos discretos - SODA '06 . págs. 271–278. doi :10.1145/1109557.1109588. ISBN 978-0898716054., Edmonds, Jeff (2011). "Cortar la torta no es realmente tarea fácil". ACM Transactions on Algorithms . 7 (4): 1–12. CiteSeerX 10.1.1.146.1536 . doi :10.1145/2000807.2000819. S2CID 2440968.
^ Este algoritmo de reducción a la mitad recursivo aleatorio es similar a un algoritmo aleatorio bien conocido para clasificación : encontrar el elemento clasificado r en una matriz de números.