Proportionales Kuchenschneiden

Eine proportionale Kuchenaufteilung ist eine Art faire Kuchenaufteilung . Es handelt sich um eine Aufteilung einer heterogenen Ressource („Kuchen“), die das Proportionalitätskriterium erfüllt , nämlich dass jeder Partner das Gefühl hat, sein zugeteilter Anteil sei mindestens 1/ n des Gesamtbetrags wert.

Bei der Diskussion um proportionale Aufteilung werden üblicherweise zwei Annahmen getroffen:

• Die Bewertungen der Partner sind nicht-atomar , d.h. es gibt keine unteilbaren Elemente mit positivem Wert.
• Die Wertvorstellungen der Partner sind additiv , d.h. wenn ein Stück geteilt wird, ist der Wert des Stücks gleich der Summe seiner Teile.

Der Kuchen wird mit bezeichnet . Es gibt Personen. Jede Person hat eine Wertfunktion . Eine Teilung des Kuchens, , heißt proportional, wenn:${\displaystyle C}$${\displaystyle n}$${\displaystyle i}$${\displaystyle V_{i}}$${\displaystyle X_{1}\sqcup \cdots \sqcup X_{n}=C}$

${\displaystyle V_{i}(X_{i})\geq V_{i}(C)/n}$ für jeden Menschen .${\displaystyle i\in \{1,\ldots ,n\}}$

Für zwei Personen ist „Teilen und Wählen“ die klassische Lösung. Eine Person teilt die Ressource in zwei vermeintlich gleich große Hälften, die andere wählt die Hälfte, die ihr lieber ist. Die Annahme der Nicht-Atomizität garantiert, dass derjenige, der den Kuchen teilt, ihn tatsächlich in zwei gleich große Stücke teilen kann; die Annahme der Additivität garantiert, dass beide Partner ihre Stücke mindestens als die Hälfte wertschätzen.

Es gibt viele Möglichkeiten, dieses Verfahren auf mehr als zwei Personen auszudehnen. Jede Methode hat ihre eigenen Vor- und Nachteile.

Der letzte Verminderer ist das früheste proportionale Teilungsverfahren, das für n Personen entwickelt wurde:

• Einer der Partner wird gebeten, ein Stück zu zeichnen, dessen Wert er auf mindestens 1/ n schätzt .
• Die anderen Partner haben ihrerseits die Möglichkeit zu behaupten, dass das aktuelle Stück tatsächlich mehr als 1/ n wert ist ; in diesem Fall werden sie aufgefordert, es so zu mindern, dass der verbleibende Wert nach ihrer eigenen Einschätzung 1/ n beträgt.
• Der letzte Partner, der das aktuelle Stück verkleinert, erhält es.
• Der restliche Kuchen wird dann auf die gleiche Weise unter den verbleibenden n  − 1 Personen aufgeteilt .

Per Induktion lässt sich beweisen, dass jeder Partner, der die Regeln befolgt, garantiert den Wert 1/ n erhält , unabhängig vom Verhalten der anderen Partner. Es handelt sich um ein diskretes Verfahren, das reihum gespielt werden kann. Im schlimmsten Fall sind Aktionen nötig: eine Aktion pro Spieler und Zug. Die meisten dieser Aktionen lassen sich jedoch theoretisch durchführen; tatsächlich werden nur n  − 1 Stücke des Kuchens benötigt. Daher können unter bestimmten Umständen alle Stücke zusammenhängend sein. ${\displaystyle n\times (n-1)/2=O(n^{2})}$

Das Moving-Knife-Verfahren ist eine kontinuierliche Version des Last Diminisher. ^{[ 1 ]}

• Ein Messer wird senkrecht zur Bewegungsrichtung von links nach rechts über den Kuchen geführt.
• Wer „Stopp“ ruft, sobald er glaubt, dass sich das Stück Kuchen links vom Messer befindet. (Der Ruf stoppt das Messer an der Stelle, die der Rufende für angemessen hält; jede Verzögerung würde dem anderen ermöglichen, sich ein Stück zu nehmen, das bis dahin zu groß geworden wäre.) Dann wird der Kuchen angeschnitten und jeder bekommt sein Stück.${\displaystyle 1/n}$
• Dies wird mit dem restlichen Kuchen und den übrigen Partnern wiederholt. Der letzte Partner erhält den restlichen Kuchen.

