Logo

Adjusted Winner (AW) ist ein Algorithmus zur neidfreien Güterverteilung . Gegeben zwei Parteien und einige diskrete Güter, gibt er eine Aufteilung der Güter zwischen den beiden Parteien zurück, die wie folgt aussieht:

  1. Ohne Neid : Jede Partei ist der Ansicht, dass ihr Anteil an den Gütern genauso gut oder besser ist als der des Gegners;
  2. Gerecht : Der „relative Glückszustand“ beider Parteien, der sich aus ihren Anteilen ergibt, ist gleich.
  3. Pareto-optimal : Keine andere Aufteilung ist für eine Partei besser und gleichzeitig mindestens genauso gut für die andere Partei; und
  4. Beinhaltet die Aufteilung von höchstens einem Gut zwischen den Parteien.

Es ist das einzige Verfahren, das alle vier Eigenschaften gleichzeitig erfüllen kann. [ 1 ] Trotzdem gibt es keine Berichte darüber, dass der Algorithmus tatsächlich zur Beilegung von Streitigkeiten eingesetzt wurde.

Das Verfahren wurde von Steven Brams und Alan D. Taylor entwickelt und in ihrem Buch über faire Aufteilung [ 2 ] : 65–94 sowie später in einem eigenständigen Buch veröffentlicht. [ 3 ] : 69–88. Das Verfahren „Adjusted Winning“ war zuvor in den Vereinigten Staaten patentiert, der Patentschutz erlosch jedoch 2016. [ 4 ]

Algorithmus

Jede Partei erhält die Warenliste und eine gleiche, festgelegte Punktzahl, die sie unter den Waren verteilen kann. Anschließend ordnen sie jeder Ware einen Wert zu und übermitteln ihre (versiegelte) Gebotsliste einem Schiedsrichter, der die Waren jeweils dem Höchstbietenden zuweist.

Ist der Gesamtwert der Güter einer Partei höher als der der anderen, ordnet der Algorithmus die Güter der Partei mit dem höheren Gesamtwert anhand des Verhältnisses aufsteigend und beginnt, sie von der Partei mit dem höheren Gesamtwert zur Partei mit dem niedrigeren Gesamtwert zu übertragen, bis deren Werte nahezu gleich sind (jede weitere Übertragung von Gütern würde dazu führen, dass die Partei mit dem niedrigeren Gesamtwert nun einen höheren Gesamtwert als die andere aufweist). Das nächste Gut wird dann zwischen den Parteien so aufgeteilt, dass ihre Werte übereinstimmen. [ 3 ] : 71–74

Nehmen wir beispielsweise an, zwei Parteien haben folgende Wertvorstellungen für vier Güter:

  • Alice: 86, 75, 30, 9
  • Bob: 19, 81, 60, 40

Die Güter werden zunächst so aufgeteilt, dass Alice Gut 1 erhält, während Bob die Güter 2, 3 und 4 erhält. Zu diesem Zeitpunkt beträgt Alices Gesamtwert ihrer Güter 86, während Bobs Wert 81 + 60 + 40 = 181 beträgt. Daher werden Bobs Güter anschließend nach dem Verhältnis geordnet , was ergibt

  • [Gut 2 = ], [Gut 3 = ], [Gut 4 = ].

Würde Gut 2 von Bob zu Alice übertragen, hätte Alice einen höheren Wert als Bob (161 gegenüber 100), daher findet kein Gütertransfer statt. Stattdessen wird Gut 2 zwischen Alice und Bob aufgeteilt: Alice erhält den Anteil (ca. 60,9 %), Bob den Anteil (ca. 39,1 %). Ihre Werte sind nun gleich .

Simulationen

Es gibt keine Fälle, in denen Adjusted Winner zur Beilegung realer Streitigkeiten eingesetzt wurde. Allerdings haben einige Studien simuliert, wie bestimmte Streitigkeiten ausgegangen wären, wenn der Algorithmus verwendet worden wäre.

Einschränkungen

Der Adjusted Winner (AW) ist kein wahrheitsgetreuer Mechanismus : Eine Partei kann sich Vorteile verschaffen, indem sie ihren Gegner ausspioniert und dessen Berichte manipuliert, um einen größeren Anteil zu erhalten. [ 2 ] Der Adjusted Winner hingegen weist stets ein annäherndes Nash-Gleichgewicht auf und bei einem informierten Tie-Breaker sogar ein reines Nash-Gleichgewicht. [ 1 ]

Der patentierte Algorithmus setzt voraus, dass die Parteien additive Nutzenfunktionen besitzen: Der Wert ihrer Güter entspricht der Summe der Werte der einzelnen Güter. Er kann beispielsweise Mehrfachvorkommen eines Gutes mit abnehmendem Grenznutzen nicht berücksichtigen .

Der Algorithmus ist zudem nur für zwei Parteien ausgelegt; bei drei oder mehr Parteien gibt es möglicherweise keine Allokation, die gleichzeitig neidfrei, gerecht und Pareto-optimal ist. Dies lässt sich anhand des folgenden Beispiels von JHReijnierse [ 2 ] (S. 82–83) mit drei Parteien und deren Bewertungen zeigen:

  • Alice: 40, 50, 10
  • Bob: 30, 40, 30
  • Carl: 30, 30, 40

