Die Kuchenteilung verständlich erklärt

Zwei Kinder teilen einen Kuchen: Eines schneidet, das andere wählt. Das gilt als gerecht. Aber holen beide damit das Beste heraus? Diese Seite prüft es an zwei Sportteams, die sich eine Halle teilen, und fragt, was Fairness kostet.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Einer schneidet, der andere wählt

Zwei Kinder teilen sich einen Kuchen. Eines schneidet ihn in zwei Stücke, das andere wählt eines. Das schneidende Kind schneidet so, dass ihm beide Stücke gleich lieb sind. Sonst bliebe ihm das schlechtere.

Das gilt als gerecht, und es stimmt: Dem schneidenden Kind sind beide Stücke gleich lieb, und das wählende Kind hat das bessere genommen. Keines würde tauschen wollen. Doch das Verfahren fragt das wählende Kind nur nach links oder rechts. Wie anders dieses Kind den Kuchen mag, erfährt es nie.

Etwas beliebig Teilbares so zu teilen, heißt Kuchenteilung. Es kann auch ein Stück Land oder Hallenzeit sein.

Zwei Teams teilen sich eine Halle

Wir spielen das mit einer Sporthalle durch, in einem vereinfachten Rechenbild (Fachwort: Modell). Die Aussagen in diesem Teil beschreiben dieses Rechenbild, nicht die Wirklichkeit. Zwei Teams teilen sich einen Tag, zwölf Stunden ab 8 Uhr morgens.

Jedes Team sagt ehrlich, wie wichtig ihm jede Stunde ist: sein Wunsch. Der Wert eines Zeitstücks ist sein Anteil an allem, was dem Team an der Halle wichtig ist: Die ganze Halle ist ganz wert, ein Stück davon etwa die Hälfte.

Team 1 sind die Stunden ab 14 Uhr wichtiger als die davor. Team 2 sind die Stunden bis 14 Uhr am wichtigsten. Die zwei Stunden von 14 bis 16 Uhr sind ihm gleichgültig, und der Abend ist ihm weniger wichtig als der Morgen.

Team 1 schneidet bei 16 Uhr, denn dort sind ihm beide Seiten gleich viel wert: Die späten Stunden zählen für Team 1 mehr als die frühen. Team 2 wählt die Seite bis 16 Uhr, weil die Stunden bis 14 Uhr ihm am wichtigsten sind. Team 1 behält den Abend.

Auf den ersten Blick ist das gerecht. Team 1 hat genau die Hälfte von dem, was ihm die Halle wert ist, Team 2 den größten Teil. Drei Fragen kann man an jede Aufteilung stellen:

• Proportional: Bekommt jedes Team mindestens seinen fairen Anteil, bei zwei Teams die Hälfte, bei drei ein Drittel? Hier ja.
• Neidfrei: Zieht kein Team das Stück eines anderen dem eigenen vor? Hier ja: Team 1 sind beide Seiten gleich viel wert, Team 2 hat gewählt.
• Effizient (Fachwort: Pareto-effizient): Lässt sich kein Team besser stellen, ohne dass ein anderes verliert? Hier nein.

Warum nicht effizient? Team 1 will die zwei Stunden von 14 bis 16 Uhr sehr, Team 2 gar nicht. Gäbe Team 2 sie ab, hätte Team 1 statt der Hälfte Dreiviertel, und Team 2 verlöre nichts. Das Verfahren bemerkt das nie, denn es fragt Team 2 nur nach links oder rechts.

Drei und mehr Teams: das wandernde Messer

Bei drei oder mehr Teams ist unklar, wer wie schneidet und wer zuerst wählt. Ein Verfahren dafür ist das bewegliche Messer: Es wandert langsam über den Kuchen, hier von morgens bis abends. Jedes Team beobachtet, wie viel ihm das Stück links vom Messer wert ist, und ruft „Halt“, sobald das seinen fairen Anteil erreicht. Wer zuerst ruft, bekommt das Stück und scheidet aus. Das letzte Team erhält den Rest.

