Der aalglatte Arthur kippte den Sack auf dem Küchentisch aus. Der biegsamen Berta, der cleveren Clara und dem durchtriebenen Detlef fielen fast die Augen aus dem Kopf, als bündelweise Banknoten herauspurzelten und die Juwelen nur so rasselten.

Nun kam der schwierigste Teil: das Teilen der Beute. Keiner traute dem anderen, und vor allem gönnte keiner einem anderen einen größeren Anteil als sich selbst. Das Bargeld auf vier Häufchen zu legen war nicht schwer, solange jeder gut aufpaßte. Aber der Schmuck! Jeder hatte seine eigenen Ansichten darüber, was jedes Teil wert sei. Zum Glück waren viele Perlen- und Goldketten darunter, die sich zur Not zerlegen ließen.

"Wir sollten uns beeilen", sagte Clara nervös. "Wahrscheinlich ist die Polizei uns schon auf den Fersen, und wir müssen das Zeug aus dem Weg schaffen."

"Ich nehme den Diamanten-Stirnreif", rief Berta und klemmte ihn sich auf den Kopf. "Dann kann Clara dieses Halsband kriegen, und -"

"Die Halsbänder sind Schrott!" kreischte Clara. "Ich will die Smaragdbrosche und die -"

"Ruhe!" schrie Detlef. "Ihr Gauner werdet euch niemals einig werden, wenn ihr so herumstreitet. Wir müssen zusehen, daß jeder zufrieden ist."

Ratloses Schweigen. Schließlich fragte Berta: "Und wie geht das?"

"Na ja", sagte Detlef, der einst über ein krummes Ding in seiner akademischen Karriere gestolpert war, "wir brauchen ein proportionales neidfreies Zuweisungsprotokoll, wie die Mathematiker sagen."

"Finde ich auch", stimmte Arthur zu. "Äh, aber was bedeutet eigentlich das geschwollene Gelaber?"

"Neid", unterbrach Clara, "ist, wenn du nicht willst, daß jemand anders was kriegt, was du -"

"Weiß ich auch", fiel Arthur ihr ins Wort. "Ich meine die langen Wörter."

"Ein Zuweisungsprotokoll", erklärte Detlef, "ist ein systematisches Verfahren, Dinge unter mehrere Personen zu verteilen. Proportional heißt, daß am Ende jeder überzeugt ist, wenigstens seinen fairen Anteil erhalten zu haben. Und neidfrei heißt, niemand glaubt, daß ein anderer mehr bekommen hat als er selbst."

"Ist das nicht dasselbe?" fragte Berta. "Wenn jeder zufrieden ist, kann doch keiner mehr abgekriegt haben als ein anderer."

"Doch", meinte Clara. "Man muß sich ja über den Wert der Sachen nicht unbedingt einig sein. Habe ich recht, Detlef?"

Der nickte. "Neidfreie Protokolle sind immer proportional, aber proportionale müssen nicht unbedingt neidfrei sein."

"Warum nicht?" fragte Arthur.

"Nehmen wir an", erklärte Detlef, "ihr drei wollt drei Gegenstände unter euch aufteilen – sagen wir ein Armband, ein Halsband und ein Paar Ohrringe. Für Arthur ist das Halsband so viel wert wie der ganze Rest, aber Berta und Clara sehen das ganz anders. Im einzelnen schreibt ihr den Gegenständen folgende Prozentanteile am Gesamtwert zu:

Armband Halsband Ohrringe

Arthur 40 50 10

Berta 30 50 20

Clara 30 20 50

Wenn nun Arthur das Armband, Berta das Halsband und Clara die Ohrringe bekäme, wäre die Aufteilung proportional, denn jeder glaubt, sein Anteil sei mehr wert als ein Drittel der Beute. Aber Arthur ist immer noch neidisch auf Berta, denn die hat das Halsband bekommen, das in seinen Augen mehr wert ist als das Armband."

"Ach Berta", sagte Arthur mit tückischem Grinsen, "du willst doch deinen alten Freund Arthur nicht verärgern..."

Berta streckte ihm die Zunge heraus.

