Quelltext der Seite Multi-Agenten-Ressourcen-Allokation

Bei der '''Multi-Agenten-Ressourcen-Allokation''' oder '''Ressourcenallokation in Multi-Agenten-Systemen''' (engl. Multiagent Resource Allocation (MARA)) geht es um das Aufteilen von [[Ressource]]n auf miteinander in Konkurrenz stehende [[Homo oeconomicus|Agenten]].

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

Die Multi-Agenten-Ressourcen-Allokation ist ein Teilgebiet der noch jungen Disziplin Computational Social Choice, die sich primär mit den [[Algorithmus|algorithmischen]] Aspekten der [[Spieltheorie|Spiel]]- und [[Sozialwahltheorie|Social-Choice]]-Theorie beschäftigt.

== Allokationsprozeduren ==
Allokationsprozeduren können in zentralisiert und verteilt unterschieden werden. Bei einer verteilten Allokationsprozedur entsteht die [[Ressourcenallokation|Allokationen]] aus einer Reihe von lokalen Verhandlungsschritten.<ref name="Cheva" /> Ein Beispiel für eine verteilte Allokationsprozedur ist das [[Gerechte Aufteilung|Cake-Cutting-Protokoll]].

Bei einer zentralisierten Allokationsprozedur findet die Aufteilung der Güter über eine zentrale Instanz statt, wie z.&nbsp;B. dem Auktionator bei einer [[Auktionstheorie|Auktion]]. Dabei kann der Auktionator die Aufteilung der Ressourcen aufgrund der [[Präferenzrelation|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 [[Steven Brams]] und [[Alan D. 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, dass 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-Optimum|Pareto-optimal]], gleichverteilt und neidfrei ist.

=== Einzelauktionen ===
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 zulassen.

Von Interesse sind z.&nbsp;B.:

* Englische Auktion
* [[Vickrey-Auktion]]
* [[Holländische Auktion]]
* [[Amerikanische Versteigerung]]

Die Gewinner-Ermittlung ist dabei in den meisten Fällen sehr einfach: es muss nur das höchste Gebot ermittelt werden; bei einem Gleichstand ist u. U. eine Vorzugsregel anzuwenden.

== Aufteilung von Bündeln von Gütern ==
Im Gegensatz zu den Einzelauktionen werden nun ganze Bündel von Gütern angeboten.

=== Multi-Agenten-Ressourcen-Allokation Ausgangslage ===
Ein ''Multi-Agenten-Ressourcen-Allokation Ausgangslage''<ref name="Cheva" /> bezeichnet ein Tripel <math>\textstyle(\mathcal A,\mathcal R,\mathcal U)</math>, wobei

<math>\textstyle \mathcal A = \{1,2,...,n\} </math> eine Menge von Agenten ist,

<math>\textstyle \mathcal R = \{r_1,r_2,...,r_m\}</math> eine Menge von Ressourcen ist und

<math>\textstyle \mathcal U = \{u_1,u_2,...,u_n\} </math> eine Menge von Nutzfunktionen ist, <math>\textstyle u_i</math> beschreibt dabei die Nutzenfunktion des i-ten Agenten, mit <math>\textstyle u_i : 2^ \mathcal R \rightarrow \Q</math>.

=== Bündelform ===
Bei der Bündelform wird jedes von null verschiedene Bündel <math>\textstyle B \subseteq \mathcal R </math> in Form eines Tupels <math>\textstyle (B,u_i(B)) </math> aufgezählt. Es kann exponentiell viele Tupel geben.

=== k-additive Form ===
Bei der k-additiven Form kann es möglich sein, durch Ausnutzungen von Regelmäßigkeiten eine kompaktere Darstellung zu erreichen.

<math>\textstyle u_i(B) = \sum_{T \subseteq R} a_i^T</math>

T ist ein Bündel, es gilt <math>\textstyle \left\|T\right\| \le k</math>, d.&nbsp;h. die maximale Bündelgröße ist durch ''k'' nach oben hin beschränkt.

Die Ausdrucksstärke der Bündelform und der k-additiven Form sind aber nicht vergleichbar; für beide kann gezeigt werden, dass es jeweils für die eine Form in Extremfällen exponentiell viele Tupel oder Koeffizienten erfordert, während die andere Form nur <math>\textstyle \left\|R\right\|</math> viele benötigt (siehe auch<ref name="Cheva2" />).

== Soziale Wohlfahrt ==

{{Hauptartikel|Wohlfahrtsfunktion}}
{{Hauptartikel|Bergson-Samuelson-Wohlfahrtsfunktion}}
Die soziale [[Wohlfahrtsökonomik|Wohlfahrt]] (engl.: social welfare) stellt ein Effizienzmaß dar.
=== Utilitaristische SWF ===
Die utilitaristische soziale Wohlfahrt bezeichnet den aufsummierten Nutzen aller Agenten. Sie ist z.&nbsp;B. von Interesse, um den durchschnittlichen Nutzen der Agenten festzustellen oder den maximalen Ertrag des Auktionators zu bestimmen.

<math>\textstyle sw_u(X) = \sum_{a_j \in A} u_j(X)</math>

=== Egalitaristisch ===
Bei der egalitaristischen sozialen Wohlfahrt wird der Nutzen des Agenten bestimmt, der am schlechtesten "weggekommen" ist. Diese Art der Bestimmung ist z.&nbsp;B. bei dem Verteilen humanitärer Güter interessant.

<math>\textstyle sw_e(X) = \operatorname{min}\{u_j(X) | a_j \in A\} </math>

=== Nash-SWF ===
Das Nash Produkt stellt einen Kompromiss aus den beiden vorangegangenen Wohlfahrten dar. Der Wert ist maximal, wenn alle Agenten den gleichen Nutzen haben. Sinnvoll sind nur positive Nutzen.

<math>\textstyle sw_N(X) = \prod_{a_j \in A} u_j(X) </math>

== Einzelnachweise ==
<references>
<ref name="Cheva">
Y. Chevaleyre et al. ''Issues in Multiagent Resource Allocation.'' In: ''Informatica.'' Issue 1, Vol. 30 2006
</ref>
<ref name="Cheva2">
Y. Chevaleyre et al. ''Multiagent resource allocation in k-additive domains: preference representation and complexity'' [[doi:10.1007/s10479-008-0335-0]], 2008
</ref>
</references>
== 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-3-8274-2570-6
* Steven J. Brams and Alan D. Taylor (1996). ''Fair Division – From cake-cutting to dispute resolution''. Cambridge University Press. ISBN 0-521-55390-3

[[Kategorie:Volkswirtschaftslehre]]
[[Kategorie:Informatik]]
[[Kategorie:Spieltheorie]]