Das Fink-Protokoll ist ein Algorithmus, der die Teilung in immer kleinere, „gleiche“ Teile fortsetzt.

• Der erste Partner teilt die Ressource in zwei Hälften auf, die er für gleich groß hält.
• Der zweite Partner wählt dann die Hälfte aus und überlässt den Rest dem ersten Partner.
• Jeder dieser beiden Partner teilt dann seinen jeweiligen Anteil in Drittel auf.
• Der dritte Partner wählt zwei der entstandenen Portionen aus: eine vom ersten Partner und eine vom zweiten Partner.
• Bei vier Partnern teilt jeder der ersten drei Partner seinen Anteil in vier Teile, und so geht es weiter.

Der Vorteil dieses Protokolls liegt darin, dass es online ausgeführt werden kann – sobald neue Partner der Gruppe beitreten, wird die bestehende Aufteilung entsprechend angepasst, ohne dass der gesamte Aufteilungsprozess neu gestartet werden muss. Der Nachteil besteht darin, dass jeder Partner eine große Anzahl unzusammenhängender Anteile anstelle eines einzigen zusammenhängenden Anteils erhält.

Der Einzelteiler ist ein Verfahren, das auf einer gleichmäßigen Aufteilung durch einen einzelnen Akteur basiert. Sein Vorteil besteht darin, dass es verallgemeinert werden kann, um eine symmetrische, faire Kuchenaufteilung zu erzielen .

Mithilfe einer Divide-and-Conquer-Strategie lässt sich eine proportionale Aufteilung in der Zeit O( n  log  n ) erreichen. ^{[ 2 ]} Der Einfachheit halber wird das Verfahren hier für eine gerade Anzahl von Partnern beschrieben, es kann aber leicht an eine beliebige Anzahl von Partnern angepasst werden:

• Jeder Partner soll eine Linie ziehen, die den Kuchen in zwei seiner Meinung nach gleichwertige Stücke teilt. Die Teile dürfen sich nicht kreuzen; dies lässt sich einfach gewährleisten, indem man entweder nur horizontale oder nur vertikale Linien zulässt.
• Der Algorithmus sortiert die n Linien in aufsteigender Reihenfolge und teilt den Kuchen in der Mitte der Linien. Wenn beispielsweise 4 Partner Linien bei x  = 1, x  = 3, x  = 5 und x  = 9 zeichnen, teilt der Algorithmus den Kuchen vertikal bei x  = 4.
• Der Algorithmus ordnet jeder der beiden Hälften n /2 Partner zu – diejenigen, deren Linie innerhalb dieser Hälfte liegt. Beispielsweise werden die Partner, die Linien bei x  = 1 und x  = 3 gezeichnet haben, der westlichen Hälfte zugeordnet, die beiden anderen Partner der östlichen. Jede Hälfte wird rekursiv unter den ihr zugeordneten n /2 Partnern aufgeteilt.

Es ist möglich, durch Induktion zu beweisen, dass jeder Partner, der sich an die Regeln hält, garantiert einen Spielstein mit einem Wert von mindestens 1/ n erhält , unabhängig davon, was die anderen Partner tun.

Dank der Divide-and-Choose-Strategie ist die Anzahl der Iterationen nur O(log n ), im Gegensatz zu O( n ) beim Last-Diminisher-Verfahren. In jeder Iteration muss jeder Partner eine Markierung setzen. Daher beträgt die Gesamtzahl der benötigten Markierungen O( n log n ).

Dieser Algorithmus verfügt über eine randomisierte Version, mit der die Anzahl der Markierungen reduziert werden kann; siehe Even-Paz-Algorithmus .

Eine andere Herangehensweise beim Kuchenanschneiden besteht darin, dass jeder Partner eine bestimmte Anzahl von Stücken zieht, die von der Anzahl der Partner, p ( n ), abhängt, und jedem Partner eines seiner ausgewählten Stücke gibt, so dass sich die Stücke nicht überlappen.