Wie wir sehen werden, sind neidfreie Protokolle viel schwieriger zu finden als proportionale; und ein Protokoll hilft für sich genommen noch nicht viel. Hinzukommen muß für jeden Beteiligten eine Strategie, mit der er sicherstellt, daß er sein Ziel erreicht – nach seiner eigenen Bewertung. Erst diese Strategien, die offiziell nicht zum Protokoll gehören und oft gar nicht explizit formuliert werden, garantieren, daß das Protokoll fair ist.

Ich werde die handelnden Personen die Spieler nennen, denn man denkt sich den ganzen Vorgang am besten als eine Folge von Spielzügen. Außerdem ist es üblich, die zu verteilenden Güter als einen Kuchen darzustellen.

Bei zwei Spielern gibt es ein einfaches, vielerprobtes, neidfreies Zuordnungsprotokoll: Ich schneide, du wählst. Die zugehörigen Strategien bestehen darin, daß Arthur nach seinen Wertvorstellungen genau hälftig teilt, also nicht verlieren kann, einerlei wie Berta sich entscheidet, und Berta dann das Stück nimmt, das sie für größer hält.

"Alter Hut", murmelte Arthur, als Detlef das in aller Ruhe zum Besten gegeben hatte. "Aber wir sind nicht zu zweit", warf Clara ein.

Detlef erzählte ungerührt weiter: "Es war 1944 in Lwow, als die Rote Armee in Polen gegen die Deutschen vorrückte. Da suchte sich der Mathematiker Hugo Steinhaus von den Schrecken des Krieges mit einem Rätsel abzulenken."

"Bist du wahnsinnig?" unterbrach ihn Arthur, "die Bullen können jeden Moment hier auftauchen, und du erzählst uns alte Geschichten aus dem Krieg!"


Das proportionale Steinhaus-Protokoll

