Faires Kuchenschneiden, wenn Spieler zu spät kommen

11

Die übliche Aussage des fairen Kuchenschneidproblems geht davon aus, dass alle Spieler gleichzeitig ihren Anteil erhalten. In vielen Fällen kommen die Spieler jedoch schrittweise an. Zum Beispiel können wir einen Kuchen auf Spieler verteilen, aber dann kommt ein neuer Spieler und möchte einen Anteil.nn

Normalerweise erfordert eine faire Kuchenaufteilung viel Aufwand (zum Beispiel müssen die Spieler viele Fragen beantworten), insbesondere wenn die Anzahl der Spieler groß ist.

Ist es möglich, die vorhandene Aufteilung des Kuchens auf Spieler zu verwenden, um mit minimalem zusätzlichen Aufwand eine neue Aufteilung des Kuchens auf Spieler zu erstellen (dh wesentlich weniger Aufwand als die Neuverteilung des Kuchens von Grund auf)?nn+1

Erel Segal-Halevi
quelle
2
Haben die ersten Spieler angefangen zu essen? Ist es fair, einem Spieler mehrere Stücke zu geben, oder muss jeder genau ein Stück bekommen? n
Raphael
@Raphael, ich bin speziell an einer fairen Aufteilung des Landes interessiert, daher können die Spieler nicht buchstäblich anfangen, ihren Anteil zu essen (sie können auf ihrem Anteil aufbauen, aber lassen Sie uns dieses Problem für den Moment ignorieren). Es ist vorzuziehen, jedem Spieler genau ein Stück zu geben. Dies ist jedoch anscheinend nicht fair, wenn nur eine einzige neue Person eintrifft. Wahrscheinlich sollte ich fragen, was passiert, wennn neue Spieler ankommen. In diesem Fall ist es (zumindest theoretisch) möglich, jede Aktie der ersten Spieler in 2 neue Aktien zu teilen . In jedem Fall ist jede Referenz willkommen. n
Erel Segal-Halevi
Warum nicht bei ungenutztem Land alles neu verteilen?
Raphael
2
Ich denke, Sie müssen klarstellen, was Ihr Ziel ist. Anzahl der Aktualisierungsschnitte minimieren? Die Gesamtlänge neuer Schnitte minimieren? Können wir Teile alten Spielern zuweisen oder können die einzigen jemals verlieren?
Raphael
Ah, jetzt verstehe ich, was Sie meinen: Sie meinen, dass einige der Spieler angefangen haben, ihren Anteil zu essen, und jetzt kommen neue Spieler, und wir möchten die Erinnerungen fair aufteilen, unter Berücksichtigung dessen, was jeder Spieler bereits gegessen hat. Obwohl dies an sich ein interessantes Problem ist, war meine Absicht anders - ich hoffe, dass meine jüngste Bearbeitung dies klarstellt.
Erel Segal-Halevi

Antworten:

6

Ich werde im Vorfeld sagen, dass ich Ihre Frage nicht gut beantworten kann (ich denke, Sie könnten vielleicht ein Forschungspapier daraus machen, wenn Sie könnten), aber ich denke, ich kann helfen, indem ich das Problem formal definiere und feststelle, wo es welche gibt der Schwierigkeiten liegen.