Nehmen wir als einfaches Beispiel für ein Auswahlverfahren an, der Kuchen sei ein eindimensionales Intervall und jeder Partner wolle ein einzelnes zusammenhängendes Intervall erhalten. Verwenden Sie folgendes Protokoll:

1. Jeder Partner teilt den Kuchen privat in n Intervalle auf, die er als gleichwertig betrachtet; diese werden Kandidatenstücke genannt .
2. Das Protokoll ordnet die n² Kandidaten nach aufsteigender östlicher Position (von West nach Ost) und wählt das Intervall mit dem westlichsten östlichen Ende aus. Dieses Intervall wird als Endstück bezeichnet .
3. Das Protokoll übergibt das letzte Teilstück seinem Besitzer und entfernt alle Kandidaten, die von diesem Teilstück überschnitten werden. Schritt 2 wird dann mit den verbleibenden Intervallen der übrigen n  − 1 Partner wiederholt.

Die Auswahlregel in Schritt 2 garantiert, dass in jeder Iteration höchstens ein Intervall jedes Partners entfernt wird. Daher entspricht die Anzahl der Intervalle pro Partner nach jeder Iteration weiterhin der Anzahl der Partner, und der Prozess kann fortgesetzt werden, bis jeder Partner ein Intervall erhält. ^{[ 3 ]}

Dieses Protokoll erfordert, dass jeder Partner n Anfragen beantwortet, sodass die Anfragekomplexität O( n ² ) beträgt, ähnlich wie beim Last Diminisher.

Durch Randomisierung lässt sich die Anzahl der Anfragen reduzieren. Dabei meldet jeder Partner nicht die gesamte Menge von n Kandidaten, sondern nur eine konstante Anzahl d zufällig ausgewählter Kandidaten. Die Anfragekomplexität beträgt O( n ), was optimal ist. In vielen Fällen ist es weiterhin möglich, jedem Partner genau einen Kandidaten zuzuweisen, sodass sich die Kandidaten nicht überschneiden. Es gibt jedoch Szenarien, in denen eine solche Zuweisung nicht möglich ist.

Wir können einen Kuchen immer noch mit O( n ) Anfragen schneiden, wenn wir einige Kompromisse eingehen:

• Anstatt eine vollständige Proportionalität zu gewährleisten, garantieren wir eine partielle Proportionalität , d. h. jeder Partner erhält einen bestimmten konstanten Anteil f ( n ) des Gesamtwerts, wobei f ( n )<1/ n .
• Anstatt jedem Partner ein einzelnes zusammenhängendes Stück zu geben, geben wir jedem Partner eine Vereinigung aus einem oder mehreren unzusammenhängenden Stücken.

Das allgemeine Schema ist wie folgt: ^{[ 4 ]}

1. Jeder Partner teilt den Kuchen privat in Stücke von gleichem subjektivem Wert auf. Diese n⋅an Stücke werden Kandidatenstücke genannt .
2. Jeder Partner wählt 2 ^d Kandidatensteine ​​gleichverteilt zufällig mit Zurücklegen aus. Die Kandidatensteine ​​werden in d Paare gruppiert, die der Partner dem Algorithmus meldet. Diese n⋅d Paare werden Viertelfinal-Klammern genannt .
3. Aus jedem Viertelfinal-Turnierbaum wählt der Algorithmus ein einzelnes Teilstück aus – dasjenige, das die wenigsten anderen Kandidatenteile schneidet. Diese n⋅d Teilstücke werden als Halbfinalteile bezeichnet .
4. Für jeden Partner wählt der Algorithmus ein einzelnes Tortenstück aus; diese werden als Endstücke bezeichnet . Die Endstücke werden so ausgewählt, dass jeder Punkt des Kuchens von höchstens zwei Endstücken bedeckt ist (siehe unten). Gelingt dies, fahren Sie mit Schritt 5 fort. Andernfalls beginnen Sie wieder bei Schritt 1.
5. Jedes Stück des Kuchens, das nur zu einem einzigen Endstück gehört, wird dem Besitzer dieses Stücks ausgehändigt. Jedes Stück des Kuchens, das zu zwei Endstücken gehört, wird proportional nach einem beliebigen deterministischen proportionalen Teilungsalgorithmus aufgeteilt .

