Aufgabenteilung - Chore division

Aufgabenteilung ist ein faires Aufteilungsproblem , bei dem die aufgeteilte Ressource unerwünscht ist, damit jeder Teilnehmer so wenig wie möglich bekommen möchte. Es ist das Spiegelbild des fairen Kuchenschneideproblems , bei dem die geteilte Ressource wünschenswert ist, damit jeder Teilnehmer so viel wie möglich bekommen möchte. Beide Probleme haben heterogene Ressourcen, was bedeutet, dass die Ressourcen uneinheitlich sind. Bei der Kuchenteilung können Kuchen Rand-, Eck- und Mittelstücke sowie unterschiedliche Zuckergussmengen aufweisen. Bei der Aufgabenteilung hingegen gibt es verschiedene Aufgabentypen und unterschiedlich viel Zeit, die benötigt wird, um jede Aufgabe zu erledigen. In ähnlicher Weise gehen beide Probleme davon aus, dass die Ressourcen teilbar sind. Aufgaben können unendlich teilbar sein, weil die endliche Menge von Aufgaben nach Aufgaben oder nach Zeit unterteilt werden kann. Beispielsweise könnte eine Wäscheladung nach der Anzahl der Kleidungsstücke und/oder nach der Zeit, die zum Beladen der Maschine aufgewendet wird, aufgeteilt werden. Die Probleme unterscheiden sich jedoch in der Erwünschtheit der Ressourcen. Das Aufgabenteilungsproblem wurde 1978 von Martin Gardner eingeführt .

Die Aufteilung der Aufgaben wird oft als gerechte Aufteilung der Schlechten bezeichnet , im Gegensatz zu dem häufiger vorkommenden Problem, das als "gerechte Aufteilung von Gütern" bezeichnet wird (ein wirtschaftlicher Nachteil ist das Gegenteil eines wirtschaftlichen Gutes). Ein anderer Name ist Schmutzarbeitsproblem . Dieselbe Ressource kann je nach Situation entweder gut oder schlecht sein. Angenommen, die aufzuteilende Ressource ist der Hinterhof eines Hauses. In einer Erbteilungssituation würde dieser Hof als gut angesehen, da jeder Erbe so viel Land wie möglich haben möchte, es ist also ein Kuchenschneideproblem. Aber in einer Situation, in der Hausarbeiten wie das Rasenmähen aufgeteilt werden, würde dieser Garten als schlecht angesehen, da jedes Kind wahrscheinlich so wenig Land wie möglich zum Mähen haben möchte, also ist es ein Problem beim Schneiden.

Einige Ergebnisse des fairen Kuchenschneidens können leicht auf das Szenario des Hausarbeitsschneidens übertragen werden. So funktioniert beispielsweise das Divide-and-Choice- Verfahren bei beiden Problemen gleich gut: Einer der Partner teilt die Ressource in zwei in seinen Augen gleichwertige Teile auf, und der andere Partner wählt den in seinen Augen "besseren" Teil aus. Der einzige Unterschied besteht darin, dass "besser" beim Kuchenschneiden "größer" und beim Hausarbeitsschneiden "kleiner" bedeutet. Allerdings sind nicht alle Ergebnisse so einfach zu übersetzen. Weitere Details sind unten angegeben.

Proportionales Arbeiten

Die Definition der proportionalen Aufteilung in Chore Schneiden ist das Spiegelbild seiner Definition in Kuchenschneiden: jeder Partner soll ein Stück erhalten , die es wert ist, nach seiner eigenen persönlichen dis Nutzenfunktion, höchstens des Gesamtwerts (wo ist die Gesamtzahl der Partner):

Die meisten Protokolle für das proportionale Kuchenschneiden lassen sich leicht auf das Hausarbeitsschneiden übertragen. Zum Beispiel:

  • Um das letzte Verkleinerungsprotokoll zu verwenden: Bitten Sie einen Agenten, ein Stück genau für ihn zu schneiden . Wenn ein anderer Agent dieses Stück für zu klein hält, kann er es vergrößern, bis es ihm genau wert ist , und so weiter. Der "letzte Vergrößerer" erhält das Stück, das genau für ihn und zumindest für die anderen wert ist .
  • Um das Even-Paz-Protokoll zu verwenden : Bitten Sie jeden Agenten, die Halbwertlinie zu markieren, und stellen Sie sicher, dass alle Linien parallel sind. Schneiden Sie den Kuchen im Median der Linien auf, teilen Sie die Agenten in zwei Gruppen von Agenten auf und lassen Sie jede Hälfte das Stück rekursiv teilen, das NICHT seine Linie enthält.

Gleichmäßiges und exaktes Arbeiten

