El año pasado, dos jóvenes teóricos de la computación lograron resolver un problema con el que los matemáticos llevaban décadas luchando: cómo repartir una tarta de manera justa entre un número arbitrario de personas. Su trabajo dejó perplejos a los numerosos investigadores que pensaban que era poco probable que existiese un protocolo de división justa de ese tipo.

El pastel funciona aquí como metáfora de un amplio conjunto de problemas del mundo real en los que hay que repartir algún objeto continuo —ya se trate de una tarta o de una extensión de tierra— entre varias personas, cada una de las cuales valora sus características de manera diferente: unas se desviven por el glaseado de chocolate, pongamos por caso, mientras que otras no apartan la vista de las flores de crema.

Al menos desde tiempos bíblicos se sabe que hay una forma de repartir un objeto entre dos personas de modo que, al final, ambas queden satisfechas: una lo divide en dos trozos que para ella tengan el mismo valor, y la otra elige cuál prefiere. En el libro del Génesis, Abraham (por entonces Abram) y Lot se valieron de este truco de “yo corto, tú escoges” para repartir la tierra: Abraham decidió cómo dividirla y Lot pudo escoger entre Canaán y el este del río Jordán.

Hacia 1960, los matemáticos concibieron un algoritmo similar para tres jugadores. Pero, hasta ahora, lo mejor que se había conseguido para más de tres agentes era un procedimiento ideado en 1995 por el politólogo Steven Brams, de la Universidad de Nueva York, y el matemático Alan Taylor, del Union College de Schenectady, también en Nueva York. Dicho protocolo garantizaba una división justa, pero no estaba acotado; es decir, podía necesitar un millón de pasos hasta llegar al reparto, mil millones o cualquier otra gran cantidad de ellos en función de las preferencias de los jugadores.

En su momento, el algoritmo de Brams y Taylor fue alabado como un gran avance en el campo. Sin embargo, “el hecho de que no estuviese acotado suponía una gran desventaja”, explica Ariel Procaccia, teórico de la computación de la Universidad Carnegie Mellon y uno de los creadores de Spliddit, una herramienta gratuita en línea que proporciona algoritmos de división justa para cuestiones como repartir el alquiler o las labores domésticas entre compañeros de piso.

Durante los últimos cincuenta años, numerosos matemáticos y teóricos de la computación, Procaccia incluido, se habían convencido de que probablemente no hubiese ningún algoritmo justo y acotado para repartir un pastel entre n jugadores. “Ese fue precisamente el problema que me llevó a estudiar los repartos justos”, explica Walter Stromquist, profesor de matemáticas en el Colegio Universitario Bryn Mawr, en Pensilvania, quien en 1980 demostró varios resultados muy influyentes sobre el problema del reparto de pasteles. “Toda mi vida he pensado que volvería a ello cuando

tuviese tiempo y que demostraría que esa extensión particular del resultado era imposible.”
En abril del año pasado, sin embargo, dos teóricos de la computación superaron todas las expectativas cuando publicaron un artículo en línea en el que describían un algoritmo de reparto justo cuyo tiempo de cómputo solo dependía del número de jugadores, no de sus preferencias individuales. Uno de ellos, Simon Mackenzie, por entonces investigador posdoctoral de 27 años en Carnegie Mellon, presentó el resultado el pasado 10 de octubre en el Simposio sobre Fundamentos de la Teoría de la Computación del Instituto de Ingeniería Eléctrica y Electrónica (IEEE), uno de los congresos anuales más prestigiosos en ciencias de la computación.

El algoritmo resulta extraordinariamente complejo: dividir un pastel entre n comensales puede requerir hasta nˆnˆnˆnˆnˆnˆn pasos (donde el símbolo ˆ se usa aquí para expresar “elevado a”) y un número equiparable de tajadas. Incluso para unos pocos jugadores, dicha cifra supera la cantidad de átomos existentes en el universo. Con todo, los investigadores ya cuentan con algunas ideas para simplificar y acelerar el algoritmo, señala Haris Aziz, el otro miembro del equipo. Aziz, de 36 años, es teórico de la computación en la Universidad de Nueva Gales del Sur y en Data61, un grupo de investigación australiano. Procaccia asegura que, para quienes se dedican a la teoría de la división justa, este es definitivamente “el mayor resultado en décadas”.

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 n2 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.

Fuente: investigacionyciencia.es