Faire Kuchenschneide, wenn die Spieler spät anschließen

Question

Die übliche Aussage der Faire Kuchenschneiderproblem Angenommen, alle $ N $ -Spieler erhalten gleichzeitig ihren Anteil. In vielen Fällen kommen die Spieler jedoch schrittweise an. Zum Beispiel können wir einen Kuchen über $ n $ player teilen, aber dann kommt ein neuer Spieler an und möchte einen Anteil.

Normalerweise erfordert Fair Cake Division viel Anstrengung (zum Beispiel müssen die Spieler viele Fragen beantworten), insbesondere wenn die Anzahl der Spieler groß ist.

Ist es möglich, die vorhandene Abteilung des Kuchens über $ N $ Player zu verwenden, um eine neue Division des Kuchens auf $ N+1 $ Player mit minimaler zusätzlicher Aufwand zu erstellen (dh wesentlich weniger Aufwand als das Neuverteilungen des Kuchens von Grund auf neu)?

Answer 1

Ich werde im Voraus sagen, dass ich keine gute Antwort auf Ihre Frage geben kann (ich denke, Sie könnten vielleicht ein Forschungspapier herausholen, wenn Sie könnten) der Schwierigkeiten liegen.

Hintergrund. Lassen Sie mich das Modell für das Kuchenschnitt eindeutig angeben. Wir möchten das Intervall $ $ [0,1] zwischen $ N $ Spielern teilen. Jeder Spieler $ i $ hat eine Bewertungsfunktion $ v_i (s) $ über Teilmengen $ s $ des Kuchens. Wir werden annehmen, dass diese Funktion eine Wahrscheinlichkeitsmaßnahme ist. Es ist nicht negativ und additiv (für disjoint $ a, b subseteq [0,1] $, $ v_i (a cup b) = v_i (a) + v_i (b) $) und $ v_i ([0,1] ) = 1 $. Eine Lösung für dieses Problem ist a Protokoll oder Algorithmus, der die Spieler abfragt und Teile des Intervalls zuweist. Beachten Sie, dass die Spieler bei der Beantwortung von Fragen falsch angemeldet/lügen können.

Einige Papiere haben spezifischer Einschränkungen; z.B, Bewertungsfunktionen sind kontinuierlich oder stückweise linear oder stückweise konstant.

Lassen Sie die den Spielern zugewiesenen Teile $ {S_1, dots, s_n } $ sein. Wir wollen oft die folgenden Eigenschaften eines Protokolls:

• Verhältnismäßigkeit: Jeder Spieler $ i $ hat eine Strategie, die garantiert, dass er einen Wert von mindestens $ (1/n) V_I ([0,1]) $ erhält. (Aus Sicht von $ i $ erhält er/er 1 $/n $ des Gesamtwerts des Kuchens.)
• Neidfeinheit: Jeder Spieler hat eine Strategie, die garantiert, dass $ V_I (S_I) Geq V_I (S_J) $ für jeden anderen Spieler $ j $. (Jeder Spieler bevorzugt sein eigenes Stück gegenüber dem Stück eines anderen Spielers.)

Beachten Sie, dass Neidfresiessheit Verhältnismäßigkeit impliziert.

Es gibt auch "operative" Eigenschaften, die wir vielleicht haben möchten, wie z. B. in wenige Teile, Polynomlaufzeit (oder überhaupt Berechnungsfähigkeit/Konstruktionsfähigkeit - wir möchten das Axiom der Wahl nicht verwenden, um eine Teilmenge des Kuchens auszuwählen! ), usw.

---

Spezifische Fragen zu stellen. Zwei Notizen. Zunächst wird jede Antwort auf Ihre Frage das allgemeine Problem lösen: Geben Sie zunächst den gesamten Kuchen für den Spieler $ 1 $ und lassen Sie die anderen Spieler online ankommen und dieses Protokoll iterativ anwenden. Wir sollten also erwarten, dass dieses Problem schwieriger ist als die Standard-Kuchenschnitt-Einstellung, auf die wir es anwenden.

Zweitens können wir Ihr Problem immer lösen, indem wir den gesamten Kuchen von allen zurücknehmen und einen bekannten Algorithmus verwenden, um ihn von Grund auf neu zu verteilen. Die Frage ist also nur, ob es eine etwas elegantere Möglichkeit gibt, dies zu tun. Ich denke, ein guter Weg, um dies zu quantifizieren, lautet: "Wann erfordert die Umverteilung weniger Zeit oder weniger Schnitte als von vorne zu beginnen./Oder wann können die Spieler einen erheblichen Teil ihrer aktuellen Slice behalten?"

1. Angenommen, wir haben eine beneidungsfreie Zuteilung für $ n $ Player. Wie verteilen wir eine neidfreie Zuordnung unter den Spielern $ N+1 $?