Die einzig Pareto-optimale und gerechte Aufteilung wäre diejenige, bei der Alice Gut 1, Bob Gut 2 und Carl Gut 3 erhalten; diese Aufteilung wäre jedoch nicht neidfrei, da Alice Bob beneiden würde. [ 8 ]

Zwei dieser drei Eigenschaften können gleichzeitig erfüllt sein:

Darüber hinaus ist es möglich, eine Aufteilung zu finden, die Pareto-optimal/neidfrei oder Pareto-optimal/gerecht ist und gleichzeitig die Anzahl der Objekte minimiert, die zwischen zwei oder mehr Parteien aufgeteilt werden müssen. Dies wird üblicherweise als Verallgemeinerung des Adjusted-Winner-Verfahrens auf drei oder mehr Parteien betrachtet. [ 11 ]

Der angepasste Gewinner ist für Akteure mit positiven Bewertungen der Güter konzipiert. Er kann jedoch auch auf Parteien mit gemischten (positiven und negativen) Bewertungen verallgemeinert werden. [ 12 ]

Das Brams-Taylor-Verfahren wurde von denselben Autoren entwickelt, dient aber der neidfreien Aufteilung von Gütern : Es verarbeitet heterogene Ressourcen („Kuchen“), deren Aufteilung schwieriger ist als die homogenen Güter des Adjusted Winning-Verfahrens. Daher garantiert BT lediglich Neidfreiheit, keine weiteren Eigenschaften.

Der Artikel über Fair-Division-Experimente beschreibt einige Laborversuche, in denen AW mit verwandten Verfahren verglichen wird.

Referenzen

  1. ^ a b Aziz, Haris; Brânzei, Simina; Filos-Ratsikas, Aris; Søren Kristoffer Stiil, Søren (2015). „The Adjusted Winner Procedure: Characterizations and Equilibria“ . Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence . S.  454–460 . arXiv : 1503.06665 . Bibcode : 2015arXiv150306665A . Archiviert vom Original am 23. Mai 2018.
  2. ^ a b c d Brams, Steven J.; Taylor, Alan D. (1996). Fair division: from cake-cutting to dispute resolution . Cambridge University Press. ISBN 0-521-55644-9Die
  3. ^ a b Steven J. Brams und Alan D. Taylr (2000). Die Win-Win-Lösung: Gerechte Anteile für alle garantieren . Norton. ISBN 978-0393320817Die
  4. ^ US-Patent 5,983,205 , Computergestütztes Verfahren zur gerechten Aufteilung des Eigentums an Gütern .
  5. ^ Brams, Steven J.; Togman, Jeffrey M. (1996). „Camp David: War das Abkommen fair?“. Conflict Management and Peace Science . 15 (1): 99–112 . doi : 10.1177/073889429601500105 . ISSN 0738-8942 . S2CID 154854128 .  
  6. ^ Massoud, Tansa George (1. Juni 2000). „Fair Division, Adjusted Winner Procedure (AW) and the Israeli-Palestinian Conflict“. Journal of Conflict Resolution . 44 (3): 333–358 . doi : 10.1177/0022002700044003003 . ISSN 0022-0027 . S2CID 154593488 .  
  7. ^ Denoon, DBH; Brams, SJ (1997-02-01). „Faire Aufteilung: Ein neuer Ansatz im Spratly-Inselstreit“. International Negotiation . 2 (2): 303–329 . doi : 10.1163/15718069720847997 . ISSN 1571-8069 . 
  8. ^ Segal-Halevi, Erel (09.07.2018). „Wettbewerbsgleichgewicht für nahezu alle Einkommen“ . Proceedings der 17. Internationalen Konferenz über Autonome Agenten und Multiagentensysteme . AAMAS '18. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 1267–1275 .
  9. ^ Willson, Stephen J. (1995). „Fair Division using Linear Programming“ (PDF) . Iowa State University (unveröffentlichtes Manuskript) .
  10. ^ Samuel Bismuth; Ivan Bliznets; Erel Segal-Halevi (2019). „Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations“. arXiv : 1912.00459 [ cs.GT ].
  11. ^ Sandomirskiy, Fedor; Segal-Halevi, Erel (01.05.2022). „Effiziente faire Aufteilung mit minimaler Gewinnbeteiligung“ . Operations Research . 70 (3): 1762–1782 . arXiv : 1908.01669 . doi : 10.1287/opre.2022.2279 . ISSN 0030-364X . S2CID 247922344 .  
  12. ^ Aziz, Haris; Caragiannis, Ioannis; Igarashi, Ayumi; Walsh, Toby (1. August 2019). „Faire Verteilung unteilbarer Güter und Aufgaben“. Tagungsband der 28. Internationalen Gemeinsamen Konferenz über Künstliche Intelligenz . Kalifornien: International Joint Conferences on Artificial Intelligence Organization. S.  53–59 . doi : 10.24963/ijcai.2019/8 . ISBN 978-0-9992411-4-1. S2CID  197468732 .