Der Algorithmus garantiert, dass jeder Partner mit Wahrscheinlichkeit O(1 a ² ) mindestens die Hälfte eines seiner Kandidatenstücke erhält, was (bei additiven Werten) einen Wert von mindestens 1/2 an impliziert . Es gibt O( n ) Kandidatenstücke und O( n ) zusätzliche Teilungen in Schritt 5, die jeweils O(1) Zeit benötigen. Daher beträgt die Gesamtlaufzeit des Algorithmus O( n ).

Die größte Herausforderung bei diesem Verfahren besteht in der Auswahl der letzten Teile in Schritt 4. Einzelheiten hierzu finden sich im Edmonds-Pruhs-Protokoll .

Die Ergebnisse der Härteprüfung werden im Sinne des Robertson-Webb-Abfragemodells angegeben , d. h. sie beziehen sich auf Verfahren, die den Agenten zwei Arten von Abfragen stellen: „Evaluate“ und „Mark“.

Jedes deterministische proportionale Teilungsverfahren für n ≥ 3 Partner benötigt mindestens n Anfragen, selbst wenn alle Bewertungen identisch sind. ^{[ 2 ]}

Darüber hinaus benötigt jedes deterministische oder randomisierte proportionale Teilungsverfahren, bei dem jeder Person ein zusammenhängendes Stück zugewiesen wird, Ω( n log n ) Aktionen. ^{[ 5 ]}

Darüber hinaus benötigt jedes deterministische proportionale Teilungsverfahren Ω( n log n ) Anfragen, selbst wenn es jedem Partner ein Stück zuweisen darf, das eine Vereinigung von Intervallen ist, und selbst wenn es nur annähernde Fairness gewährleisten darf . Der Beweis basiert auf einer unteren Schranke für die Komplexität, für einen einzelnen Spieler ein Stück Kuchen zu finden, das sowohl wertvoll als auch schmal ist. ^{[ 6 ]}

Diese Ergebnisse zur Härte implizieren, dass die rekursive Halbierung der schnellste Algorithmus ist, um bei zusammenhängenden Teilen vollständige Proportionalität zu erreichen, und der schnellste deterministische Algorithmus, um selbst bei nicht zusammenhängenden Teilen partielle Proportionalität zu erzielen. Nur im Fall von Verbesserungen durch randomisierte Algorithmen, die partielle Proportionalität bei nicht zusammenhängenden Teilen garantieren, ist eine Verbesserung möglich.

Wenn die Spieler nur mit endlicher Genauigkeit schneiden können, dann umfasst die untere Schranke Ω(n log n) auch randomisierte Protokolle. ^{[ 6 ]}

Die folgende Tabelle fasst die bekannten Ergebnisse zusammen: ^{[ 4 ]}

Das Proportionalitätskriterium lässt sich auf Situationen verallgemeinern, in denen die Anteile der Partner ungleich verteilt sind. Beispielsweise kann eine Ressource zwei Gesellschaftern gehören, wobei Alice 8/13 und George 5/13 hält. Dies führt zum Kriterium der gewichteten Proportionalität (WPR): Es gibt mehrere Gewichte w _{_i} , die sich zu 1 summieren, und jeder Partner i sollte gemäß seiner eigenen Bewertung mindestens einen Anteil w _{_i} an der Ressource erhalten. Zur Ermittlung einer WPR-Aufteilung können verschiedene Algorithmen verwendet werden. Die größte Herausforderung besteht darin, dass die Anzahl der Teilungsschritte selbst bei nur zwei Partnern groß sein kann.

Eine superproportionale Aufteilung ist eine Aufteilung, bei der jeder Partner gemäß seiner eigenen subjektiven Bewertung strikt mehr als 1/ n der Ressource erhält.