"Für eine gute Theorie muß Zeit sein, auch wenn's draußen schon knallt." Detlef nahm seinen Faden wieder auf: "So hat Steinhaus das auch gesehen. Er wußte, warum das klassische Verfahren mit zwei Spielern funktioniert, und fragte sich, was mit dreien wäre." "Das ist einfach", sagte Arthur. "Ich schneide den Kuchen in drei Stücke, die ich für gleich halte, und erst kann Berta ein Stück wählen, dann Clara; das letzte nehme ich." "Nein", protestierte Berta, "das funktioniert nicht. Clara und ich meinen vielleicht beide, daß ein Stück etwas größer ist als ein Drittel. Wenn ich es nehme, keift Clara wieder los." "Steinhaus war ja nicht blöd", bemerkte Detlef mit einem kurzen Seitenblick auf Arthur. "Er fand eine komplizierte Folge von neun Schritten, aber ich kann sie euch erklären" (Bild 1). Der Einfachheit halber ist im folgenden von der Größe eines Stücks die Rede, obgleich damit stets der relative Wert – gemessen an dem des ganzen Kuchens – gemeint ist, wie der Spieler ihn einschätzt. Alle Urteile sind die subjektiven Einschätzungen des Spielers, der gerade am Zuge ist. Dieser nennt ein Stück fair, wenn er es für so groß hält wie ein Drittel des Kuchens – oder größer; andernfalls unfair. Was in Klammern steht, gehört nicht zum Protokoll, sondern zur Strategie des jeweiligen Spielers. 1. Arthur schneidet den Kuchen in drei Teile (die er für fair hält, also als gleich groß einschätzt). 2. Berta kann entweder aussetzen (wenn sie wenigstens zwei Teile für fair hält) oder zwei Stücke als schlecht kennzeichnen (die sie für unfair hält). 3. Wenn Berta ausgesetzt hat, nimmt Clara ein Stück (das sie für fair hält). Dann nimmt Berta ein Stück (das sie für fair hält). Schließlich nimmt Arthur das letzte Stück. 4. Wenn Berta zwei Stücke als schlecht gekennzeichnet hat, dann hat Clara die gleichen Entscheidungsmöglichkeiten wie sie: aussetzen oder zwei Stücke als schlecht kennzeichnen (nach derselben Strategie). Bertas Beurteilung berücksichtigt sie dabei überhaupt nicht. 5. Wenn Clara ausgesetzt hat, nehmen die Spieler Stücke in der Reihenfolge Berta, Clara, Arthur (nach der Strategie wie in Schritt 3). 6. Wenn nicht, haben Berta und Clara je zwei Stücke als schlecht bezeichnet. Also gibt es mindestens eines, das beide für schlecht halten. Das bekommt Arthur (der, weil er geteilt hat, alle Stücke für fair hält und sich nicht beklagen kann.) 7. Die beiden anderen Stücke werden vereinigt. (Clara und Berta glauben beide, daß diese Stücke zusammen wenigstens zwei Drittel des Kuchens ausmachen.) Nun spielen Clara und Berta "ich schneide, du wählst", um den Rest unter sich aufzuteilen (und dabei bekommt jede, was sie für einen fairen Anteil hält). "Bor äy", staunte Arthur. "Wart's ab", sagte Detlef. "Das war erst der Anfang. Das Verfahren von Steinhaus ist zwar proportional, aber nicht neidfrei. Es gibt Fälle, in denen jeder Spieler glaubt, er habe einen fairen Anteil erhalten, aber Clara – zum Beispiel – glaubt, Berta wäre besser weggekommen als sie selber. Nehmen wir an, Berta bewertet die drei Stücke mit 1/6, 1/2 und 1/3. Also setzt sie aus, denn es sind ihrer Ansicht nach zwei faire Stücke dabei. Clara hat dieselbe Einschätzung wie Berta, greift sich also das 1/2-Stück. Dann nimmt Berta das 1/3-Stück und Arthur das 1/6-Stück, das er selber aber für ein 1/3-Stück hält. Weil jeder meint, sein Stück habe wenigstens die Größe 1/3, ist die Zuordnung proportional. Trotzdem wird Berta neidisch auf Clara sein." "Ich bin mal gespannt, was ich bin, wenn du deinen Teil von der Sore hier hast", zischte Clara. "Hat Steinhaus ein – wie hieß das noch mal – neidfreies Protokoll für vier Leute gefunden?" "Nein", antwortete Detlef. "Er hat sich mit der Neidfreiheit überhaupt nicht beschäftigt. Das kam erst später." Arthur kaute Fingernägel und spähte nervös aus dem Fenster. Noch keine Polizei in Sicht. "Statt dessen", fuhr Detlef fort, "suchte er ein Protokoll für eine proportionale Teilung unter vier oder mehr Personen. Und seine Freunde Stefan Banach und Bronisðaw Knaster waren dabei bald erfolgreich." Das Banach-Knaster-Protokoll für n Spieler S₁, S₂, ..., S_n besteht aus folgenden Schritten: 1. S₁ schneidet ein (faires) Stück C vom Kuchen ab. Fair bedeutet jetzt mindestens 1/n vom ganzen Kuchen. 2. S₂ kann aussetzen (wenn er C für unfair oder gerade noch fair hält) oder von C etwas abschneiden (wenn er es für zu groß hält; er macht also aus C ein nach seiner Auffassung gerade noch faires Stück, das wir weiter mit C bezeichnen). Das abgeschnittene Stück wird wieder zum restlichen Kuchen gelegt. 3. S₃ hat dieselben Entscheidungs- und Wahlmöglichkeiten wie S₂, aber mit dem neuen Stück C. Dann kommt S₄ an die Reihe – und so weiter, bis jeder Spieler außer S₁ Gelegenheit zur Korrektur hatte. 4. Wenn kein Spieler von C etwas abgeschnitten hat, geht das Stück an S₁. Ansonsten geht es an den letzten Spieler, der etwas abgeschnitten hat (und das Stück nun für fair hält). Der so Bedachte scheidet mitsamt seinem Anteil aus dem Spiel aus. 5. Der Rest des Kuchens wird mit den abgeschnittenen Teilen vereinigt. Die restlichen n-1 Spieler (die sämtlich der Meinung sind, daß noch wenigstens (n-1)/n vom Kuchen übrig ist) wiederholen das Verfahren. 6. Es wird fortgesetzt, bis nur noch zwei Spieler übrig sind. Die einigen sich dann nach dem Verfahren "ich schneide, du wählst". "Auch das Banach-Knaster-Protokoll ist proportional, aber nicht neidfrei", erläuterte Detlef. "Mag sein", sagte Berta, "jedenfalls ist es anders als das Steinhaus-Protokoll – und für drei Spieler sogar einfacher." "Stimmt", sagte Detlef. "Das liegt an der neuen Idee von Banach und Knaster, etwas abzuschneiden. Steinhaus hatte schon ein anderes wichtiges Prinzip eingeführt: Teile einem Spieler ein Stück zu und kümmere dich dann um den Rest." Berta lehnte sich auf ihrem Stuhl zurück. "Aber wir sind uns nicht unbedingt einig, wieviel jedes Teil wert ist." "Das ist es ja gerade. Wie Steinhaus schon bemerkt hat, wird das Problem im allgemeinen sogar einfacher, wenn die Leute sich nicht einig sind." "Wieso das?" "Wenn ich lieber die Streusel mag und du lieber die Kirschen, dann können wir uns doch ziemlich leicht einigen, oder?" Arthur grummelte dazwischen: "Wenn ihr mit euren ausgefuchsten Protokollen so weiter macht, können wir nachher eins auf der Wache unterschreiben. Geht es nicht anders?" "Theoretisch mit Sicherheit. Nach einem Existenzbeweis, der seinerseits auf dem Konvexitätssatz des russischen Mathematikers Alexander Michailowitsch Ljapunow beruht -" "Bleib mir mit deinen Theorien vom Leib, Professor. Wir müssen zu den Mäusen und Klunkern hier kommen." Arthurs Zorn zu erregen war nicht ungefährlich. Detlef beeilte sich fortzufahren: "Dann gibt es noch die Verfahren mit bewegtem Messer. Lester Dubins und Edwin Spanier haben 1961 so etwas vorgeschlagen. Stellt euch einen langen Kastenkuchen vor. Einer fährt mit dem Messer langsam vom linken Ende nach rechts darüber hinweg. Ein Spieler ruft ,Halt!', sobald er bereit ist, das Stück links vom Messer zu akzeptieren. Dann wird es abgeschnitten, und dieser Spieler trollt sich damit. Alle anderen haben keinen Anlaß zum Neid, denn sie hätten ja vorher schreien können." "Sehr schön. Wie holländische Blumenauktion. Ist aber ungeschickt für Ringe und Broschen." "Ist auch eigentlich kein Algorithmus, weil es eine potentiell unendliche Anzahl von Entscheidungen erfordert. Man muß sich ja zu jedem Zeitpunkt überlegen, ob man zugreift." "Also. Sonst noch eine Idee?"