Verfahren zur gerechten Aufteilung und exakten Aufteilung funktionieren bei Kuchen und Hausarbeit gleichermaßen gut, da sie gleiche Werte garantieren. Ein Beispiel ist das Austin-Moving-Knife-Verfahren , das jedem Partner ein Stück garantiert, das er mit genau 1/ n der Gesamtsumme schätzt .

Neidfreie Hausarbeit

Die Definition von Neidfreiheit in Chore-Schneiden ist das Spiegelbild seiner Definition in Kuchenschneiden: jeder Partner soll ein Stück erhalten , die es wert ist, nach seiner eigenen persönlichen disutility Funktion, höchstens so viel wie jedes anderes Stück:

Für zwei Partner führt Divide and Choose zu einer neidfreien Hausarbeit. Bei drei oder mehr Partnern ist die Situation jedoch viel komplizierter. Die Hauptschwierigkeit liegt im Trimmen – das Trimmen eines Stückes, um es einem anderen Stück anzugleichen (wie zB im Selfridge-Conway-Protokoll ). Diese Aktion lässt sich nicht ohne weiteres auf das Szenario der Hausarbeit übertragen.

Oskuis diskretes Verfahren für drei Partner

Reza Oskui war der erste, der drei Partner für eine Hausarbeit vorschlug. Seine Arbeit wurde nie offiziell veröffentlicht; Es ist auf den Seiten 73–75 beschrieben. Es ähnelt dem Selfridge-Conway-Protokoll , ist jedoch komplizierter: Es erfordert 9 statt 5 Schnitte.

Unten heißen die Partner Alice, Bob und Carl.

Schritt eins. Alice schneidet die Arbeit in ihren Augen in drei gleiche Teile (dies ist auch der erste Schritt im Selfidge-conway-Protokoll). Bob und Carl spezifizieren ihr kleinstes Stück. Der einfache Fall ist, dass sie anderer Meinung sind, da wir dann jedem Partner ein kleinstes Stück geben können und wir sind fertig. Der schwierige Fall ist, dass sie sich einig sind. Nennen wir das Stück, das sowohl Bob als auch Carl als das kleinste ansehen, X1 und die anderen beiden Stücke X2 und X3.

Schritt zwei. Bitten Sie Bob und Carl, auf jedem der Stücke X2 und X3 zu markieren, wo das Stück geschnitten werden muss, um es gleich X1 zu machen. Wir betrachten mehrere Fälle.

Fall 1. Bobs Trimmung ist schwächer. Dh wenn Bob X2 auf X2' und X3 auf X3' trimmt, so dass sowohl X2' als auch X3' für ihn so klein wie X1 sind, dann hält Carl X1 immer noch für ein kleinstes Stück – schwach kleiner als X2' und X3'. Dann ist die folgende Teilteilung neidfrei:

  • Carl bekommt X1;
  • Alice bekommt das kleinere von X2' und X3' (beide sind für sie kleiner als X1);
  • Bob bekommt das Stück nicht von Alice genommen (beide sind für ihn gleich X1).

Jetzt müssen wir die Zutaten E2 und E3 teilen. Bei jedem Trimmen wird Folgendes durchgeführt:

  • Bob schneidet es in drei gleiche Stücke.
  • Der Agent wählt Teile in der Reihenfolge: Carl, Alice, Bob.

Carl ist nicht neidisch, da er sich zuerst entschieden hat; Bob ist nicht neidisch, seit er geschnitten hat; Alice ist nicht neidisch, da sie einen (negativen) Vorteil gegenüber Carl hatte: Im ersten Schritt nahm Carl X1, während Alice ein Stück nahm, das um max(E2,E3) kleiner als X1 ist, während Alice im letzten Schritt zwei Stücke, die höchstens wert sind (E2+E3)/2.

Fall 2. Carls Trimmungen sind schwächer. Dh wenn Carl X2 auf X2' und X3 auf X3' trimmt, so dass sowohl X2' als auch X3' für ihn so klein sind wie X1, dann denkt Bob, dass X1 immer noch ein kleinstes Stück ist – schwach kleiner als X2' und X3'. Dann verfahren wir wie in Fall 1, wobei die Rollen von Bob und Carl getauscht werden.

Fall 3. Bobs Trimmung ist in X2 schwächer und Carls Trimmung in X3 schwächer. Dh, wenn Bob X2 auf X2' trimmt, was für ihn gleich X1 ist, und Carl X3 auf X3' trimmt, was für ihn gleich X1 ist, dann:

  • Für Carl: X2' >= X1 = X3'
  • Für Bob: X3' >= X1 = X2'

Dann ist die folgende Teilteilung neidfrei:

  • Alice bekommt das kleinere von X2' und X3' (beide sind für sie kleiner als X1);
  • Bob bekommt entweder X2' (wenn es nicht von Alice genommen wurde) oder X1 (sonst);
  • Carl bekommt entweder X3' (wenn es nicht von Alice genommen wurde) oder X1 (sonst).

