L'art étonnamment complexe de la coupe de gâteaux

Les mathématiciens aiment un bon gâteau, il n'est donc pas surprenant que le problème de la façon de couper et de répartir une éponge Victoria, par exemple, les ait durement mis à l'épreuve. Aujourd'hui, les amateurs de gâteaux seront ravis d'entendre parler d'une percée importante.

Le problème est le suivant : comment couper un gâteau et le répartir équitablement entre m personnes alors que chaque personne peut avoir une opinion différente de la valeur de chaque pièce ?

En 1980, Walter Stromquist du Swarthmore College près de Philadelphie a prouvé qu'il existait une solution sans envie au problème. En d'autres termes, il est possible de couper un gâteau en m pièces utilisant m -1 coupes et d'attribuer une pièce à chaque personne afin que chacun valorise sa pièce au moins autant que n'importe quelle autre pièce.

Mais bien qu'une solution soit possible, la trouver est difficile. La question ouverte aujourd'hui est de savoir s'il existe un algorithme efficace qui trouve une telle part du gâteau, déclarent Xiaotie Deng de la City University of Hong Kong et quelques amis.

Leur contribution au problème est de trouver un tel algorithme, mais avec quelques mises en garde mineures. De manière impressionnante, leur algorithme fonctionne en temps polynomial, ce qui signifie qu'une solution peut toujours être trouvée assez rapidement.

Les mises en garde ? L'algorithme fonctionne lors de la division d'un gâteau uniquement entre trois personnes et uniquement pour le cas particulier impliquant des objets mathématiques appelés fonctions d'utilité mesurables, et le résultat n'est qu'approximativement sans envie.

Néanmoins, cela devrait toujours être utile lorsqu'un différend survient lors du prochain goûter de la salle commune junior.

Réf : arxiv.org/abs/0907.1334 : Sur la complexité de la coupe de gâteau sans envie

cacher