Ich vermute, das ist sehr schwierig. Der Grund dafür ist, dass es bereits schwierig ist, eine beneidungsfreie, effiziente Allokation zu finden. Soweit ich weiß, könnten bekannte Protokolle eine unbegrenzte Anzahl von Schnitten am Kuchen erfordern und sind sehr komplex. (Siehe Brams und Taylor, Ein beneidungsfreies Protokoll der Kuchenabteilung, 1995.) Es kann also nichts besser geben, als den gesamten Kuchen von allen zurückzunehmen und ihn mit Brams-Taylor in die $ n+1 $ Agents zu verteilen.

1. Angenommen, wir haben eine proportionale Zuordnung für $ n $; Wie verteilen wir eine proportionale Zuordnung für $ n+1 $?

Ich denke, das ist immer noch schwierig (wenn auch machbarer). Betrachten Sie den Fall, in dem jeder Spieler den Kuchen einheitlich schätzt und jeder Spieler eine Scheibe von 1 $/n $ hat. Was auch immer der neue Spieler tut, erfordert, dass der neue Spieler unter allen eine Umgestaltung erfordert. Hier ist ein weiterer schlechter Fall: Angenommen, der Spieler $ 1 $ hat eine Bewertung von genau 1 $/n $ für ihr Slice, aber der Spieler $ 2 $ $ von $ (n-1)/n $. Nehmen wir an, Spieler $ 2 $ Werte ihre eigene Scheibe bei genau 1 $/n $, aber schätzt Spieler $ 3 $ von $ $ (n-1)/n $ usw. mit Spieler $ n $ schätzt ihre eigene Slice bei 1 $/ N $ und Player $ 1 $ $ 's Slice bei $ (n-1)/n $. Jetzt kommt der neue Spieler an. Egal, was der neue Spieler will, Ihr Protokoll muss am Ende etwas von Spieler $ 2 $ bis Player $ 1 $, von Player $ $ bis zum Spieler $ $ $ $ usw. neu formulieren müssen.

---

Eine Referenz könnte sein Walsh, Online -Kuchenschnitt, in der algorithmischen Entscheidungstheorie 2011 (PDF -Link). Aber ich denke, dass das Papier davon ausgeht, dass wir im Voraus die Anzahl der ankommenden Agenten kennen und dass die Spielern ein Stück genau zugeteilt werden muss, wenn sie gehen (was vor dem Ende des Protokolls ist), so dass es wirklich nicht so anwendbar ist, dass Ihr Problem anwendbar ist.

---

Eine Möglichkeit, eine proportionale Zuordnung umzuverteilen, die die Verhältnismäßigkeit aufrechterhält, ist wie folgt. Lassen Sie jeden der vorliegenden $ n $ -Frieler sein zugewiesenes Stück Kuchen in $ n+1 $ $ poies schneiden, die er selbst gleich schätzt. Player $ N+1 $ wird jetzt das beste Stück aus jeder der Kürzungen des $ n $ Player auswählen. Es ist leicht zu zeigen, dass die resultierende Zuordnung auch proportional ist.

Answer 2

Angenommen, der Kuchen/Gebiet ist ein Kreis $ C $ mit Radius $ R $. Dann können wir $ n $ faire Stücke durch das kanonische Kuchenschnitt erstellen und so jedem Spieler einen Bereich von $ frac { pi r^2} {n} $ zuweisen. Wir können dann den $ (n+1) $ einen kleinen Kreis um das Zentrum zuweisen, und nachfolgende neue Spieler klingen um diesen (schlucken Teil des inneren Kreises) und so weiter. Auf diese Weise erhält jeder Spieler ein zusammenhängendes Stück/eine zusammenhängende Grundstück, das für die ersten $ N+1 $ Player auf monotone Weise schrumpft und sich für diejenigen, die sich später anschließen, in Richtung des Zentrums bewegt.

Das Ausarbeiten der Zahlen ist einfach; Lösen Sie für den ersten neuen Spieler einfach

$ qquad pi r_1^2 = frac { pi r^2} {n+1} $

den Radius für seine Verschwörung bekommen. Für die zweite, lösen Sie

$ qquad begin {align} pi r_1^2 & = frac { pi r^2} {n+2} pi r_2^2 - pi r_1^2 & = frac { pi r r r ^2} {n+2} end {align} $

(äußere) Radien für beide neuen Spieler und so weiter zu bekommen. Es scheint, dass Player $ n + i $ äußere Radius $ r_i = frac {r sqrt {i}} { sqrt {n + k}} $ nach $ k $ zusätzliche Spieler beigetreten ist, aber ich habe dies nicht beweisen .

Das erhalten Sie für $ n = 6 $ und $ k = 0,1,2,3 $:

^[Quelle]

Die gleiche Idee eignet sich für reguläre Polygone mit $ N $ Seiten. Wenn Sie ein Rechteck als Basisformular annehmen, können Sie etwas Ähnliches tun, indem Sie die ersten $ n $ gleich großen Spalten und die folgenden Spielerreihen zuweisen (beginnend auf einer Seite).