Die Zutaten E2 und E3 sind ähnlich wie bei Fall 1 aufgeteilt.

Oskui zeigte auch, wie man die folgenden Moving-Messer-Verfahren vom Kuchenschneiden zum Hausarbeitsschneiden umwandelt:

Kontinuierliche Verfahren von Peterson und Su für drei und vier Partner

Peterson und Su schlugen für drei Partner ein anderes Vorgehen vor. Es ist einfacher und symmetrischer als das Verfahren von Oskui, aber es ist nicht diskret, da es auf einem Verfahren mit beweglichem Messer beruht. Ihre Kernidee besteht darin, die Aufgaben in sechs Teile zu unterteilen und dann jedem Partner die beiden Teile zu geben, die ihrer Meinung nach mindestens so klein sind wie die Teile, die die anderen Spieler erhalten.

Schritt eins. Teilen Sie die Aufgaben mit einer beliebigen neidfreien Kuchenschneidemethode in 3 Teile und weisen Sie jedes Stück dem Spieler zu, der es am größten findet.

Schritt zwei.

  • Unter Verwendung des Austin-Moving-Knife-Verfahrens teilen Sie Stück 1 in zwei Scheiben, die Partner 1 und 2 als gleich betrachten. Lassen Sie Partner 3 die Scheibe wählen, die in seinen Augen kleiner ist, und geben Sie die andere Scheibe an Partner 2.
  • Auf ähnliche Weise teilen Sie Teil 2 in zwei Scheiben, die Partner 2 und 3 als gleich betrachten, lassen Sie Partner 1 die kleinste Scheibe auswählen und geben Sie die andere Scheibe an Partner 3.
  • Auf ähnliche Weise teilen Sie Stück 3 in zwei Scheiben, die Partner 3 und 1 als gleich betrachten, lassen Sie Partner 2 die kleinste Scheibe auswählen und geben Sie die andere Scheibe an Partner 1.

Analyse. Partner 1 hält zwei Scheiben: eine von Teil 2 und eine von Teil 3. In den Augen von Partner 1 ist die Scheibe von Teil 2 kleiner als ihre an Partner 3 gegebene Scheibe und die Scheibe von Teil 3 ist kleiner als ihre gegebene Scheibe zu Partner 2. Außerdem sind diese beiden Scheiben kleiner als die Scheiben von Teil 1, da Teil 1 größer ist als sowohl Teil 2 als auch Teil 3 (nach Schritt Eins). Daher ist Partner 1 der Meinung, dass sein Anteil (schwach) kleiner ist als jeder der beiden anderen Anteile. Für Partner 2 und 3 gelten die gleichen Überlegungen. Daher ist die Aufteilung neidlos.

Peterson und Su erweitern ihr kontinuierliches Verfahren auf vier Partner.

Das diskrete Verfahren von Peterson und Su für eine beliebige Anzahl von Partnern

Die Existenz eines diskreten Verfahrens für fünf oder mehr Partner blieb offen, bis 2009 Peterson und Su ein Verfahren für n Partner veröffentlichten. Es ist analog zum Brams-Taylor-Verfahren und verwendet die gleiche Idee des unwiderruflichen Vorteils . Anstatt zu trimmen, verwenden sie das Hinzufügen aus Reserve .

Das diskrete und beschränkte Verfahren von Dehghani et al. für eine beliebige Anzahl von Partnern

Peterson und Su gaben ein Verfahren mit beweglichem Messer für eine 4-Personen-Aufgabenteilung. Dehghaniet al. lieferte das erste diskrete und begrenzte neidfreie Protokoll für die Aufteilung von Aufgaben auf eine beliebige Anzahl von Agenten.

Verfahren für verbundene Teile

Die folgenden Verfahren können angepasst werden, um einen schlechten Kuchen mit getrennten Stücken zu teilen:

Fairnesspreis

Heydrich und van Stee berechnen den Preis der Fairness in der Hausarbeit, wenn die Teile verbunden werden müssen.

Anwendungen

Es kann möglich sein, Hausarbeitsteilungsverfahren zu verwenden, um die Arbeit und die Kosten der Reduzierung des Klimawandels auf die Nationen aufzuteilen. Es treten Probleme mit der Moral und der Zusammenarbeit zwischen den Nationen auf. Durch die Verwendung von Hausarbeitsteilungsverfahren wird jedoch die Notwendigkeit einer supranationalen Behörde zur Aufteilung und Überwachung der Arbeit dieser Nationen verringert.

Eine andere Verwendung für die Hausarbeitsteilung wäre das Problem der Mietharmonie .

Verweise

Siehe auch