El sorprendentemente complejo arte de cortar pasteles

A los matemáticos les encanta un buen pastel, por lo que no es de extrañar que el problema de cómo cortar y distribuir una esponja Victoria, digamos, les haya ejercitado mucho. Hoy, los amantes de los pasteles estarán emocionados de saber de un avance significativo.

El problema es este: ¿cómo se corta un pastel y se lo divide equitativamente entre norte personas cuando cada persona puede tener una opinión diferente sobre el valor de cada pieza?

En 1980, Walter Stromquist en Swarthmore College cerca de Filadelfia demostró que había una solución libre de envidia al problema. En otras palabras, es posible cortar un pastel en norte piezas usando norte −1 cortes y asignar una pieza a cada persona para que todos valoren su pieza no menos que cualquier otra pieza.

Pero aunque puede ser posible encontrar una solución, es difícil encontrarla. La pregunta abierta hoy es si existe un algoritmo eficiente que encuentre tal parte del pastel, dicen Xiaotie Deng de la City University of Hong Kong y un par de amigos.

Su contribución al problema es encontrar tal algoritmo, aunque con un par de salvedades menores. Sorprendentemente, su algoritmo funciona en tiempo polinomial, lo que significa que siempre se puede encontrar una solución con razonable rapidez.

¿Las advertencias? El algoritmo funciona cuando se divide un pastel solo entre tres personas y luego solo para el caso especial que involucra objetos matemáticos llamados funciones de utilidad medibles, y el resultado es solo aproximadamente libre de envidia.

Sin embargo, eso aún debería ser útil cuando surja una disputa en la próxima fiesta del té en la sala común juvenil.

Ref: arxiv.org/abs/0907.1334 : Sobre la complejidad de cortar pasteles sin envidia

esconder