Dieses Verfahren ist proportional. Wer ruft, hat genau seinen Anteil. Das letzte Team hat nie gerufen, also war ihm jedes abgeschnittene Stück höchstens so viel wert wie sein Anteil. Der Rest ist ihm deshalb mindestens so viel wert.

Neidfrei ist es in der Regel nicht. Wer zuerst ruft, schaut danach auf die übrigen Stücke. Bei drei Teams sind sie ihm zusammen zwei Drittel wert, verteilt auf zwei Stücke. Wären sie ihm gleich viel wert, hätte jedes ein Drittel, so viel wie sein eigenes. Sonst ist eines mehr wert als sein eigenes. In den gerechneten Fällen mit drei bis fünf Teams war das Ergebnis nie neidfrei.

Was gerechnet wurde

Ein Programm hat diese Verfahren auf viele erdachte Teams angewandt. Die Wünsche waren zufällig, auf drei Arten: unabhängig voneinander, ähnlich oder gegensätzlich (jedes Team will einen eigenen Block). Als Maß dient die Gesamtzufriedenheit, die Summe der Anteile, die die Teams von ihrem Wunsch bekommen. Ihr Höchstwert entsteht, wenn jede Stunde an das Team geht, das sie am meisten will.

Die klassischen Verfahren waren fast nie effizient: Von 3.600 gerechneten Ergebnissen war nur in 26 Fällen kein Tausch ohne Verlierer mehr möglich. Im Mittel über die drei Arten von Wünschen blieben 16 % des Höchstwerts liegen, wenn zwei Teams schneiden und wählen, und 32 % beim Messer mit fünf Teams. Mit Tauschen ohne Verlierer ließ sich der größte Teil davon zurückholen.

Man könnte erwarten, dass Neidfreiheit viel Gesamtzufriedenheit kostet. Die beste neidfreie Aufteilung verlor aber im Mittel weniger als ein Prozent des Höchstwerts, im schlechtesten gefundenen Fall gut neun Prozent (fünf Teams, ähnliche Wünsche). Bei zwei Teams und unabhängigen Wünschen war die Aufteilung mit dem Höchstwert in 174 von 200 Fällen schon neidfrei. Ein mögliches Bild: Jedes Team bekommt die Stunden, die es mehr will als das andere, und das ist oft mehr als die Hälfte seines Werts. Mit mehr Teams wird das seltener.

Die Kosten liegen woanders: Effiziente Aufteilungen zerstückeln die Halle. Das Messer gibt jedem Team einen zusammenhängenden Block, die Aufteilungen mit dem Höchstwert gaben im Mittel zwei bis gut drei getrennte Blöcke. Bei zufälligen Wünschen liegen die Stunden, die ein Team am meisten will, nicht nebeneinander.

Häufige Missverständnisse

• „Gleich lang heißt gleich gerecht.“ Nein. Im Hallenbeispiel hat Team 1 vier Stunden und Team 2 acht, und keines beneidet das andere. Gerecht wird am Wert fürs Team gemessen.
• „Wenn niemand mehr gewinnen kann, ist es fair.“ Nein. Effizient heißt nur, dass sich ohne Verlierer nichts verbessern lässt. Die ganze Halle für ein Team kann effizient sein, wenn ihm jede Stunde etwas wert ist.

Woran Sie das im Alltag erkennen

Achten Sie auf Folgendes:

• Mehrere Menschen teilen etwas Teilbares, etwa ein Erbe, und wollen Verschiedenes davon.
• Alle stimmen der Aufteilung zu, tauschen danach aber freiwillig einzelne Stücke. Wer freiwillig tauscht, hofft zu gewinnen. Steht dabei keiner schlechter da und einer besser, blieb beim Teilen Wert liegen.
• Wer geteilt hat, kannte die Wünsche der anderen nicht. Dann konnte der Schnitt sie nicht berücksichtigen.

Wie ernst ist das Modell zu nehmen?

Alle Teams sagen ehrlich, was ihnen wichtig ist. Die Wünsche sind erzeugt, nicht erhoben, und echte Wünsche könnten Neidfreiheit teurer machen. Wer die Wünsche der anderen kennt, könnte tricksen; das zeigt das Rechenbild nicht.

