Das Problem bei der Aufteilung eines Kuchens – oder eines anderen kontinuierlichen Objektes, wie etwa eines Grundstücks – liegt darin, dass die beteiligten Personen die Eigenschaften des Objekts unterschiedlich bewerten. So liebt der eine den Schokoladenüberzug, die andere die Verzierungen aus Buttercreme. Seit biblischen Zeiten kennen die Menschen einen simplen Trick, etwas zwischen zwei Personen so zu teilen, dass keiner der beiden sich übervorteilt fühlt: Man lässt den einen die Teilung vollziehen und den anderen wählen, welchen der beiden Teile er nimmt. Im 1. Buch Mose wenden Abraham und Lot dieses Verfahren an, um Land aufzuteilen: Abraham zieht die Grenze, und Lot wählt zwischen dem Jordantal und Kanaan.

Um das Jahr 1960 herum entwickelten Mathematiker einen Algorithmus für eine solche »neidfreie« Teilung unter drei Personen. Für mehr als drei Teilnehmer haben das bislang beste Verfahren für neidfreie Teilungen 1995 der Politologe Steven Brams von der New York University und der Mathematiker Alan Taylor vom Union College im US-Bundesstaat New York entwickelt. Doch ihr Verfahren ist nicht terminiert – je nach den Präferenzen der Teilnehmer kann es eine Million, eine Milliarde oder noch viel mehr Schritte benötigen, bis eine faire Teilung erreicht ist.

Der Algorithmus von Brams und Taylor wurde seinerzeit zwar als Durchbruch gefeiert, doch »die Tatsache, dass er nicht terminiert ist, ist aus meiner Sicht ein großer Nachteil«, sagt Ariel Procaccia, Informatiker an der Carnegie Mellon University und einer der Schöpfer von »Spliddit«, einem kostenlosen Onlinewerkzeug für die faire Aufteilung beispielsweise von Haushaltsarbeiten oder Mietkosten unter Zimmergenossen oder Wohngemeinschaften.

Im Verlauf der vergangenen 50 Jahre kamen Mathematiker und Informatiker, darunter auch Procaccia, zu der Überzeugung, es gäbe keinen terminierten Algorithmus für eine neidfreie Teilung unter n Personen.

»Genau dieses Problem brachte mich dazu, mich mit dem Thema der fairen Teilung zu befassen«, sagt Walter Stromquist, Professor für Mathematik am Bryn Mawr College in Pennsylvania, der 1980 eine Reihe wichtiger Erkenntnisse zur Kuchenteilung bewies. »Ich hatte immer vor, zu diesem Thema zurückzukehren, wenn ich einmal Zeit hätte, und zu beweisen, dass eine solche Erweiterung des Ergebnisses unmöglich ist.«

»Definitiv das größte Ergebnis in Jahrzehnten!«
Ariel Procaccia

Doch im April 2016 widersprachen zwei Informatiker in einem online veröffentlichten Aufsatz dieser Erwartung: Sie beschrieben einen Algorithmus zur neidfreien Teilung, bei dem die Anzahl der nötigen Schritte nur noch von der Zahl der Teilnehmer und nicht länger von deren Präferenzen abhängt. Einer der beiden Forscher, der 27-jährige Simon Mackenzie, Postdoc an der Carnegie Mellon University, präsentierte das Verfahren im Oktober des Jahres auf dem »IEEE Symposium on Foundations of Computer Science«, einer der bedeutendsten Tagungen im Bereich Informatik.

Der Algorithmus ist außerordentlich komplex: Die Aufteilung eines Kuchens unter n Personen kann bis zu n hoch n hoch n hoch n hoch n hoch n Schritte erfordern und eine etwa ebenso große Anzahl von Schnitten. Selbst für eine Hand voll Teilnehmer ist die Zahl der Schritte schon größer als die Zahl aller Atome im Universum. Doch die Forscher haben bereits Ideen, um den Algorithmus einfacher und schneller zu machen, sagt der andere der beiden Forscher, Haris Azis, ein 35 Jahre alter Informatiker der University of New South Wales in Australien.

Für all die Wissenschaftler, die sich der Theorie der fairen Teilung gewidmet haben, sei das definitiv das größte Ergebnis in Jahrzehnten", so Procaccia.

