211service.com
Die überraschend komplexe Kunst des Kuchenschneidens
Mathematiker lieben einen guten Kuchen, daher ist es kaum verwunderlich, dass das Problem, wie man beispielsweise einen Victoria-Schwamm schneidet und zuteilt, sie stark beansprucht hat. Heute werden sich Kuchenliebhaber über einen bedeutenden Durchbruch freuen.
Das Problem ist folgendes: Wie schneidet man einen Kuchen und teilt ihn gerecht auf n Menschen, wenn jeder eine andere Meinung über den Wert jedes Stücks hat?
1980 bewies Walter Stromquist vom Swarthmore College in der Nähe von Philadelphia, dass es eine neidfreie Lösung für das Problem gibt. Mit anderen Worten, es ist möglich, einen Kuchen in n stücke mit n −1 schneidet und jeder Person ein Stück zuteilt, damit jeder sein Stück nicht weniger schätzt als jedes andere Stück.
Aber obwohl eine Lösung möglich sein mag, ist es schwierig, sie zu finden. Die offene Frage ist heute, ob es einen effizienten Algorithmus gibt, der ein solches Stück vom Kuchen findet, sagen Xiaotie Deng von der City University of Hong Kong und ein paar Kumpel.
Ihr Beitrag zum Problem besteht darin, einen solchen Algorithmus zu finden, wenn auch mit ein paar kleineren Einschränkungen. Beeindruckenderweise arbeitet ihr Algorithmus in polynomieller Zeit, was bedeutet, dass eine Lösung immer relativ schnell gefunden werden kann.
Die Vorbehalte? Der Algorithmus funktioniert beim Aufteilen eines Kuchens nur auf drei Personen und dann nur für den Sonderfall mathematischer Objekte, genannt messbare Nutzenfunktionen, und das Ergebnis ist nur annähernd neidfrei.
Trotzdem sollte das immer noch praktisch sein, wenn es bei der nächsten Junior-Gemeinschaftsraum-Teeparty zu Streitigkeiten kommt.
Ref: arxiv.org/abs/0907.1334 : Über die Komplexität des neidfreien Kuchenschneidens