Was Sie mitnehmen

• Fragen Sie vor dem Teilen: Kennt, wer schneidet, die Wünsche der anderen?
• Fragen Sie vor dem Teilen: Muss niemand neidisch sein, und was darf dafür liegen bleiben?
• Fragen Sie sich: Braucht jeder einen zusammenhängenden Block?

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, die Demo. Dort stellen Sie Teams, Wunscharten und Verfahren ein. Zum Verstehen brauchen Sie sie nicht. Der erste Knopf unten öffnet sie, der zweite führt zum zweiten Teil für Fachleute.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er beschreibt, wie zwölf Hallenstunden unter \(n\) Teams bewertet und verteilt werden, welche drei Teilungsprotokolle und welche Vergleichsverteilungen gerechnet werden und was die Messreihen zeigen.

• Kuchen und Bewertung: Der Kuchen ist das Intervall \([0, m]\) mit \(m = 12\) Stunden (8 bis 20 Uhr). Team \(i\) vergibt an Stunde \(j\) ein ganzzahliges Gewicht \(w_{ij}\) von 0 bis 9 und hat damit die Dichte \(v_{ij} = w_{ij} / \sum_j w_{ij}\) (die Summe sei positiv). Der Wert eines Stücks \(S\) ist \(V_i(S) = \int_S v_i\); der ganze Kuchen ist 1 wert, \(V_i([0; m]) = 1\). Innerhalb einer Stunde ist jede Minute gleich viel wert: Die Bewertung ist stückweise konstant und additiv. Der Nutzen von Team \(i\) ist \(V_i(S_i)\), angegeben in Prozent des ganzen Kuchens.
• Verteilung und Eigenschaften: Eine Verteilung \((S_1, \dots, S_n)\) zerlegt den Kuchen in disjunkte Stücke; ein Stück darf aus mehreren getrennten Blöcken bestehen. Sie ist proportional, wenn \(V_i(S_i) \ge 1/n\) für alle \(i\); neidfrei, wenn \(V_i(S_i) \ge V_i(S_k)\) für alle \(i, k\); Pareto-effizient, wenn es keine Verteilung gibt, in der alle Teams mindestens so gut und ein Team besser dasteht. Die Wohlfahrt ist die Summe der Nutzen, \(W = \sum_i V_i(S_i)\).
• Protokolle (Gleichstand: kleinere Teamnummer; die Zahl der Teams \(n\) liegt zwischen 2 und 6). Geteilt und gewählt (zwei Teams): Team 1 schneidet an der Stelle \(c\), an der ihm beide Seiten gleich viel wert sind; Team 2 wählt die höher bewertete Seite, bei Gleichstand die linke. Selfridge–Conway (drei Teams): Team 1 schneidet in drei gleich bewertete Stücke, Team 2 kürzt das von ihm am höchsten bewertete Stück auf den Wert des zweitbesten, Team 3 wählt unter den drei Stücken; hat es das gekürzte nicht gewählt, bekommt dieses Team 2, sonst wählt Team 2 unter den übrigen beiden. Das Team aus {Team 2, Team 3}, das das gekürzte Stück nicht hat, teilt die Kürzung in drei gleich bewertete Teile; es wählen der Halter des gekürzten Stücks, dann Team 1, zuletzt der Teiler. Sind die beiden besten Stücke gleich viel wert, entfällt Kürzen und Teilen. Bewegliches Messer (Dubins–Spanier, beliebig viele Teams): Das Messer wandert von links nach rechts; wer zuerst ruft, weil ihm das Stück links vom Messer \(1/n\) wert ist, bekommt es und scheidet aus; das letzte Team erhält den Rest.
• Vergleichsverteilungen (Rechnungen, keine Protokolle, denn sie setzen voraus, dass jemand alle Bewertungen kennt). Höchste Wohlfahrt: jede Stunde an das Team mit der höchsten Dichte, \(W^* = \sum_j \max_i v_{ij}\); sie ist nicht immer neidfrei. Neidfrei, beste Wohlfahrt: die größte Wohlfahrt unter der Bedingung „kein Neid“, \(W_{\mathrm{ef}}\). Nachgebessert: die größte Wohlfahrt, bei der kein Team unter seinen Nutzen \(u_i\) im Protokoll fällt (und neidfrei, wenn das Protokoll es war). Der Preis der Neidfreiheit ist \(1 - W_{\mathrm{ef}} / W^*\).
• Erzeuger der Bewertungen: unabhängig (jedes Gewicht unabhängig zufällig von 0 bis 9), ähnlich (eine für alle Teams gleiche, zufällig gezogene Grundform, nämlich exponentialverteilt und mit 5 multipliziert, dazu je Team und Stunde ein gleichverteiltes Rauschen von −2 bis 2, gerundet und auf 0 bis 9 begrenzt), gegensätzlich (die zwölf Stunden werden in \(n\) aufeinanderfolgende Blöcke von je etwa \(12/n\) Stunden geteilt; Team \(i\) gibt Block \(i\) das Gewicht 8, allen anderen Stunden ein zufälliges Gewicht von 0 bis 2). Hat eine Zeile nur Nullen, wird eine zufällige Stunde auf 1 gesetzt. Jede Zeile der Messreihen besteht aus 200 Zufallsinstanzen mit festen Zufallsstartwerten, zwölf Stunden und Gewichten 0 bis 9.
• Rechnung: Gesucht ist jeweils der kleinste Punkt, bis zu dem ein Stück den verlangten Wert erreicht. Stunden mit Dichte null enthält das Stück ohne Wertzuwachs, der Punkt liegt daher in einer Stunde mit Dichte größer null und löst dort eine lineare Gleichung. Die Protokolle rechnen exakt in Brüchen. Die Vergleichsverteilungen sind lineare Programme (HiGHS) mit Toleranz \(10^{-7}\); Wohlfahrtsverhältnisse werden auf eine Stelle angezeigt.