Neidfreiheit für drei Spieler

"Ja. In den frühen sechziger Jahren haben John Selfridge und John Horton Conway unabhängig voneinander ein neidfreies Protokoll für drei Spieler gefunden."

Es verläuft folgendermaßen:

1. Arthur schneidet den Kuchen in drei (faire) Teile.

2. Berta setzt aus (wenn sie glaubt, wenigstens zwei Stücke seien gleich groß und nicht kleiner als das dritte) oder schneidet von einem (dem größten) Stück etwas ab (um den ersten Fall herbeizuführen). Abgeschnittene Stückchen werden beiseite gelegt.

3. Clara, Berta und Arthur nehmen nun in dieser Reihenfolge je ein Stück (von dem sie jeweils glauben, es sei das größte oder ein größtes, also eines von mehreren gleich großen, und es gibt kein größeres). Wenn Berta in Schritt 2 ein Stück beschnitten hat, muß sie es nehmen – es sei denn, Clara hätte es schon gegriffen. Jetzt ist der Kuchen neidfrei verteilt – bis auf die Schnipsel. Das ist nicht ganz offensichtlich; aber es stimmt.

4. Wenn Berta im zweiten Schritt ausgesetzt hat, gibt es gar keine Schnipsel, und wir sind fertig. Wenn nicht, ernennen wir die Spielerin, die nicht das beschnittene Stück genommen hat, also entweder Berta oder Clara, zur Schneiderin; denn sie darf das Überbleibsel in drei Häufchen (die sie für gleich groß hält) aufteilen. Die andere nennen wir die Nicht-Schneiderin.

Arthur hat ihr gegenüber einen uneinholbaren Vorsprung in folgendem Sinne: Die Nicht-Schneiderin hat das beschnittene Stück erhalten; selbst wenn sie das Überbleibsel komplett einstreichen würde, hätte sie in Arthurs Einschätzung nicht mehr als ihren fairen Anteil erhalten, weil er die ursprünglichen drei Stücke alle für gleich groß hielt. Einerlei wie die Überbleibsel jetzt verteilt werden, Arthur wird nicht neidisch auf die Nicht-Schneiderin sein.

