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 .
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]
El algoritmo utiliza una estrategia de divide y vencerás, es posible lograr una división proporcional en el tiempo O( n log n ).
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 ).
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 .
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.