Gerechte Kuchenaufteilung

Die gerechte Kuchenaufteilung (EQ) ist eine Art von fairem Kuchenaufteilungsproblem , bei dem das Fairnesskriterium die Gleichbehandlung ist . Es handelt sich um eine Kuchenaufteilung, bei der der subjektive Wert für alle Partner gleich ist, d. h. jeder Partner ist mit seinem Anteil gleichermaßen zufrieden. Mathematisch bedeutet dies, dass für alle Partner i und j gilt :

${\displaystyle V_{i}(X_{i})=V_{j}(X_{j})}$

Wo:

• ${\displaystyle X_{i}}$ist das Stück Kuchen, das Partner i zugeteilt wurde ;
• ${\displaystyle V_{i}}$ist das Wertmaß für Partner i . Es handelt sich um eine reellwertige Funktion , die für jedes Stück Kuchen eine Zahl zurückgibt, die den Nutzen von Partner i aus diesem Stück darstellt. Üblicherweise werden diese Funktionen so normiert, dass und für jedes i gilt .${\displaystyle V_{i}(\emptyset )=0}$${\displaystyle V_{i}(EntireCake)=1}$

Beispiele und Vergleiche mit anderen Fairnesskriterien finden Sie auf der Seite zum Thema Gerechtigkeit .

Bei zwei Partnern ist eine gerechte Aufteilung mit einem einzigen Schnitt möglich, erfordert jedoch die genaue Kenntnis der Wertvorstellungen der Partner. ^{[ 1 ]} Angenommen, der Kuchen entspricht dem Intervall [0,1]. Berechnen Sie für jedes und und tragen Sie die Werte in ein gemeinsames Diagramm ein. Beachten Sie, dass der erste Graph von 0 bis 1 steigt und der zweite Graph von 1 bis 0 fällt; sie haben also einen Schnittpunkt. Ein Schnittpunkt an diesem Punkt führt zu einer gerechten Aufteilung. Diese Aufteilung besitzt mehrere weitere Eigenschaften: ${\displaystyle x\in [0,1]}$${\displaystyle u_{1}([0,x])}$${\displaystyle u_{2}([x,1])}$

• Es handelt sich um EF, da jeder Partner einen Wert von mindestens 1/2 erhält.
• Es handelt sich nicht um EX, da der Wert pro Partner mehr als 1/2 betragen kann.
• Unter allen Teilungen, die einen einzigen Schnitt verwenden, ist diese Teilung Pareto-effizient . Es kann jedoch effizientere Teilungen geben, die zwei oder mehr Schnitte verwenden. ^{[ 2 ]}
• Wird die Richtung des Kuchens zufällig gewählt (d. h. er kann so umgedreht werden, dass 0 zu 1 und 1 zu 0 wird), so ist dieses Verfahren auch schwach wahrheitsgemäß, und zwar in folgendem Sinne: Nur durch die Abgabe aufrichtiger Wahrscheinlichkeitsmaße kann ein Partner sicherstellen, dass er mindestens die Hälfte des Kuchens erhält. ^{[ 1 ]}

Das gleiche Verfahren kann auch zur Aufteilung von Hausarbeiten (mit negativem Nutzen) angewendet werden.

Das vollständige Offenlegungsverfahren hat eine Variante ^{[ 3 ]} , die eine schwächere Art von Fairness und eine stärkere Art von Wahrhaftigkeit erfüllt. Das Verfahren ermittelt zunächst die Medianwerte beider Partner. Angenommen, der Medianwert von Partner A ist und der von Partner B ist , mit . Dann erhält A und B erhält . Es entsteht ein Überschuss - . Dieser Überschuss wird zu gleichen Teilen zwischen den Partnern aufgeteilt . Wenn beispielsweise A den Überschuss mit 0,4 und B mit 0,2 bewertet, erhält A doppelt so viel Wert von wie B. Daher ist dieses Protokoll nicht fair, aber dennoch EF. Es ist in folgendem Sinne schwach wahrheitsgemäß: Ein risikoaverser Spieler hat einen Anreiz, seine wahre Bewertung anzugeben, da die Angabe einer falschen Bewertung zu einem geringeren Wert führen könnte. ${\displaystyle a}$${\displaystyle b}$${\displaystyle 0<a<b<1}$${\displaystyle [0,a]}$${\displaystyle [b,1]}$${\displaystyle [a,b]}$${\displaystyle [a,b]}$

Das Austin-Verfahren mit dem beweglichen Messer gibt jedem der beiden Partner ein Stück mit einem subjektiven Wert von genau 1/2. Die Teilung lautet also EQ, EX und EF. Es sind zwei Schnitte erforderlich, und einer der Partner erhält zwei voneinander getrennte Stücke.