Die Formeln

Weil innerhalb einer Stunde jede Minute gleich viel wert ist, genügen für die Vergleichsverteilungen die Anteile \(x_{ij} \in [0; 1]\) der Stunde \(j\), die Team \(i\) bekommt, mit \(\sum_i x_{ij} = 1\). Das lineare Programm lautet:

\[\max \sum_{i,j} v_{ij}\, x_{ij} \quad \text{unter} \quad \sum_j v_{ij} x_{ij} \ge \sum_j v_{ij} x_{kj} \;\; (\text{neidfrei}), \qquad \sum_j v_{ij} x_{ij} \ge u_i \;\; (\text{nicht schlechter})\]

Die erste Nebenbedingung verlangt Neidfreiheit für alle Paare \(i, k\), die zweite, dass kein Team unter seinen Nutzen \(u_i\) im Protokoll fällt. Die Vergleichsverteilungen benutzen sie getrennt: \(W_{\mathrm{ef}}\) nur die erste, die Nachbesserung eines nicht neidfreien Protokolls nur die zweite, die eines neidfreien Protokolls beide. Die höchste Wohlfahrt braucht keine Nebenbedingung: \(W^* = \sum_j \max_i v_{ij}\). Die beiden Schnittregeln lauten: Geteilt und gewählt wählt \(c\) mit \(V_1([0; c]) = 1/2\), und beim Messer ruft Team \(i\) beim kleinsten \(c\) mit \(V_i([a, c]) = 1/n\), wobei \(a\) das rechte Ende des zuletzt vergebenen Stücks ist (zu Beginn \(a = 0\)).

Herleitung Schritt für Schritt

Die folgenden Schritte sind Rechnung dieser Seite, keine Messung der Demo.