5. Die Spieler greifen sich die drei Häufchen in der Reihenfolge Nicht-Schneiderin, Arthur, Schneiderin. (Jeder wählt den in seinen Augen größten unter den Haufen, die noch zu haben sind.)

Da die Nicht-Schneiderin zuerst wählt, hat sie keinen Grund, neidisch zu sein. Arthur ist nicht neidisch auf die Nicht-Schneiderin wegen seines uneinholbaren Vorsprungs und auch nicht auf die Schneiderin, weil er vor ihr an der Reihe ist. Die Schneiderin schließlich kann auf niemanden neidisch sein, weil sie ja die Überbleibsel in die drei Häufchen aufgeteilt hat.

"Das ist ja ganz hübsch", sagte Arthur, dessen Geduld langsam zur Neige ging. "Aber ich sag's nur noch einmal: Wir sind vier und nicht drei." Dabei starrte er Detlef an und ließ sein Klappmesser aufschnappen. "Dieses Problem ist allerdings leicht lösbar..."

"Das wird nicht nötig sein", sagte Detlef hastig. "Vor einigen Jahren wurde eine Lösung gefunden – nach längerer Stagnation. Man wußte, daß für vier und mehr Spieler stets eine neidfreie Zuweisung existiert, aber keiner konnte ein Protokoll angeben, mit dem man nach endlich vielen Schritten garantiert eine finden würde."

Clara lehnte sich vor. "Also, was passierte?"


Teilung bis auf die letzten Krümel

"Der Wissenschaftsautor Dominic Olivastro veröffentlichte einen Übersichtsartikel zu dem Thema in der Zeitschrift ,The Sciences'. Steven Brams, ein Politologe an der Universität von New York, der auch Bücher über Spieltheorie geschrieben hat, war davon fasziniert, denn er fand in mathematischer Form wieder, was ihn schon lange beschäftigte: das Problem fairer Aufteilung in Wirtschaft und Politik, zum Beispiel die Aufteilung Deutschlands in Besatzungszonen der Alliierten nach dem Zweiten Weltkrieg – mit Berlin als dem Überbleibsel für die zweite Runde.

Brams entwickelte unabhängig von Selfridge und Conway ein neidfreies Protokoll für drei Spieler. In den ersten drei Schritte war es mit ihrem identisch. Statt sich aber über die Aufteilung des Restes komplizierte Gedanken zu machen, wandte Brams auf diesen nochmals die gleiche Methode an."

"Aber dabei entstehen wieder Überbleibsel", protestierte Berta.

"Schon richtig, nur sind es Überbleibsel zweiter Ordnung, die sind viel mickriger als die ersten. Darauf wird dann die Methode ein drittes Mal angewandt, und so weiter."

"Ist das wirklich ein Protokoll? Das ist nach endlich vielen Schritten ja nicht unbedingt zu Ende."

"Richtig. Aber es ist einfach, und es funktioniert."

"Na ja, aber..."

"Wart's ab. Am Ende kommt ein endliches Verfahren heraus. Jedenfalls machte sich Brams, durch seinen Erfolg ermutigt, an den Fall mit vier Leuten – und scheiterte."

Arthur fingerte drohend an seinem Messer herum. Detlef schluckte und fuhr hastig fort: "Da setzte er sich mit seinem Freund Alan Taylor in Verbindung, einem Mathematiker vom Union College in Schenectady."

"Wo ist das denn?"

"Staat New York."

"Ist ja auch egal."

"Jedenfalls", fuhr Detlef fort, "nahm Taylor den gleichen großzügigen Standpunkt ein wie Brams – Überbleibsel sind Peanuts, auf die kommt es nicht so an – und löste das Problem, allerdings auf merkwürdige Weise: Im ersten Schritt wird der Kuchen in fünf Teile aufgeteilt, obwohl es nur vier Spieler sind."

"Sonderbar."

"Ja. Taylor sagte, er habe keine Ahnung, wie er darauf gekommen sei."

Detlef referierte Taylors neidfreies Protokoll zur partiellen Aufteilung für vier Spieler so:

1. Arthur schneidet den Kuchen in fünf Teile (die er für gleich groß hält).

