Kooperative Spiele:Beispiel: UNO

Aus Wikiludia
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Begriffserklärung

Der Shapley-Wert

Einleitung

Für allgemeine n-Personen-Spiele besteht eine Lösung im allgemeinen aus mehreren Verteilungen. Durch diesen Lösungsbegriff wird also nicht eine bestimmte Verteilung des Spieles ausgezeichnet, deren Komponenten sich dann als Wert des Spielers für die einzelnen Spieler ansprechen ließen. Es fragt sich nun, ob man nicht durch andere intuitiv einleuchtende Forderungen eine bestimmte Verteilung des Spieles aussondern kann, deren Komponenten als vernünftige a-priori-Bewertung des Spieles für die einzelnen Spieler angesehen werden können. Ein besonders einfaches System von solchen Forderungen hat Shapley angegeben. Hierbei werden Spiele nur durch ihre charakteristischen Funktionen gegeben. Sei also  G_n\!\, die Gesamtheit der auf R={1, \dots, n} erklärten charakteristischen Funktionen, also die Spielgesamtheit.

Definition

Eine Wertfunktion \Phi\!\, ist eine auf G_n\!\, erklärte Funktion, die jedem v \in G_n\!\, eine Verteilung \Phi(v)=(\Phi_1(v),\dots, \Phi_n(v))\!\, des Spieles v\!\, zuordnet, so dass die folgenden Forderungen erfüllt sind:

1. Für jede Permutation \pi : R \rightarrow R\!\, und jedes v \in G_n\!\, mit v(\pi(S))=v(S)\!\, für alle S \subseteq R\!\, gilt \Phi_{\pi(i)}=\Phi_{i}(v)\!\, für i=1, \dots, n\!\,.

2. Gilt für ein i \in R\!\, die Beziehung v(S)=v(S-{i})+v({i})\!\, für alle S \subseteq R\!\, mit i \in S\!\,, so ist \Phi_i(v)=v({i})\!\,.

3. Für irgendwelche v, w \in G_n\!\, gilt\Phi(v+w)=Phi(v)+\Phi(w)\!\,, d.h. \Phi_i(v+w)= \Phi_i(v)+\Phi_i(w)\!\, für i=1, \dots, n\!\,.

Forderung 1 verlangt, dass für zwei Spieler i\!\, und j\!\,, die vermöge der Spielregeln des Spieles v\!\, nicht unterschieden sind, die Beträge \Phi_i(v)\!\, und \Phi_j(v)\!\, gleich sind. Für jeden Spieler i\!\, ist für alle S \subseteq R\!\, mit i \in S\!\, sicher v(S)\geq v(S-{i})+v({i})\!\,. Gilt also für einen Spieler i\!\, in diesen Ungleichungen immer das Gleichheitszeichen, so ist der Spieler i\!\, sozusagen in jeder Koalition unwesentlich. Er trägt zu keiner Koalition mehr als seinen Minimalwert v({i})\!\, bei. Man bezeichnet ihn dann als 'Strohmann'. Nach Forderung 2 erhält jeder Strohmann i\!\, im Spiel v\!\, nur den Minimalwert v({i})\!\,. Schließlich kann in Forderung 3 die Summe der zwei charakteristischen Funktionen v\!\, und w\!\, aufgefasst werden als charakteristische Funktion des Spieles, das entsteht, indem man die völlig unabhängig voneinander gespielten Spiele v\!\, und w\!\, als ein einziges Spiel auffassen. Es ist natürlich, zu verlangen, dass dann die Beträge für alle Spieler sich ebenso addieren. Man beachte dazu noch , dass die Summe v+w\!\, zweier charakteristischen Funktionen aus G_n\!\, wieder zu G_n\!\, gehört und dass die Vektorsumme einer Verteilung von v\!\, und einer Verteilung von w\!\, eine Verteilung von v+w\!\,ist.

Gewichtetes Majoritätsspiel

Einleitung

Ein solches Spiel beschreibt zum Beispiel den Mechanismus, nach dem die Aktienbesitzer ihre Gesellschaft kontrollieren. Die Spieler besitzen gewissen Gewichte (ihre Aktienanteile) und eine Koalition gewinnt (bringt einen bestimmten Antrag durch), wenn sie mehr als einen vorgeschriebenen Bruchteil (üblicherweise die Hälfte) des Gesamtaktienwertes besitzt.

Definition

Das gewichtete Majoritätsspiel [L; w_1, \dots, w_n]\!\, (L, w_1, \dots, w_n reell, nicht-negativ, L > \frac{1}{2}\sum_{i=1}^n w_i \!\,) ist das n-Personen-Spiel, dessen charakteristische Funktion v\!\, durch