• Schritt 1, Wohlfahrt nach oben begrenzt: Für jede Verteilung ist \(W = \sum_j \sum_i v_{ij} x_{ij} \le \sum_j \max_i v_{ij} = W^*\), denn für jede Stunde gilt \(\sum_i x_{ij} = 1\). Gleichheit gilt genau dann, wenn jede Stunde nur an Teams mit der höchsten Dichte geht. Das Verhältnis \(W / W^*\) liegt also zwischen 0 und 1, der Preis der Neidfreiheit nicht unter 0.
• Schritt 2, neidfrei heißt proportional: Bei einer Zerlegung des ganzen Kuchens ist \(\sum_k V_i(S_k) = 1\). Gilt \(V_i(S_i) \ge V_i(S_k)\) für alle \(k\), dann ist \(n \cdot V_i(S_i) \ge 1\).
• Schritt 3, Geteilt und gewählt: Team 1 bewertet beide Seiten mit \(1/2\), ist also mit jeder zufrieden und beneidet niemanden. Team 2 nimmt die Seite, die es mindestens mit \(1/2\) bewertet; die andere ist ihm höchstens \(1/2\) wert. Beide sind neidfrei und damit proportional.
• Schritt 4, das Messer ist proportional: Wer ruft, bekommt genau den Wert \(1/n\). Ein Team, das bis zum Ende nicht gerufen hat, bewertete jedes abgeschnittene Stück mit höchstens \(1/n\), sonst hätte es früher gerufen. Bei \(n - 1\) abgeschnittenen Stücken bleibt ihm ein Rest von mindestens \(1 - (n-1)/n = 1/n\).
• Schritt 5, wann das Messer ab drei Teams Neid erzeugt: Der erste Rufer bewertet sein Stück mit \(1/n\), die übrigen \(n - 1\) Stücke zusammen mit \(1 - 1/n\), also im Mittel mit \(1/n\). Sind sie ihm nicht alle genau \(1/n\) wert, ist eines mehr wert als sein eigenes: Er beneidet. Bei zwei Teams gibt es nur ein anderes Stück, und es ist genau \(1/2\) wert. Die Bedingung ist hinreichend für Neid, nicht notwendig: Auch ein späterer Rufer kann beneiden (zweites Beispiel unten).
• Schritt 6, wann ein Tausch ohne Verlierer existiert: Hält Team \(i\) einen Teil der Stunde \(a\) und Team \(k\) einen Teil der Stunde \(b\) (alle Dichten positiv), und gilt \(v_{ia} / v_{ka} < v_{ib} / v_{kb}\), dann gibt \(i\) einen kleinen Anteil \(\delta\) von \(a\) an \(k\) und erhält von \(k\) den Anteil \(\eta = (v_{ia} / v_{ib})\,\delta\) von \(b\). Team \(i\) bleibt unverändert, Team \(k\) gewinnt \(\delta\,(v_{ka} v_{ib} - v_{kb} v_{ia}) / v_{ib} > 0\). Eine solche Verteilung ist nicht Pareto-effizient. Geteilt und gewählt schneidet nur nach den Dichten von Team 1; die Dichten von Team 2 gehen nur über die Wahl links oder rechts ein. Das Protokoll kann solche Stundenpaare daher nicht ausschließen.

Durchgerechnet: zwei Beispiele

Zwei Teams, Geteilt und gewählt. Gewichte der zwölf Stunden von 8 bis 20 Uhr: Team 1 gibt sechs Stunden das Gewicht 1 und danach sechs das Gewicht 3; Team 2 gibt bis 14 Uhr das Gewicht 3, den zwei Stunden bis 16 Uhr das Gewicht 0 und den vier Abendstunden das Gewicht 1. Das Beispiel stammt aus der Demo und ist dort von Hand nachgerechnet.

Schritt	Rechnung	Ergebnis
Schnitt von Team 1	\(V_1([8; 14]) = \frac{6\cdot1}{6\cdot1+6\cdot3} = \frac{1}{4}\); danach wächst der Wert um \(\frac{1}{8}\) je Stunde	\(V_1([8; c]) = \frac{1}{2}\) bei \(c\) = 16 Uhr
Wahl von Team 2	\(V_2([8; 16]) = \frac{6\cdot3+2\cdot0}{6\cdot3+2\cdot0+4\cdot1} = \frac{9}{11}\), die rechte Seite \(\frac{2}{11}\)	Team 2 wählt links
Nutzen	Team 1: \(V_1([16; 20]) = \frac{1}{2}\); Team 2: \(\frac{9}{11}\)	neidfrei und proportional
Übertrag der Stunden 14 bis 16 Uhr an Team 1	\(V_1([14; 16]) = \frac{2\cdot3}{6\cdot1+6\cdot3} = \frac{1}{4}\); \(V_2([14; 16]) = 0\)	Team 1: \(\frac{1}{2} + \frac{1}{4} = \frac{3}{4}\), Team 2 unverändert \(\frac{9}{11}\)