Natürlich existiert eine solche Aufteilung nicht immer: Wenn alle Partner exakt dieselben Wertfunktionen haben, können wir bestenfalls jedem Partner genau 1/ n zuweisen . Eine notwendige Bedingung für die Existenz einer superproportionalen Aufteilung ist also, dass nicht alle Partner dasselbe Wertmaß haben.

Überraschenderweise ist diese Bedingung auch dann hinreichend, wenn die Bewertungen additiv und nicht-atomar sind. Das heißt, wenn es mindestens zwei Partner gibt, deren Wertfunktion sich auch nur geringfügig unterscheidet, dann gibt es eine überproportionale Aufteilung, bei der alle Partner mehr als 1/ n erhalten .

Neben der üblichen Bedingung, dass alle Teile zusammenhängen müssen, gibt es in manchen Fällen zusätzliche Einschränkungen. Insbesondere wenn es sich bei dem aufzuteilenden Gebiet um ein umstrittenes Territorium handelt, das sich über mehrere Länder erstreckt, kann es erforderlich sein, dass das jedem Land zugeteilte Stück an dessen aktuellen Standort angrenzt. Eine proportionale Aufteilung mit dieser Eigenschaft existiert stets und lässt sich durch die Kombination des Last-Diminisher-Protokolls mit geometrischen Tricks unter Verwendung konformer Abbildungen finden .

Wenn das zu teilende Objekt zweidimensional ist, wie beispielsweise ein Grundstück oder eine Werbefläche in Print- oder elektronischen Medien, müssen die Stücke neben der Konnektivität oft auch bestimmte geometrische Anforderungen erfüllen. So kann beispielsweise gefordert sein, dass jedes Stück ein Quadrat, ein breites Rechteck oder allgemein ein breites Objekt ist . Bei solchen Anforderungen an die Breite ist eine proportionale Teilung in der Regel nicht möglich, wohl aber eine teilweise proportionale, die sich mithilfe effizienter Algorithmen finden lässt. ^{[ 7 ]}

Neben der Proportionalität wird oft auch gefordert, dass die Aufteilung wirtschaftlich effizient ist , d. h. die soziale Wohlfahrt maximiert (definiert als die Summe der Nutzen aller Akteure).

Nehmen wir beispielsweise einen Kuchen mit 500 Gramm Schokolade und 500 Gramm Vanille. Dieser wird zwischen zwei Partnern aufgeteilt, von denen einer nur die Schokolade und der andere nur die Vanille möchte. Viele Aufteilungsprotokolle sehen vor, jedem Partner 250 Gramm Schokolade und 250 Gramm Vanille zu geben. Diese Aufteilung ist proportional, da jeder Partner die Hälfte seines Gesamtwerts erhält, sodass die normalisierte soziale Wohlfahrt 1 beträgt. Diese Aufteilung ist jedoch sehr ineffizient, da man die gesamte Schokolade dem einen Partner und die gesamte Vanille dem anderen geben könnte, wodurch eine normalisierte soziale Wohlfahrt von 2 erreicht würde.

Das optimale proportionale Aufteilungsproblem besteht darin, unter allen möglichen proportionalen Aufteilungen diejenige zu finden, die den sozialen Nutzen maximiert. Dieses Problem ist derzeit nur für den Spezialfall lösbar, dass der Kuchen ein eindimensionales Intervall ist und die Nutzendichtefunktionen linear sind (d. h. u ( x ) =  Ax  +   B ). Im Allgemeinen ist das Problem NP-schwer. Sind die Nutzenfunktionen nicht normalisiert (d. h. , jeder Partner darf einen anderen Wert für den gesamten Kuchen haben), ist die Approximation des Problems sogar bis auf einen Faktor von 1/ √n NP-schwer . ^{[ 8 ]}

Wahrhaftigkeit ist keine Eigenschaft der Aufteilung selbst, sondern eine Eigenschaft des Protokolls. Alle Protokolle zur proportionalen Aufteilung sind schwach wahrhaftig, da jeder Partner, der gemäß seiner wahren Wertschätzung handelt, garantiert mindestens 1/ n (bzw. 1/ an im Falle eines teilweise proportionalen Protokolls) erhält, unabhängig vom Verhalten der anderen Partner. Selbst wenn alle anderen Partner eine Koalition bilden, deren einzige Absicht darin besteht, ihm zu schaden, erhält er dennoch seinen garantierten Anteil. ^{[ 9 ]}