v(S)=\begin{cases} 1,  & \mbox{falls} \sum_{i \in S}w_i \geq L \\ 0, & \mbox {falls} \sum_{i \in S}w_i < L\end{cases} gegeben ist.

Die Gewichte w_1, \dots, w_n\!\, der einzelnen Spieler im Spiel [L; w_1, \dots, w_n]\!\, geben nur ein sehr rohes Bild von der relativen Stärke der Positionen der einzelnen Spieler in diesem Spiel. Sie sind zum Beispiel nicht mal eindeutig bestimmt. [10; 10, 9]\!\,und [10; 15, 0]\!\, dasselbe Spiel, nämlich v(\emptyset)=0, v({1})=1, v({2})=0, v({1,2})=1\!\,.

Dagegen bietet sich der Shapley-Wert als eine vernünftige Bewertung der Stärken der Spieler in einem solchen Spiel an.



Beispiel: UNO

Fünfzehn Nationen gehören zum UNO-Sicherheitsrat, fünf mit einem permanenten Sitz und zehn auf rotierender Basis. Bei wichtigen Entscheidungen wie Sanktionen und Resolutionen sind neun Zustimmungen nötig, einschließlich aller ständigen Mitglieder. Falls eines der ständigen Mitglieder gegen eine Resolution stimmt (Veto), gilt sie als nicht angenommen.

Dieses Veto-Recht gibt den ständigen Mitgliedern einen ungleich größeren Einfluß. Im folgenden soll diese Machtdifferenz quanitisiert werden.

Da ein Antrag entweder angenommen oder abgelehnt wird, weist man allen gewinnenden Koalitionen V(S) = 1 und allen verlierenden Koalitionen V(S) = 0 zu, wobei im ersten Fall S mindestens die fünf ständigen Mitglieder und vier nichtständige Mitglieder beinhalten muß. Solche Spiele, in denen die charakteristische Funktion entweder 0 oder 1 ist, heißen einfache Spiele.

Eine interessante Klasse einfacher Spiele ist die Klasse der gewichteten Majoritätsspiele.

Ein solches Spiel F = (L,{wi}) mit nichtnegativen reellen Zahlen wi für alle i \in M ist ein kooperatives n-Personenspiel mit

L > \frac{1}{2}\sum_{i}^n w_i

und der charakteristischen Funktion V(S) = 1 falls \sum_{i\in S} w_i \geq L

bzw. V(S) = 0, falls \sum_{i\in S} w_i <
L

für alle S \subset M. wi ist die Macht von Spieler i (Anzahl der Stimmen, Aktien usw.), L ist die benötigte Mehrheit.


Die Abstimmungsregeln des Sicherheitsrates können als ein gewichtes Majoritätsspiel modelliert werden, indem jedem ständigen Mitglied 7 Stimmen, jedem einfachen Mitglied 1 Stimme zugestanden wird. Die benötigte Mehrheit ist 39 Stimmen, da es insgesamt 5 mal 7 plus 10 Stimmen gibt und alle ständigen Mitglieder zustimmen müssen. Ohne die Stimmen der ständigen Mitglieder kann Majorität nicht erreicht werden:

F = [39;7,7,7,7,7,1,1,1,1,1,1,1,1,1,1]

Bedeutet das, daß die ständigen Mitglieder einen sieben mal so großen Einfluß haben? Berechnen wir den Shapley-Wert.

In einem einfachen Spiel muß lediglich die Wahrscheinlichkeit berechnet werden, daß ein Spieler über den Sieg für einen Antrag entscheidet. Im Falle des UN-Sicherheitsrates ist dies die Wahrscheinlichkeit, daß ein nicht ständiges Mitglied als 9. einer bestehenden Koalition beitritt, die bereits die fünf permanenten Mitglieder umfaßt:

 p_i =  {8 \choose 3}\cdot \frac{5}{15}\cdot
\frac{4}{14}\cdot \frac{3}{13} \cdot \frac{2}{12}\cdot
\frac{1}{11}\cdot \frac{9}{10}\cdot \frac{8}{9}\cdot
\frac{7}{8}\cdot\frac{1}{7}

Sie beträgt nur p_i = 0.1865\%. Aus der Symmetrie 10pi + 5pj = 1 folgt für die Wahrscheinlichkeit pj, daß ein ständiges Mitglied den Ausschlag gibt, p_j = 19.62\%.

Die ständigen Mitglieder sind also 100mal einflußreicher als ein nichtständiger Mitgliedsstaat.

Quellen

  • Ewald Burger: 'Einführung in die Theorie der Spiele'
Meine Werkzeuge