Drei Teams, Messer. Team 1 bewertet wie oben, Team 2 und Team 3 geben allen zwölf Stunden das Gewicht 1.

Messer bei	Rechnung	Ergebnis
12 Uhr	Team 2 und Team 3: \(\frac{4}{12} = \frac{1}{3}\); Team 1: \(\frac{4\cdot1}{6\cdot1+6\cdot3} = \frac{1}{6}\)	Team 2 und 3 rufen gleichzeitig, es gewinnt die kleinere Nummer: Team 2 erhält 8 bis 12 Uhr
16 Uhr	Team 1: \(\frac{2\cdot1+2\cdot3}{6\cdot1+6\cdot3} = \frac{1}{3}\); Team 3: \(\frac{4}{12} = \frac{1}{3}\)	Team 1 ruft (kleinere Nummer) und erhält 12 bis 16 Uhr; Team 3 erhält den Rest, 16 bis 20 Uhr
Neid	Team 1 bewertet 16 bis 20 Uhr mit \(\frac{4\cdot3}{6\cdot1+6\cdot3} = \frac{1}{2}\), das eigene Stück mit \(\frac{1}{3}\)	Team 1 beneidet Team 3

Der erste Rufer, Team 2, bewertet alle drei Stücke mit \(\frac{1}{3}\) und beneidet niemanden; der Neid entsteht beim zweiten Rufer, Team 1.

Befunde

Alle Zahlen stammen aus Messreihen mit je 200 Zufallsinstanzen je Zeile (zwölf Stunden, Gewichte 0 bis 9, feste Zufallsstartwerte). Die Protokolle sind exakt gerechnet, die Wohlfahrtsverhältnisse numerisch. Der Kern ist gegen unabhängige Rechenwege geprüft: Die linearen Programme stimmen mit einer Aufzählung aller Ecken des zulässigen Bereichs in Brüchen überein (kleine Instanzen), die Schnittstellen mit einer Intervallhalbierung nach dem Zielwert, und eine Rasterprobe (15 Zufallsinstanzen, zwei Teams, drei Stunden, Anteile in Zwanzigsteln) findet bei der neidfreien Optimierung nichts Besseres als das lineare Programm.

Eigenschaften der Protokolle. Alle Protokolle sind in allen Instanzen proportional. Geteilt und gewählt und Selfridge–Conway sind in allen 200 Instanzen jeder Zeile neidfrei, das Messer mit zwei Teams ebenfalls. Ab drei Teams war das Messer in keiner Instanz neidfrei; andere Zufallsstartwerte können einzelne neidfreie Fälle liefern. Pareto-effizient waren nur 26 von 3.600 Protokollergebnissen (0,7 %); die Tabelle zeigt, wo (Zahl der Instanzen von je 200 je Erzeuger):

Protokoll	Teams	unabhängig	ähnlich	gegensätzlich
Geteilt und gewählt	2	0	3	14
Bewegliches Messer	2	0	1	7
Selfridge–Conway	3	0	1	0
Bewegliches Messer	3 bis 5	0	0	0

Protokoll	Teams	neidfrei	proportional
Geteilt und gewählt	2	alle 200 je Zeile	alle 200 je Zeile
Selfridge–Conway	3	alle 200 je Zeile	alle 200 je Zeile
Bewegliches Messer	2	alle 200 je Zeile	alle 200 je Zeile
Bewegliches Messer	3 bis 5	0 von 1.800	alle 1.800

