Trozos de pastel

El algoritmo de Aziz y Mackenzie se basa en un elegante procedimiento ideado de manera independiente por los matemáticos John Selfridge y John Conway hacia 1960. Dicho algoritmo determina cómo repartir un pastel entre tres personas.

Si Alicia, Benito y Carlos desean dividir una tarta, el protocolo establece que, en primer lugar, Carlos deberá cortar el pastel en tres porciones igualmente valiosas desde su punto de vista. Después, Alicia y Benito dirán qué trozo prefieren. Si son distintos, habremos concluido: cada uno se lleva la porción que prefiere, Carlos toma la que sobra y todos marchan felices a casa.

Si Alicia y Benito desean el mismo pedazo, entonces Benito deberá extraer de él una pequeña rebanada, de tal modo que la parte que quede tenga el mismo valor que su segunda elección. La rebanada extraída se reserva para más adelante. Ahora Alicia toma el trozo que prefiere de los tres disponibles. Luego lo hará Benito, con la condición de que, si Alicia no escogió la porción recortada, él deberá llevársela. Por último, Carlos tomará el tercer pedazo.

Llegados aquí, ningún jugador envidia la elección de otro. Alicia está satisfecha, pues ha elegido primero. Benito también, ya que ha acabado con uno de sus dos trozos preferidos, los cuales eran igualmente valiosos para él. Y lo mismo ocurre con Carlos, pues ha conseguido una de las tres piezas originales, las cuales eran idénticas desde su punto de vista.

Sin embargo, aún queda por repartir la pequeña rebanada que extrajo Benito. Lo que hace que resulte posible dividirla sin caer en un bucle infinito de más y más divisiones y elecciones es el hecho de que Carlos está más que contento con su porción de pastel: no se sentiría engañado aunque quien se llevó la porción recortada obtuviese también toda la rebanada que queda por repartir, ya que la porción recortada más la rebanada equivalen a uno de los tres pedazos originales. Aziz y Mackenzie expresan esta relación entre los jugadores diciendo que Carlos «domina» a quien tomó la porción recortada.

Si, por ejemplo, fue Alicia quien se llevó la porción recortada, el algoritmo procede ahora como sigue: Benito divide la rebanada en tres pedazos que considera igualmente valiosos; después Alicia escoge uno, luego Carlos y finalmente Benito. Todos vuelven a estar satisfechos: Alicia, porque escogió primero; Carlos, porque ha elegido un pedazo mejor que el de Benito (y porque no le importaba cuánto se hubiese llevado Alicia); y Benito, porque esos tres pedazos eran igualmente apetitosos desde su punto de vista.

En su algoritmo de 1995, Brams y Taylor emplearon la noción de dominación —aunque no la llamaron de esa manera—, pero no consiguieron explotarla para obtener un algoritmo acotado. Durante los veinte años que siguieron, nadie consiguió mejorar el resultado. «No creo que sea por no haberlo intentado», apunta Procaccia. 

Pasteleros novatos

Cuando Aziz y Mackenzie decidieron abordar el problema hace poco más de dos años, ambos eran relativamente primerizos en el problema del reparto justo. «No teníamos tanta formación como quienes habían estado trabajando intensamente en él», reconoce Aziz. «Aunque eso suele suponer un obstáculo, en este caso creo que nos benefició, ya que no estábamos pensando de la misma manera».

Aziz y Mackenzie comenzaron a tantear el terreno estudiando desde cero el problema para tres jugadores. Su análisis finalmente les permitiría encontrar un algoritmo acotado para el caso de cuatro agentes, el cual publicaron en línea en 2015. En un principio no supieron ver cómo extenderlo a más de cuatro jugadores, pero se zambulleron febrilmente en el problema. «Tras publicar nuestro artículo para el caso de cuatro agentes, estábamos realmente entusiasmados con la idea de intentarlo antes de que alguien con mucha más experiencia e ingenio lo generalizase al caso de n agentes», explica Aziz. Un año después, sus esfuerzos rindieron fruto.

Al igual que el algoritmo de Selfridge-Conway, el enrevesado protocolo de Aziz y Mackenzie se basa en pedir repetidas veces a los distintos jugadores que dividan el pastel en n piezas idénticas, para después solicitar a otros participantes que extraigan rebanadas y elijan. Sin embargo, su algoritmo también implica otros pasos, como intercambiar de manera periódica porciones de pastel de forma cuidadosamente controlada, con vistas a aumentar las relaciones de dominación entre los jugadores.

Son esas relaciones de dominación las que han permitido a Aziz y Mackenzie reducir la complejidad del problema: si, por ejemplo, tres jugadores dominan a todos los demás, pueden irse a casa con sus respectivas porciones de tarta, ya que estarán satisfechos con ellas independientemente de quién se lleve las rebanadas sobrantes. Eso hace que queden menos jugadores de los que preocuparse y que, después de un número acotado de pasos, el pastel se reparta por completo y todos acaben felices.

«Al mirar atrás y ver lo enrevesado que es el algoritmo, no sorprende que pasase tanto tiempo antes de que alguien encontrase uno», señala Procaccia. Sin embargo, Aziz y Mackenzie creen que podrán simplificar su algoritmo de manera considerable hasta convertirlo en uno que no requiera intercambios de pastel y que lleve menos de nˆnˆn pasos.

Brams opina que es poco probable que un algoritmo más simple tenga consecuencias prácticas: las porciones que típicamente recibiría cada jugador incluirían numerosas pequeñas migajas de diferentes partes del pastel, lo que
no proporcionaría un enfoque práctico si de lo que se trata es, por ejemplo, de repartir una extensión de terreno. A pesar de todo, para los matemáticos y teóricos de la computación que estudian el problema, el nuevo resultado «reinicia la cuestión», observa Stromquist.

Ahora que se sabe que es posible repartir de manera justa un pastel en un número acotado de pasos, Procaccia dice que la nueva meta consistirá en entender el inmenso océano que separa la cota superior de Aziz y Mackenzie y el límite inferior existente en el número de cortes para dividir un pastel. En su día, Procaccia demostró que un algoritmo de reparto justo necesitaría al menos n² pasos. Sin embargo, esa cifra palidece en comparación con nˆnˆnˆnˆnˆn o incluso con nˆnˆn. Aziz señala que ahora los investigadores deberán encontrar cómo achicar esa brecha. «Creo que es posible avanzar en ambas direcciones», concluye el investigador.

Este artículo apareció originalmente en QuantaMagazine.org,
una publicación independiente promovida por la Fundación
Simons para potenciar la comprensión pública de la ciencia.