Sind mehr als zwei Schnitte zulässig, kann eine Aufteilung erreicht werden, die nicht nur EQ, sondern auch EF und PE entspricht . Einige Autoren bezeichnen eine solche Aufteilung als „perfekt“. ^{[ 4 ]}

Die Mindestanzahl der für eine PE-EF-EQ-Aufteilung erforderlichen Schnitte hängt von den Bewertungen der Partner ab. In den meisten praktischen Fällen (einschließlich aller Fälle, in denen die Bewertungen stückweise linear sind) ist die Anzahl der erforderlichen Schnitte endlich. In diesen Fällen ist es möglich, sowohl die optimale Anzahl der Schnitte als auch deren genaue Positionen zu bestimmen. Der Algorithmus erfordert die vollständige Kenntnis der Bewertungen der Partner. ^{[ 4 ]}

Alle oben genannten Verfahren sind kontinuierlich: Das zweite erfordert ein sich kontinuierlich bewegendes Messer, die anderen erfordern eine kontinuierliche Aufzeichnung der beiden Messwerte. Daher können sie nicht in einer endlichen Anzahl diskreter Schritte durchgeführt werden.

Diese Unendlichkeitseigenschaft ist charakteristisch für Divisionsaufgaben, die ein exaktes Ergebnis erfordern. Siehe Exakte Division#Unmöglichkeit .

Eine nahezu gerechte Aufteilung ist eine Aufteilung, bei der sich die Werte der Partner für jedes gegebene um höchstens unterscheiden . Eine nahezu gerechte Aufteilung für zwei Partner kann in endlicher Zeit und mit einem einzigen Schnitt gefunden werden. ^{[ 5 ]}${\displaystyle \epsilon }$${\displaystyle \epsilon >0}$

Austins Verfahren lässt sich auf n Partner erweitern . Dabei erhält jeder Partner einen Anteil mit einem subjektiven Wert von genau . Diese Aufteilung ist EQ, aber nicht notwendigerweise EX, EF oder PE (da manche Partner den Anteil anderer Partner höher bewerten könnten ). ${\displaystyle 1/n}$${\displaystyle 1/n}$

Es gibt ein weiteres Verfahren mit n - 1 beweglichen Messern, mit dem sich für jede beliebige Reihenfolge der Agenten eine zusammenhängende , gerechte Aufteilung finden lässt . ^{[ 6 ] : Abs. 6.2}

Jones' vollständiges Offenlegungsverfahren kann wie folgt auf Partner ausgedehnt werden: ^{[ 3 ]}${\displaystyle n}$

• Für jede mögliche Reihenfolge der Partner wird ein Gleichungssystem mit Variablen aufgestellt: Die Variablen sind die Trennpunkte, und die Gleichungen bestimmen die Gleichbehandlung benachbarter Partner. Beispiel: Bei drei Partnern in der Reihenfolge A:B:C sind die beiden Variablen (der Trennpunkt zwischen A und B) und , und die beiden Gleichungen lauten und . Dieses Gleichungssystem besitzt mindestens eine Lösung, in der alle Partner den gleichen Wert haben.${\displaystyle n!}$${\displaystyle n-1}$${\displaystyle n-1}$${\displaystyle n-1}$${\displaystyle x_{AB}}$${\displaystyle x_{BC}}$${\displaystyle V_{A}(0,x_{AB})=V_{B}(x_{AB},x_{BC})}$${\displaystyle V_{B}(x_{AB},x_{BC})=V_{C}(x_{BC},1)}$
• Wähle aus allen möglichen Reihenfolgen diejenige aus, bei der der (gleiche) Wert aller Partner am größten ist.${\displaystyle n!}$

Beachten Sie, dass der maximale gerechte Wert mindestens betragen muss , da wir bereits wissen, dass eine proportionale Aufteilung (bei der jeder Partner mindestens erhält ) möglich ist. ${\displaystyle 1/n}$${\displaystyle 1/n}$

Sind die Wertmaße der Partner absolut stetig zueinander (haben sie also denselben Träger), so muss jede Wertsteigerung eines Partners zwangsläufig den Wert eines anderen Partners verringern. Dies bedeutet, dass die Lösung PE unter den Lösungen, die zusammenhängende Teile ergeben, die beste Lösung ist.

Brams, Jones und Klamler untersuchen eine Teilung, die aus EQ, PE und EF besteht (sie nennen eine solche Teilung "perfekt").