Hintergrund . Lassen Sie mich das Modell für das Kuchenschneiden klar formulieren. Wir wollen das Intervall teilen zwischen n - Player. Jeder Spieler i hat eine Bewertungsfunktion v i ( S ) über Teilmengen S des Kuchens. Wir nehmen an, dass diese Funktion ein Wahrscheinlichkeitsmaß ist; es ist nicht negativ und additiv (für disjunktes A ist B [ 0 , 1 ] , v i ( A B ) = v i ([0,1]nivi(S)SA,B[0,1] ) und v i ( [ 0 , 1 ] ) = 1 . Eine Lösung für dieses Problem ist einProtokolloder ein Algorithmus, der die Spieler abfragt und Teile des Intervalls zuweist. Beachten Sie, dass Spieler bei der Beantwortung von Fragen möglicherweise falsch berichten / lügen.vi(AB)=vi(A)+vi(B)vi([0,1])=1

Einige Papiere unterliegen spezifischeren Einschränkungen. Beispielsweise sind Bewertungsfunktionen stetig oder stückweise linear oder stückweise konstant.

Die den Spielern zugewiesenen Teile seien . Wir möchten oft die folgenden Eigenschaften eines Protokolls:{S1,,Sn}

  • Verhältnismäßigkeit : Jeder Spieler hat eine Strategie, die garantiert, dass er einen Wert von mindestens ( 1 / n ) v i ( [ 0 , 1 ] ) erhält . (Aus der Sicht von i erhält er 1 / n des Gesamtwerts des Kuchens.)i(1/n)vi([0,1])i1/n
  • Neidfreiheit : Jeder Spieler hat eine Strategie, die garantiert, dass für jeden anderen Spieler j ist . (Jeder Spieler zieht seine eigene Figur der Figur eines anderen Spielers vor.)vi(Si)vi(Sj)j

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

Es gibt auch "betriebliche" Eigenschaften, die wir uns wünschen könnten, wie das Schneiden in wenige Teile, die Polynomlaufzeit (oder überhaupt die Berechenbarkeit / Konstruierbarkeit - wir möchten nicht das Axiom der Wahl verwenden, um eine Teilmenge des Kuchens auszuwählen! ), und so weiter.


Spezifische Fragen zu stellen . Zwei Noten. Zuerst wird jede Antwort auf Ihre Frage das allgemeine Problem lösen: Geben Sie zunächst Spieler den ganzen Kuchen , lassen Sie dann die anderen Spieler online eintreffen und wenden Sie dieses Protokoll iterativ an. Wir sollten also erwarten, dass dieses Problem schwieriger ist als die Standardeinstellung für das Schneiden von Kuchen, auf die wir es anwenden.1

Zweitens können wir Ihr Problem jederzeit lösen, indem wir den gesamten Kuchen von allen zurücknehmen und ihn mit einem bekannten Algorithmus von Grund auf neu verteilen. Die Frage ist also nur, ob es einen etwas eleganteren Weg gibt, dies zu tun. Ich denke, ein guter Weg, dies zu quantifizieren, ist: "Wann erfordert die Umverteilung weniger Zeit oder weniger Schnitte als bei Null anzufangen; und / oder wann können die Spieler einen signifikanten Teil ihres aktuellen Slice behalten?"

  1. Angenommen, wir haben eine neidfreie Zuteilung für Spieler. Wie verteilen wir uns neu, um eine neidfreie Verteilung unter den n + 1 Spielern zu erreichen?nn+1

Ich vermute, das ist sehr schwierig. Der Grund ist, dass es bereits schwierig ist, eine neidfreie, effiziente Allokation zu finden. Soweit ich weiß, können bekannte Protokolle eine unbegrenzte Anzahl von Schnitten erfordern und sind sehr komplex. (Siehe Brams und Taylor, Ein Protokoll der Abteilung für neidfreie Kuchen , 1995.) Es gibt also möglicherweise nichts Besseres, als den gesamten Kuchen von allen zurückzunehmen und ihn mit Brams-Taylor an die Agenten weiterzugeben.n+1

  1. Angenommen, wir haben eine proportionale Zuordnung für ; Wie verteilen wir uns neu, um eine proportionale Zuordnung für n + 1 zu erhalten ?nn+1

Ich denke, das ist immer noch schwierig (obwohl machbarer). Stellen Sie sich den Fall vor, in dem jeder Spieler den Kuchen einheitlich bewertet und jeder Spieler eine Scheibe im Maßstab hat. Was auch immer der neue Spieler tut, muss unter allen neu gemischt werden. Hier ist ein weiterer schlechter Fall: Angenommen, Spieler 1 hat eine Bewertung von genau 1 / n für ihr Slice, bewertet aber das Slice von Spieler 2 mit ( n - 1 ) / n . Angenommen, Spieler 2 bewertet ihr eigenes Slice mit genau 1 / n , aber das Slice von Spieler 3 mit ( n)1/n11/n2(n1)/n21/n3 und so weiter, wobei Spieler n ihr eigenes Slice bei 1 / n unddas Slice vonSpieler 1 bei ( n - 1 ) / n bewertet . Jetzt kommt der neue Spieler. Egal was der neue Spieler will, Ihr Protokoll muss am Ende etwas von Spieler 2 zu Spieler 1 , von Spieler 3 zu Spieler 2 usw. neu mischen.(n1)/nn1/n1(n1)/n2132


Eine Referenz könnte Walsh, Online Cake Cutting , in Algorithmic Decision Theory 2011 (pdf-Link) sein. Ich denke jedoch, dass das Papier davon ausgeht, dass wir die Anzahl der ankommenden Agenten im Voraus kennen, und dass den Spielern genau dann ein Stück zugewiesen werden muss, wenn sie abreisen (was vor dem Ende des Protokolls liegt), sodass es für Ihr Problem wirklich nicht zutreffend ist.


Eine Möglichkeit zur Umverteilung einer proportionalen Zuweisung unter Wahrung der Verhältnismäßigkeit ist die folgende. Lassen Sie jeden der anwesenden Spieler sein zugewiesenes Stück Kuchen in n + 1 Stücke schneiden , die er selbst gleichermaßen schätzt. Spieler n + 1 wählt nun aus jedem Schnitt des n Spielers das beste Stück aus . Es ist leicht zu zeigen, dass die resultierende Zuordnung auch proportional ist.nn+1n+1n

usul
quelle
Ich bin mir nicht sicher, wie das allgemeine Problem (mit uneinheitlicher Präferenz) hier hilfreich ist. whoops ? Das Problem für unveränderliche Spieler (und vernünftige Formen) zu lösen ist einfach. Ich denke, wir müssen korrigieren, was "effizient" bzw. "gut" für Stecklinge / Zuordnungen und Änderungen davon bedeutet.
Raphael
1
@ Raphael - Soweit ich das beurteilen kann, wird in der Frage nach der Lösung des allgemeinen Problems gefragt. (Ich bin damit einverstanden, dass wir zusätzliche Struktur verwenden sollten, falls eine angegeben ist.)
Usul
Vielen Dank, Ihre Definition hat genau meine Absicht erfasst. Und die Referenz zum Online-Kuchenschneiden ist interessant und relevant.
Erel Segal-Halevi
6

C.rnπr2n(n+1)n+1

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

πr12=πr2n+1

um den Radius für seine Handlung zu erhalten. Zum zweiten lösen

πr12=πr2n+2πr22πr12=πr2n+2

n+iri=rin+kk

Dafür bekommen Sie n=6 und k=0,1,2,3::

example [ Quelle ]

Die gleiche Idee gilt für reguläre Polygone mit nSeiten. Wenn Sie ein Rechteck als Grundform annehmen, können Sie etwas Ähnliches tun, indem Sie das erste zuweisenn gleich große Spalten und die folgenden Spielerzeilen (beginnend an einer Seite).

Raphael
quelle
1
Es wäre interessant, den Bereich, der durch diese Methode neu zugewiesen wird, mit dem Bereich zu vergleichen, der neu zugewiesen wird, indem ein neues Stück (dh ein Sektor) Kuchen eingefügt und alle vorhandenen Teile im Uhrzeigersinn bewegt (und verkleinert) werden. Die Anzahl der von einem Umzug betroffenen Parteien (nicht nur ein Verlust) unterscheidet sich nur durch eine Konstante. Beachten Sie auch, dass Ringe nicht effektiver sind als Sektoren, aber der Wechsel von einer Methode zur anderen ermöglicht es, den durch die erste Methode zugewiesenen Bereich nicht zu verschieben.
frafl
@frafl Ich stimme zu. Können Sie die anderen Varianten in einer Antwort präsentieren? (Sie haben Recht: Es scheint keinen guten Grund für das Mischen der Methoden zu geben. Für mich war es durch das Kuchenproblem motiviert: Angenommen, der Kuchen wurde bereits geschnitten, was ist zu tun?)
Raphael
@frafl Beachten Sie, dass ein Vorteil des von mir verwendeten Schemas darin bestehen kann, dass die Teile des ersten n+1Spieler schrumpfen nur, bewegen sich aber nicht. Mit anderen Worten, dieses Schema macht weniger Schnitte (vollständig) überflüssig als das Einfügen neuer Kuchenstücksektoren.
Raphael
1
Dies ist eine schöne gemoetrische Lösung, die jedoch nur für einheitliche Kuchen und einheitliche Präferenzen relevant ist. Ich bezog mich auf das allgemeine Problem des Kuchenschneidens : en.wikipedia.org/wiki/Fair_division, bei dem davon ausgegangen wird, dass der Kuchen ungleichmäßig sein kann und verschiedene Spieler unterschiedliche Bewertungen für verschiedene Teile des Kuchens haben können.
Erel Segal-Halevi