Multi-Agenten-Ressourcen-Allokation

Bei der Multiagent Resource Allocation (MARA) geht es um das Aufteilen von Ressourcen auf miteinander in Konkurrenz stehende Agenten.

Dieser Artikel folgt der Annahme, wie in der Literatur üblich, das die Ressourcen unteilbar sind. D.h. Ressourcen sind "indivisible", können also nicht in kleinere Teilstücke zerlegt werden und zu dem sind sie "nonshareable", können also nicht gemeinsam genutzt werden.

Multiagent Resource Allocation ist ein Teilgebiet der noch jungen Disziplin Computational Social Choice, die sich primär mit den algorithmischen Aspekten der Spiel- und Social-Choice-Theorie beschäftigt.

Allokationsprozeduren

Allokationsprozeduren können in zentralisiert und verteilt unterschieden werden. Bei einer verteilten Allokationsprozedur entsteht die Allokationen aus einer Reihe von lokalen Verhandlungsschritten. Ein Beispiel für eine verteilte Allokationsprozedur ist das Cake-Cutting-Protokoll.

Bei einer zentralisierten Allokationsprozedur findet die Aufteilung der Güter über eine zentrale Instanz statt, wie z.B. dem Auktionator bei einer Auktion. Dabei kann der Auktionator die Aufteilung der Ressourcen aufgrund der Präferenzen der Agenten oder ihrer Gebote durchführen.

Aufteilung einzelner Güter

Scheidungsformel

Eine Möglichkeit Güter aufzuteilen ist die sogenannte Scheidungsformel (engl. Adjusted Winner Procedure) von Brams und Taylor. Dabei werden die aufzuteilenden Güter von den betroffenen Parteien nach ihrem subjektiven Empfinden bewertet (es können insgesamt 100 Punkte vergeben werden) und aufgrund dieser Wertung verteilt. Bei einem Ungleichgewicht muss der Begünstigte solange Objekte abtreten, bis ein Ausgleich eintritt. Die Reihenfolge der abzutretenden Güter ergibt sich durch die ins Verhältnis gesetzten Bewertungen der einzelnen Güter, diese werden aufsteigend, mit der Bedingung, dass das Verhältnis mindestens 1 ergibt, sortiert. Das Bedeutet, das zunächst die Objekte betrachtet werden, bei denen die Gewinn/Verlust-Ratio am Kleinsten ist, also die Parteien am Ehesten übereinstimmen.

Die Vorteile der Scheidungsformel sind, dass das erzielte Ergebnis pareto-optimal, gleichverteilt und neidfrei ist.

Einzelauktionen (engl. single-item auctions)

Bei Einzelauktionen werden die Objekte einzeln an die Bieter versteigert. Ziel einer Auktion aus Sicht des Auktionators ist es einen möglichst hohen Erlös für das Objekt zu erzielen, wohingegen der Agent (Bieter) einen möglichst geringen Preis bezahlen will. Bieter stehen miteinander in Konkurrenz. Es gibt eine Reihe von verschiedenen Auktionen, die aufgrund ihrer Beschaffenheit verschiedene Strategien für die Bieter zu lassen.

Aufteilung von Bündeln von Gütern

Resource Allocation Setting

Ein Resource Allocation Setting bezeichnet ein Tripel $({\mathcal {A}},{\mathcal {R}},{\mathcal {U}})$, wobei

${\mathcal {A}}=\{1,2,...,n\}$ eine Menge von Agenten ist,

${\mathcal {R}}=\{r_{1},r_{2},...,r_{m}\}$ eine Menge von Ressourcen ist und

${\mathcal {U}}=\{u_{1},u_{2},...,u_{n}\}$ eine Menge von Nutzfunktionen ist, $u_{i}$ beschreibt dabei die Nutzenfunktion des i-ten Agenten, mit $u_{i}:2^{\mathcal {R}}\rightarrow \mathbb {Q}$.

Eine Allokation einer Ressource ist eine Abbildung von ${\mathcal {P}}:{\mathcal {A}}\rightarrow 2^{\mathcal {R}}$.

Literatur

• Jörg Rothe, Dorothea Baumeister, Claudia Lindner, Irene Rothe. Einführung in Computational Social Choice: Individuelle Strategien und kollektive Entscheidungen beim Spielen, Wählen und Teilen. Spektrum Akademischer Verlag. ISBN 978-3827425706
• Steven J. Brams and Alan D. Taylor (1996). Fair Division - From cake-cutting to dispute resolution. Cambridge University Press. ISBN 0-521-55390-3