Activa las notificaciones para estar al tanto de lo más nuevo en tecnología.

Algoritmos para partir un pastel en rebanadas iguales

El problema parece simple: corte un pastel de manera que cada persona piense que le toca una parte justa. Si quitamos a los tramposos y...

Corte del pastel

El problema parece simple: corte un pastel de manera que cada persona piense que le toca una parte justa. Si quitamos a los tramposos y a los envidiosos, veremos que quizás hay algún problema. Pero no se preocupe, hay un algoritmo que trabaja incluso cuando el pastel es compartido a través de internet.

Cortar un pastel no parece ser a todas luces un problema importante, pero si en lugar de pastel hablamos de compartir un territorio, entonces nos daremos cuenta que hay asuntos a considerar y espacio para muchas aplicaciones prácticas. Incluso, puede ser útil si hay un pastel real que se está compartiendo, pero esto sólo tendrá sentido si quienes comparten el postre son programadores.

Antes de decidir cómo partir un pastel vayamos al caso más simple, que es cuando dos personas lo comparten. Si ambos valoran el pastel de la misma manera, es obvio que ambos querrán la misma cantidad. Para hacer las cosas interesantes, supongamos que cada persona tiene una función u1 y u2 respectivamente, que mide qué tanto valoran diferentes tamaños de pastel.

Al introducir estas funciones, el problema se vuelve más interesante porque cada participante tiene diferentes puntos de vista de las porciones del pastel. Lo que importa en este problema es que todos piensen que tiene al menos una parte justa (o más) del pastel, de acuerdo a las funciones u.

Entonces, ¿cómo partimos el pastel entre dos personas?

Una solución es usar el algoritmo ‘divide y elige’. Uno de los participantes corta el pastel y el otro hace la elección de qué pedazo quiere. Quien corta buscará dividir en dos porciones iguales el pastel, como bien podrían medirse por su propia función u. Quien elige podrá seleccionar el pedazo que es más grande, de acuerdo a su función u o de manera azarosa (si ambos trozos se ven más o menos iguales).

Es curioso pero este algoritmo tiene un número de propiedades deseables. El que corta busca dividir el pastel de forma igual de manera que no importa qué pedazo elija la otra parte, con la intención de que parezca que el pastel se dividió en partes iguales, no importa qué digan las funciones u de cada uno. Quien elige estará feliz de ser quien seleccione la parte más grande o la que sea igual a la otra.

Pero generalicemos el algoritmo a un problema con n personas. Lo justo sería que cada participante recibiese 1/n fracción de pastel (o más si se puede). Para n=2, el algoritmo ‘divide y elige’ es bueno y probablemente el ‘más justo’. ¿Cómo hacemos para n>2? Por ejemplo, el algoritmo del cuchillo en movimiento Dubins-Spanier usa un elemento llamado “tercera persona en la que se confía (TTP por sus siglas en inglés). El TTP mueve el cuchillo a lo largo del pastel, que para simplificar las cosas, asumimos que es rectangular.

Cuando el cuchillo se mueve a la rebanada S, debe ver si crece en tamaño. Cada uno de los participantes usa su función ui(A) y lo primero que observa es que ui(A) = ui(pastel)/n de forma que eso marca donde debe detenerse el cuchillo, que es cuando las rebanadas no pasan el tamaño 1/n. Esto se repite a los n-1 participantes con el resto del pastel.  Nótese que cada participante obtiene una rebanada de al menos 1/n del pastel y que, de nuevo, hacer trampa está fuera de discusión, porque entonces alguien recibirá una rebanada más chica. El algoritmo del cuchillo parece simple, pero puede ser difícil de ver si realmente es justo y para probarlo hay que elaborar más.

Hay dos problemas con este algoritmo: el primero es que sólo trabaja si la división es continua y si todos los participantes pueden ver lo que está pasando al hacer los cortes del pastel y que pueden pedir que el procedimiento se detenga de forma inmediata.

Sin embargo, podemos hacer uso de un nuevo algoritmo asíncrono, que es posible usar para compartir pasteles hasta en internet, por decirlo de alguna manera. Los detalles lo hacen un poco complicado porque involucra a la criptografia pues cada participante apuesta en forma encriptada de forma que se sepa cuál es su apuesta sin saber las de los demás (es decir, el tamaño que debe usarse para cortar el pastel, según cada participante). A esto se le llama encriptación holomórfica. Con esto en mente, el algoritmo funciona así:

Primero, asúmase que el pastel debe ser compartido entre 2 y 2m personas, que es el entero más largo que podemos usar en cualquier punto para cortar el pastel. Cada jugador trabaja usando su punto de corte xi para que la rebanada que obtenga sea 1/n del total del pastel, considerando esto vía su función u. Este punto de corte está encriptado y se envía a los otros participantes de forma segura.

Todos los jugadores hacen su máxima apuesta y el jugador que hace la apuesta máxima, sin revelar las otras, es quien gana, obteniendo el pedazo que dijo era el adecuado. Una vez más, como en el caso del cuchillo que se mueve, el resultado es que los participantes obtienen al menos 1/n del pastel completo a través de su manera de medir. Como en el caso del algoritmo del cuchillo en movimiento, los participantes que ganan toman la rebanada correspondiente y el procedimiento se repite con el resto del pastel.  Se asume desde luego que nadie quiere pasarse de vivo ni busca hacer trampa, sino que intenta que sea justo para todos.

Lo simpático de este procedimiento es que puede hacerse asíncronamente. Cada jugador en la repartición del pastel pondrá su punto de corte que represente lo que es simplemente justo. No necesita saber las apuestas de los demás. Lo que sabe es que gana el que haya apostado el máximo y que además, puede hacerlo sin tener que estar en sincronía con los demás.

Fuente:  i-programmer.

Comentarios