71. AUFGABE DER WOCHE

Zwei Personen können einen Kuchen fair, d.h. so, daß keine der Personen neidisch auf das Kuchenstück der anderen ist, aufteilen: Die erste Person teilt den Kuchen so, daß sie mit beiden Stücken zufrieden wäre. Anschließend wählt die zweite Person eines der Stücke für sich aus, woraufhin die erste Person die übrige Hälfte bekommt.

Sei nun n eine natürliche Zahl mit n ≥ 2. Die Frage ist nun: Gibt es ein faires Verfahren zur Aufteilung des Kuchens unter n Personen?

(Ein ”Verfahren“ sei hier ein nichtdeterministischer Algorithmus (mit einer allerdings unendlichen Zustandsmenge, da das den Kuchen repräsentierende Intervall [0, 1] in der Beschreibung vorkommt), wobei Nichtdeterminismus bedeute, daß in jedem Schritt des Algorithmus maximal eine der n Personen eine ”ja/nein“- Entscheidung fällen darf. Ein solches Verfahren heiße fair, wenn jede der n Personen unabhängig von Entscheidungen der anderen Personen mindestens 1/n des Kuchens durch ihre eigenen Entscheidungen bekommen kann. Jede Teilmenge des Kuchens werde von jeder der n Personen in der gleichen Weise, d.h. durch ein gemeinsames endlich-additives nichtatomares Wahrscheinlichkeitsmaß bewertet. Außerdem finde keine Kommunikation ”außerhalb“ des Algorithmus statt.)

Die ’Aufgabe der Woche’ ist eine inoffizielle Belustigung. Für den Urheber der ersten Lösung liegt in V4-206 ein namhafter Schokoriegel bereit. Vorschläge für schöne neue Aufgaben werden dankend aber schokoriegelfrei in V4-206 angenommen. Den Lösungsstatus einer Aufgabe, sowie die normalerweise montags neu erscheinende Aufgabe findet man unter http://www.math.unibielefeld.de/∼florian/adw/ .