Wie viel Wohlfahrt bleibt liegen? Summe der Nutzen im Verhältnis zur höchsten Wohlfahrt \(W^*\), unabhängige Vorlieben:

Protokoll	Teams	\(W / W^*\)
Geteilt und gewählt	2	80,9 %
Selfridge–Conway	3	78,3 %
Bewegliches Messer	3	75,9 %
Bewegliches Messer	4	73,8 %
Bewegliches Messer	5	73,2 %

Bei gegensätzlichen Vorlieben fällt das Messer von 80,6 % (zwei Teams) auf 44,6 % (fünf Teams). Gemittelt über die drei Erzeuger sind es 84,3 % bei Geteilt und gewählt, 77,7 % bei Selfridge–Conway und 68,2 % beim Messer mit fünf Teams; es bleiben also 16 %, 22 % und 32 % liegen. Nachgebessert (kein Team schlechter, bei einem neidfreien Protokoll weiter neidfrei) steigen die Verhältnisse auf 99,7 % (Geteilt und gewählt, unabhängig) und 96,8 % (Messer, fünf Teams); über alle Zeilen ohne den Erzeuger „gegensätzlich“ liegen sie bei 97 bis 100 %, bei gegensätzlichen Vorlieben bei 90,9 bis 95,8 %. Der Abstand zwischen Protokollergebnis und Nachbesserung beträgt über alle 18 Zeilen (Protokoll, Teamzahl, Erzeuger) 8 bis 51 Prozentpunkte.

Was kostet Neidfreiheit? Über 2.400 Instanzen (drei Erzeuger, vier Teamzahlen, je 200) liegt die beste neidfreie Wohlfahrt im Mittel bei 99,3 % von \(W^*\), der Preis also bei 0,7 %; ohne den Erzeuger „gegensätzlich“, bei dem der Preis konstruktionsbedingt null ist, sind es 1,0 %. Der schlechteste Fall ist 90,8 % (Preis 9,2 %) bei fünf Teams mit ähnlichen Vorlieben. Beim Erzeuger „gegensätzlich“ ist die höchste Wohlfahrt in allen Instanzen schon neidfrei. Bei unabhängigen und ähnlichen Vorlieben wächst der Preis mit der Zahl der Teams. Die Tabelle zeigt die beste neidfreie Wohlfahrt im Verhältnis zu \(W^*\) (Mittel) bei unabhängigen Vorlieben und dazu die Zahl der Instanzen (von je 200), in denen \(W^*\) schon neidfrei ist, bei unabhängigen und bei ähnlichen Vorlieben. Bei zwei Teams ist \(W^*\) also nicht immer neidfrei; das Mittel liegt dort nur knapp unter 100 % und erscheint bei einer Stelle als 100,0 %.

Größe	2 Teams	3 Teams	4 Teams	5 Teams
\(W_{\mathrm{ef}} / W^*\), unabhängig	100,0 %	99,7 %	99,3 %	98,5 %
\(W^*\) schon neidfrei, unabhängig	174	97	23	6
\(W^*\) schon neidfrei, ähnlich	52	17	2	0

Zersplitterung. Mittlere Zahl getrennter Blöcke je Team bei unabhängigen Vorlieben: Das Messer gibt immer einen zusammenhängenden Block, die Verteilung mit höchster Wohlfahrt und die beste neidfreie Verteilung zerlegen die Zeit. Bei den linearen Programmen hängt die Zahl von der gewählten Lösung und der Anordnung innerhalb einer Stunde ab; bei mehreren gleich guten Verteilungen ist die Wohlfahrt gleich, die gezeigte Zeitaufteilung nicht.

Verteilung	2 Teams	3 Teams	4 Teams	5 Teams
Bewegliches Messer	1,0	1,0	1,0	1,0
Höchste Wohlfahrt	3,35	2,89	2,41	2,00
Neidfrei, beste Wohlfahrt	3,39	3,16	2,84	2,56

Grenzen: was die Messung zeigt und was nicht