Kuchenstücke

Der neue Algorithmus von Aziz und Mackenzie basiert auf einem eleganten Verfahren zur Teilung eines Kuchens unter drei Personen, das die Mathematiker John Selfridge und John Conway unabhängig voneinander um das Jahr 1960 herum entwickelten. Wenn Alice, Bob und Charlie einen Kuchen teilen wollen, beginnt der Algorithmus damit, dass Charlie den Kuchen in drei – aus seiner Sicht gleichwertige – Stücke schneidet. Alice und Bob wählen nun beide ihr bevorzugtes Stück aus. Handelt es sich um zwei verschiedene Stücke, ist die Teilung bereits beendet: Alice und Bob erhalten das von ihnen gewählte Stück, Charlie das übrig gebliebene, und alle sind glücklich und zufrieden.

Wählen Alice und Bob jedoch ein und dasselbe Stück, dann sind weitere Schritte nötig. Bob schneidet nun vom Lieblingsstück so viel ab, dass es – aus seiner Sicht – gleichwertig ist zu seinem Stück zweiter Wahl. Das kleine abgeschnittene Teil wird für eine spätere Verwendung beiseitegelegt. Jetzt wählt Alice aus den drei Stücken aus, anschließend Bob – wobei er allerdings, sofern nicht Alice genau dieses gewählt hat, sein ursprüngliches Lieblingsstück nehmen muss. Charlie erhält wieder das verbliebene Stück.

Auch jetzt gibt es keinen Grund für Neid unter den drei Teilnehmern: Alice ist glücklich, dass sie als Erste wählen konnte; Bob ist glücklich, da er eines seiner beiden – nach dem »Trimmen« gleichwertigen – favorisierten Stücke nehmen konnte; und Charlie ist glücklich, weil er in jedem Fall eines der von ihm als gleichwertig angesehenen Originalteile erhält.

Doch was ist mit dem kleinen abgeschnittenen Teil? Warum lässt es sich vermeiden, für dieses Stück die ganze Prozedur von vorn zu beginnen und so in eine endlose Reihe von Teilungen zu geraten? Der Grund ist Charlies völlige Zufriedenheit. Er würde nicht einmal dann neidisch sein, wenn einer der beiden anderen das verkleinerte Stück und das abgeschnittene Stückchen erhalten würde – denn zusammen ergäbe das gerade wieder eines der Originalstücke. Aziz und Mackenzie bezeichnen diese Situation als »Dominanz« von Charly über den Teilnehmer, der das »getrimmte« Stück erhalten hat.

Hat beispielsweise Alice dieses Stück erhalten, dann geht die Prozedur so weiter: Bob schneidet das Reststück in drei aus seiner Sicht wiederum gleichwertige Teile. Alice darf als Erstes wählen, dann Charly. Bob erhält das letzte Stück. Wieder ist jeder glücklich und zufrieden: Alice, weil sie zuerst wählen durfte; Charlie, weil ihm einerseits egal ist, was Alice bekommt, und weil er andererseits ein besseres Stück als Bob erhält; und Bob, weil aus seiner Sicht die drei Teile ohnehin gleichwertig waren.

Schon Brams und Taylor waren in ihrem Algorithmus 1995 auf das Phänomen der Dominanz gestoßen, ohne allerdings diesen Begriff zu verwenden. Doch es gelang ihnen nicht, aus dieser Erkenntnis heraus einen terminierten Algorithmus zu entwickeln. In den 20 Jahren danach gelang das auch sonst niemandem, »und ich glaube nicht, dass es daran lag, dass es keiner versucht hätte«, sagt Procaccia.

Kuchenteilungsanfänger

Als Aziz und Mackenzie sich vor ein paar Jahren dem Problem zuwandten, waren sie Neulinge auf diesem Gebiet. »Wir hatten nicht so viel Hintergrundwissen, wie all die Leute, die sich bereits intensiv damit auseinandergesetzt hatten«, so Aziz. »Meistens ist das ein Nachteil, doch hier war es eher von Vorteil, denn wir dachten nicht in den bekannten Bahnen.«