2. Berta beschneidet, falls nötig, ein oder zwei Stücke so, daß drei (ihrer Meinung nach) gleiche größte Stücke entstehen. Die Überbleibsel kommen auf die Seite.

3. Clara beschneidet, falls nötig, ein Stück, so daß (ihrer Meinung nach) zwei gleiche größte Stücke entstehen.

4. Detlef, Clara, Berta und Arthur greifen sich in dieser Reihenfolge jeweils ein Stück. Wenn Berta Stücke beschnitten hat, muß sie eins davon – falls überhaupt noch verfügbar – nehmen; gleiches gilt für Clara.

Es ist nicht schwer zu sehen, daß jeder Spieler sein Stück für ein größtes hält. Die Zuordnung ist also neidfrei. Das übrigbleibende fünfte Stück wird mit den anderen Überbleibseln vereint, darauf das Verfahren wieder angewandt, und so weiter.

"Alles schön und gut", sagte Arthur. "aber das hört doch wieder nicht von alleine auf."

"Stimmt. Genaugenommen hatten Brams und Taylor kein echtes Protokoll gefunden. Das verdroß Brams nicht allzusehr, denn in der Politik bleiben immer ein paar Restprobleme ungelöst. Doch Taylor, dem Mathematiker, ließ das keine Ruhe. Mit seinen Kollegen William Zwicker und Fred Galvin tüftelte er mehrere Monate, bis er die Reihenfolge der Wahlmöglichkeiten so angeordnet hatte, daß der Kuchen stets nach endlich vielen Schritten restlos verteilt war."

Absolute Gerechtigkeit in endlich vielen Schritten

Selbst für vier Spieler ist das Protokoll außerordentlich komplex. Es durchläuft zwanzig Schritte, von denen einer eine lange Folge von Beschneide-und-Wähle-Entscheidungen mehrerer Spieler enthält (siehe Kasten Seite 15). An zwei Stellen muß ein Spieler eine Zahl ansagen, die mit seiner Werteinschätzung der Stücke zusammenhängt. Die Anzahl der Schritte hängt von diesen Zahlen ab. Unter ungünstigen Umständen wird sie beliebig groß, aber nie unendlich.

Anders als Taylors ursprüngliches Verfahren beginnt dieses mit einer Teilung in vier Teile. Taylors neue Idee, mehr Stücke als Spieler zu verwenden, kommt jedoch mehrfach vor, auch in Form seiner ursprünglichen Fünfteilung.

Die vier Gauner begannen, sich durch das Brams-Taylor-Protokoll zu arbeiten. Nach zwei Stunden war der Tisch über und über mit bekritzeltem Papier bedeckt. Arthur starrte auf einen einzelnen großen Smaragd.

"Ich glaube, wir müssen den in zwölf Splitter teilen", sagte er und blickte den durchtriebenen Detlef durchbohrend an.

"Nun ja, das Protokoll ist gut für Kuchen und natürlich für alles andere, was sich leicht beliebig unterteilen läßt." Er bemerkte den Blick in Arthurs Augen. "Ähm, das Problem mit Stücken, die sich nicht unterteilen lassen, ist viel schwieriger und vielleicht überhaupt nicht lösbar." Seine Stimme überschlug sich vor Angst. "Aber Freddy der Hehler könnte diesen Smaragd -"

"Ich will Freddy hier nicht dabei haben", sagte Arthur. "Du hast viel kostbare Zeit verschwendet, und das habe ich gar nicht gerne."

In der Ferne hörte man Sirenengeheul.

Arthur wandte sich an Berta und Clara: "Ich glaube, es ist Zeit für eine unproportionale, gnadenfreie Verteilung nach dem Prinzip des bewegten Messers. Soll ich schneiden?"

"Au ja. Und wir wählen", entschied Berta.

Literaturhinweise

- An Envy-Free Cake Division Protocol. Von Steven J. Brams und Alan D. Taylor in: The American Mathematical Monthly, Band 102, Seiten 9 bis 18, Januar 1995.

– Old and New Moving-Knife Schemes. Von Steven J. Brams, Alan D. Taylor und William S. Zwicker in: The Mathematical Intelligencer, Band 17, Heft 4, Seiten 30 bis 35, 1995.


Aus: Spektrum der Wissenschaft 12 / 1996, Seite 12
© Spektrum der Wissenschaft Verlagsgesellschaft mbH