• Ehrliche Bewertungen: Jedes Team nennt seine wahre Bewertung. Wer die der anderen kennt, kann beim Schneiden, Kürzen oder Rufen taktieren; die Messreihen untersuchen das nicht.
• Stückweise konstant und additiv: Wer zusammenhängende Blöcke braucht (ein Spiel dauert 90 Minuten), hat keine additive Bewertung; die Reihen zählen nur die Blöcke. Reale Zeitfenster haben Mindestlängen und Wechselzeiten, die hier fehlen.
• Erzeugte Vorlieben: Die Befunde gelten für die drei Erzeuger; echte Vorlieben können mehr Neidkosten haben. Der schlechteste Fall der Reihe ist der schlechteste von 200 Instanzen je Zeile, keine Schranke; über Mittel und schlechtesten Fall hinaus wird keine Streuung berichtet, und ein Vergleich mit den Worst-Case-Schranken der Literatur zum Preis der Fairness fehlt. Die Zählungen gelten für die festen Instanzen der Reihen.
• Teamzahl: Einstellbar sind 2 bis 6 Teams, die Messreihen decken nur 2 bis 5 ab; für sechs Teams gibt es keine Messzahl.
• Wohlfahrt als Summe: Jede Bewertung ist auf 1 normiert, und die Wohlfahrt addiert diese Nutzen verschiedener Teams. Das setzt vergleichbare Skalen voraus und ist eine Festlegung, keine Messung (Anmerkung dieser Seite).
• Selfridge–Conway nur für drei Teams: Neidfreie Protokolle für beliebig viele Teams gibt es (Aziz und Mackenzie, aus dem Gedächtnis); sie brauchen eine riesige Zahl von Schritten und sind nicht umgesetzt. Für vier bis sechs Teams liegen nur das Messer (proportional) und die Vergleichsverteilungen vor.
• Vergleichsverteilungen sind Rechnungen: Sie setzen voraus, dass jemand alle Bewertungen kennt. Die Ergebnisse der linearen Programme sind numerisch; die Blockzahlen der Reihe zur Zersplitterung gelten nur für diese Verteilungen und unabhängige Vorlieben mit zwei bis fünf Teams.
• Gleichstände: Es gilt die kleinere Teamnummer; bei Geteilt und gewählt nimmt Team 2 bei gleicher Bewertung beider Seiten die linke. Im zweiten Beispiel hängt der Ausgang daran.

Erweiterungen und Verweise

Nicht gebaut, jeweils ein eigenes Problem: Stücke erzwingen, die aus genau einem Block bestehen (das erlaubt Neidfreiheit nicht immer), taktisches Verhalten, Schätzfehler der Bewertungen, verschieden große Ansprüche der Teams und mehrere Tage oder Räume. Verwandte Aufteilungsprobleme behandeln diese Demos der Linie:

• Preise statt Stücke: Die Erklärseite zur Mietaufteilung zeigt, wie sich eine feste Gesamtmiete so auf Zimmer verteilt, dass niemand ein fremdes Zimmer zu dessen Preis lieber hätte.
• Ganze Güter: Die unteilbare-gueter-demo verteilt Güter, die sich nicht zerlegen lassen, und prüft Neidfreiheit und Pareto-Optimalität.

Quellen

• Steinhaus, H. (1948): The problem of fair division. Econometrica 16.
• Dubins, L. E., & Spanier, E. H. (1961): How to cut a cake fairly. American Mathematical Monthly 68.
• Selfridge, J. L., & Conway, J. H. (um 1960): das neidfreie Verfahren für drei Personen (nach üblicher Zuschreibung).
• Aziz, H., & Mackenzie, S. (2016): A discrete and bounded envy-free cake cutting protocol for any number of agents. FOCS 2016.
• Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., & Kyropoulou, M. (2012): The efficiency of fair division. Theory of Computing Systems 50.
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/kuchenteilung-demo.

Keine der genannten Arbeiten wurde für die Demo oder diese Seite im Volltext gelesen. Die Beschreibung der Demo nennt nur Autoren, Jahr und bei Aziz und Mackenzie die Tagung; die übrigen Angaben stehen hier aus dem Gedächtnis, nicht nachgeschlagen.