Ihre ersten Gehversuche machten die beiden Forscher mit einer kompletten Neuuntersuchung des Teilungsproblems für drei Personen. Ihre Analyse führte sie schließlich zu einem terminierten Algorithmus für eine neidfreie Teilung für vier Personen, die sie im vergangenen Jahr veröffentlichten.

»Nicht überraschend, dass so lange keiner darauf gekommen ist«
Ariel Procaccia

Aziz und Mackenzie sahen zunächst keinen offensichtlichen Weg, diesen Algorithmus auf mehr als vier Teilnehmer zu erweitern – aber sie arbeiteten fieberhaft daran. »Nachdem wir die Arbeit für vier Teilnehmer zur Veröffentlichung eingereicht hatten, waren wir natürlich scharf darauf, es selbst zu versuchen«, sagt Aziz, »bevor jemand mit mehr Erfahrung unseren Ansatz auf den allgemeinen Fall mit n Teilnehmern erweiterte.« Es dauerte ein Jahr, dann hatten sie Erfolg.

Ähnlich wie der Selfridge-Conway-Algorithmus fordert das komplizierte Protokoll von Aziz und Mackenzie individuelle Teilnehmer immer wieder dazu auf, Kuchenstücke in n gleiche Teile zu schneiden, anschließend dürfen andere Teilnehmer die Stückgröße durch das Abschneiden kleiner Teile »trimmen« und Teile auswählen. Aber zu dem Algorithmus gehören noch andere Schritte, wie etwa der periodische, sorgfältig kontrollierte Austausch von Teilen der angesammelten »Kuchenvorräte« zwischen Teilnehmern. Dabei geht es darum, die Anzahl dominanter Beziehungen zwischen den Teilnehmern zu erhöhen.

Diese dominanten Beziehungen erlauben es Aziz und Mackenzie, die Komplexität des Problems zu verringern: Wenn beispielsweise drei Teilnehmer alle anderen dominieren, können diese drei mit ihren Kuchenstücken fortgeschickt werden – sie sind bereits völlig unabhängig davon, wer die übrigen Reste bekommt, zufrieden. Es verbleibt eine kleinere Zahl von Teilnehmern, und nach einer endlichen Zahl solcher Schritte sind schließlich alle zufrieden und der gesamte Kuchen ist verteilt.

»Schaut man sich im Rückblick an, wie kompliziert der Algorithmus ist, so ist es nicht überraschend, dass so lange keiner darauf gekommen ist«, sagt Procaccia. Aziz und Mackenzie glauben aber, dass sich das Verfahren noch erheblich vereinfachen lässt – zu einem Algorithmus ohne den Austausch von Kuchenstücken, der weniger als n hoch n hoch n Schritte benötigt. Nach Auskunft von Aziz bereiten die beiden Forscher derzeit die Veröffentlichung ihrer neuen Ergebnisse vor.

Allerdings dürfte selbst ein solcher vereinfachter Algorithmus kaum praktische Anwendungen haben, warnt Brams. Denn die Portionen, welche die Teilnehmer letztlich erhalten, würden aus vielen kleinen Krümeln von unterschiedlichsten Stellen des Kuchens bestehen. Und das ist kein brauchbarer Ansatz etwa für die Teilung von Land.

Für Mathematiker und Informatiker, die sich mit dem Problem des Kuchenteilens befassen, handele es sich trotzdem geradezu um eine Art Neustart des Forschungsgebiets, sagt Stromquist.

Denn die Forscher wissen jetzt, dass es möglich ist, einen Kuchen in einer endlichen Anzahl von Schritten fair aufzuteilen. Das nächste Ziel sei es, so Procaccia, die gewaltige Kluft zwischen der Obergrenze der nötigen Schnitte im Algorithmus von Aziz und Mackenzie und der bereits zuvor existierenden Mindestzahl von Schnitten für eine Kuchenteilung zu überbrücken. Procaccia gelang bereits der Beweis, dass eine neidfreie Kuchenteilung mindestens 2 Schritte erfordert – aber diese Untergrenze ist verschwindend klein gegen n hoch n hoch n hoch n hoch n hoch n und selbst gegen n hoch n hoch n.

Die Forscher müssen also sehen, wie sie diese Kluft schließen könne, so Aziz: »Ich glaube, an beiden Enden sind noch Fortschritte möglich.«