Die meisten Protokolle sind jedoch nicht absolut wahrheitsgemäß, da manche Partner einen Anreiz haben könnten, zu lügen, um mehr als den garantierten Anteil zu erhalten. Dies gilt selbst für das einfache „ Teile und wähle “-Protokoll: Kennt derjenige, der teilt, die Präferenzen desjenigen, der wählt, kann er ein Stück abschneiden, das der Wählende als etwas weniger als die Hälfte bewertet, derjenige, der teilt, selbst aber als deutlich mehr als die Hälfte.

Es gibt wahrheitsgemäße Mechanismen, um eine perfekte Teilung zu erreichen ; da eine perfekte Teilung proportional ist, sind dies auch wahrheitsgemäße Mechanismen für eine proportionale Teilung.

Diese Mechanismen können erweitert werden, um eine superproportionale Teilung zu ermöglichen , sofern eine solche existiert: ^{[ 10 ]}

1. Bitten Sie jeden Partner, seine gesamte Wertmessung mitzuteilen.
2. Wählen Sie eine zufällige Partition (siehe ^{[ 10 ]} für weitere Details).
3. Falls die zufällige Aufteilung gemäß den angegebenen Wertmaßen überproportional ist, implementieren Sie sie. Andernfalls verwenden Sie einen Mechanismus, der eine korrekte Aufteilung gewährleistet.

Existiert eine superproportionale Aufteilung, so besteht eine positive Wahrscheinlichkeit, dass diese in Schritt 2 ausgewählt wird. Daher ist der Erwartungswert jedes wahrheitsgemäßen Partners strikt größer als 1/ n . Um die Wahrhaftigkeit des Mechanismus zu überprüfen, betrachten wir drei Fälle: (a) Ist die ausgewählte Aufteilung tatsächlich superproportional, so besteht die einzige mögliche Folge einer Lüge darin, den Mechanismus in die Irre zu führen und ihn glauben zu lassen, dass sie es nicht ist. Dies führt dazu, dass der Mechanismus eine perfekte Aufteilung durchführt, was für alle Partner, einschließlich des Lügners, nachteilig ist. (b) Ist die ausgewählte Aufteilung nicht superproportional, weil sie nur dem Lügner einen Wert von 1/ n oder weniger zuweist, so besteht die einzige Folge einer Lüge darin, dass der Mechanismus die Aufteilung für superproportional hält und sie durchführt, was nur dem Lügner selbst schadet. (c) Ist die ausgewählte Aufteilung tatsächlich nicht superproportional, weil sie einem anderen Partner einen Wert von 1/ n oder weniger zuweist, so hat eine Lüge keinerlei Auswirkung, da die Aufteilung ohnehin nicht durchgeführt wird.

Wenn die zu teilende Ressource unerwünscht ist (wie bei der Aufteilung von Hausarbeiten ), wird eine proportionale Aufteilung als eine Aufteilung definiert, bei der jede Person höchstens 1/ n der Ressource erhält (d. h. das Ungleichheitszeichen wird umgekehrt).

Die meisten Algorithmen für die proportionale Aufteilung lassen sich auf einfache Weise an die Aufgabenteilung anpassen.

• Exakte Teilung

• Brams, Steven J.; Taylor, Alan D. „Ein neues proportionales Verfahren für das n-Personen-Kuchenaufteilungsproblem.“ In: *Social Choice and Welfare*, Bd. 7, Nr. 3, 1990, S. 247–261. Online verfügbar .
• Eine Zusammenfassung der proportionalen und anderer Divisionsverfahren findet sich in: Austin, AK (1982). „Sharing a Cake“. The Mathematical Gazette . 66 (437): 212–215 . doi : 10.2307/3616548 . JSTOR 3616548. S2CID 158398839 .