Zunächst beweisen sie, dass bei drei Partnern, die verbundene Teile erhalten müssen, eine EQ+EF-Aufteilung möglicherweise nicht existiert. ^{[ 3 ]} Sie tun dies, indem sie drei spezifische Wertmaße auf einem eindimensionalen Kuchen beschreiben, in dem jede EQ-Zuteilung mit zwei Schnitten nicht EF entspricht.

Anschließend beweisen sie, dass bei drei oder mehr Partnern eine PE+EF+EQ-Teilung selbst bei unzusammenhängenden Teilen nicht existieren muss. ^{[ 2 ]} Sie tun dies, indem sie drei spezifische Wertmaße auf einem eindimensionalen Kuchen mit folgenden Eigenschaften beschreiben:

• Bei zwei Kürzungen ist nicht jede EQ-Zuteilung EF oder PE (es gibt aber Zuteilungen, die EF und 2-PE oder EQ und 2-PE sind).
• Bei 3 Kürzungen ist nicht jede EQ-Zuteilung eine PE-Zuteilung (es gibt aber eine EQ+EF-Zuteilung).
• Bei 4 Kürzungen ist nicht jede EQ-Zuteilung EF (es gibt aber eine EQ+PE-Zuteilung).

Ein Pie ist ein Kuchen in Form eines eindimensionalen Kreises (siehe faires Pie-Schneiden ).

Barbanel, Brams und Stromquist untersuchen die Existenz von Teilungen eines Kuchens, die sowohl EQ als auch EF sind. Die folgenden Existenzresultate werden bewiesen, ohne einen spezifischen Teilungsalgorithmus anzugeben: ^{[ 7 ]}

• Für zwei Partner existiert stets eine Aufteilung des Kuchens, die sowohl neidfrei als auch gerecht ist. Wenn die Wertmaße der Partner absolut stetig zueinander sind (d. h. jedes Stück, das für den einen Partner einen positiven Wert hat, hat auch für den anderen Partner einen positiven Wert), dann existiert eine Aufteilung, die neidfrei, gerecht und ungeteilt ist.
• Bei drei oder mehr Partnern ist es möglicherweise unmöglich, eine Aufteilung zu finden, die sowohl neidfrei als auch gerecht ist. Es gibt aber immer eine Aufteilung, die sowohl gerecht als auch unparteiisch ist.

Das angepasste Gewinnerverfahren berechnet eine gerechte, neidfreie und effiziente Aufteilung eines Satzes teilbarer Güter zwischen zwei Partnern.

Eine gerechte Kuchenverteilung lässt sich im Robertson-Webb-Abfragemodell mit einem endlichen Protokoll nicht finden , selbst nicht für zwei Agenten. ^{[ 8 ]} Darüber hinaus gilt für jedes ε > 0:

• Ein zusammenhängendes, ε-gerechtes Kuchenaufteilungsverfahren benötigt mindestens Ω(log ε ⁻¹ ) Anfragen. ^{[ 9 ]} Für 2 Agenten existiert ein Protokoll mit einer Laufzeit von O(log ε ^{−1 ). [ 5 ]} Für 3 oder mehr Agenten benötigt das beste bekannte Protokoll O( n (log n + log ε ⁻¹ )) Anfragen. ^{[ 10 ]}
• Selbst ohne Konnektivität erfordert die ε-gerechte Kuchenaufteilung mindestens Ω(log ε ⁻¹ / log log ε ⁻¹ ) Anfragen. ^{[ 8 ]}

Die Regel der maximalen gerechten Aufteilung ist eine Regel, die aus allen gerechten Kuchenaufteilungen diejenige auswählt, bei der der gemeinsame Wert der Akteure maximal ist. Es gibt zwei Varianten:

• Die Regel der absoluten Gleichheit gleicht die absoluten (nicht normierten) Werte an;
• Die Regel der relativen Gleichbehandlung gleicht die relativen (normalisierten) Werte an.

Es gibt immer eine zusammenhängende, maximal gerechte Aufteilung (sowohl absolut als auch relativ), und diese kann mithilfe eines verallgemeinerten Moving-Knives- Verfahrens gefunden werden.

• Die absolut- gerechte Regel ist schwach Pareto-optimal und ressourcenmonoton , aber nicht proportional .
• Die Regel der relativen Gerechtigkeit ist schwach Pareto-optimal und proportional, aber nicht ressourcenmonoton. ^{[ 6 ]}

• Egalitäre Kuchenaufteilung – eine Zuteilung, die den geringsten Nutzen eines Akteurs maximiert. Oftmals deckt sich die egalitäre Zuteilung mit der gerechten Zuteilung, da bei unterschiedlichen Nutzen der geringere Nutzen verbessert werden kann, indem man dem Akteur mit dem höheren Nutzen etwas Kuchen wegnimmt.