Handschuh-Spiel

Aus Wikiludia
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Das Handschuhspiel

Das Handschuhspiel ist ein Spiel aus der kooperativen Spieltheorie, das folgendermaßen aufgebaut ist:

Es verfügen einige Spieler über je einen rechten Handschuh, und die restlichen über je einen linken Handschuh. Dabei gilt, dass einzelne Handschuhe über keinen Wert verfügen, sondern nur Paare. Natürlich ist es unökonomisch für einen Spieler mit rechten Handschuh diesen einfach wegzuwerfen, da er ihn an einen anderen Spieler, der einen linken Handschuh besitzt, verkaufen kann, und somit beide einen Gewinn erzielen!

Im folgenden Artikel werden nun unterschiedliche Lösungskonzepte vorgestellt, wie sich anhand von Koalitionen die Preise für einen rechten/linken Handschuh bilden.

Zuerst jedoch noch ein paar Erläuterungen, die benötigt werden:

  • N steht für die Menge der Spieler
  • L gibt die Menge der Spieler mit einem linken Handschuh an und R die Menge aller Spieler mit einem rechten Handschuh. Dabei gilt: L \cap R=\emptyset und L \cup R=N
  • K ist eine beliebige Koalition: K \subseteq N
  • die Koalitionsfunktion des Handschuhspiels: v_{L,R}:2^N \rightarrow \mathbb{R}, K \mapsto \min( |K \cap L| , |K \cap R|)

Lösungskonzepte

mengenwertige Lösungskonzepte

Pareto-Optimalität

Damit das Handschuhspiel pareto-optimal ist, muss für den Auszahlungsvektor x = (x1,x2,...,xn) die Bedingung \sum_{i \in N}x_i=v_{L,R}(N) gelten! Dies folgt automatisch aus den zwei Einzelbedingungen

(a) \sum_{i \in N}x_i \leq v_{L,R}(N) und

(b) \sum_{i \in N}x_i \geq v_{L,R}(N),

wobei (a) garantiert, dass die Aufteilung zulässig ist und (b) garantiert, dass es die größtmögliche Aufteilung gibt, und nicht gleichzeitig ein rechter und linker Handschuh übrig bleiben. Bedingung (b) schließt also die Blockade durch eine Koaliton (hier N: die große Koaliton) aus, was verhindert dass ein Spieler besser gestellt werden könnte, ohne dass ein anderer schlechter gestellt wird.


Beispiel mit L={1,2}, R={3}:

Alle x = (x1,x2,x3) mit x1 + x2 + x3 = 1 sind effizient, da:

v_{L,R}(N)=\min( |N \cap L| , |N \cap R|)= \min(1,1)=1


Daran lassen sich nun auch schon die ersten Nachteile dieses Lösungskonzepts aufzeigen:

Es gibt eine riesige Anzahl an Lösungsmöglichkeiten, die "Preise" für einen Handschuh, der weitergegeben wird, kann auch negativ sein, und es wird bei einem größeren Unterschied von |L| und |R| nicht die relative Knappheit der Güter beachtet.


Kern

Das Handschuhspiel lässt sich durch den Kern verbessern, indem Bedingung (b) verschärft wird durch:

\sum_{i \in K}x_i \geq v_{L,R}(K) \forall K \subseteq N

Damit wird nun sichergestellt, dass der Auszahlungsvektor nur positive Einträge enthält!


Beweis:

Für x = (x1,..,xn) muss nach Definition gelten: \sum_{i \in K}x_i \geq v_{L,R}(K) \forall K \subseteq N

Setze also K_i=\lbrace i \rbrace \forall i \in N \Rightarrow \sum_{j=i}^{i}x_i=x_i \geq v_{L,R}(K_i)=0


Für das oben genannte Beispiel mit vL,R(N) = 1 = x1 + x2 + x3 folgt nun:

x_i \geq 0, i=1,2,3

x_1+x_2 \geq v_{L,R}(\lbrace 1,2 \rbrace)=0

x_1+x_3 \geq v_{L,R}(\lbrace 1,3 \rbrace)=1

x_2+x_3 \geq v_{L,R}(\lbrace 1,2 \rbrace)=1

\Rightarrow x_1=x_2=0, x_3=1, und somit ist (0,0,1) der einzige optimale Auszahlungsvektor als Element des Kerns.

Das Problem hierbei ist nun, dass der Kern die relative Knappheit eines Gutes recht drastisch äußert, und in der Wirtschaft normalerweise keiner sich darauf einlassen würde, dem anderem alles kostenlos zu übergeben. Dieser Nachteil soll nun durch die Shapley-Lösung beseitigt werden.


punktwertige Lösungskonzepte

Shapley-Lösung

Die Shapley-Lösung beruht auf dem Shapley-Wert, und beachtet den Wert der Koalition, den ein einzelner Spieler i beitragen würde, wenn er daran teilnimmt, oder nicht.

Zurückkommend auf das Beispiel ergibt sich hier nun folgende Lösung:

\varphi_{1}({v})=\sum_{K\in P(N),1\in K}\frac{(|K|-1)!(n-|K|)!}{n!}(V({K})-V(K \setminus \{1\}))=

=\frac{(2-1)!(3-2)!}{3!}(0-0)+\frac{(2-1)!(3-2)!}{3!}(1-0)+\frac{(3-1)!(3-3)!}{3!}(1-1)=\frac{1}{6}

Da Spieler 1 mit einem linken Handschuh gleich gestellt ist mit Spieler 2, der ebenso einen linken Handschuh hat, ist auch \varphi_2=\frac{1}{6}. Also folgt \varphi_3=\frac{2}{3} und damit \varphi=(\frac{1}{6},\frac{1}{6},\frac{2}{3}) als Shapley-Lösung! Aber auch hier tritt nun wieder ein Problem auf, wenn man versucht das Spiel realitätsnah zu betrachten. Da es nur einen rechten Handschuh gibt, und somit Spieler 3 auch entweder nur mit Spieler 1 oder mit Spieler 2 zusammen arbeiten kann, ist es realitätsfremd wenn alle Spieler eine Auszahlung erhalten.

Daher nun noch das folgende Lösungskonzept:


Aumann-Drèze-Lösung

Die Aumann-Drèze-Lösung (kurz: AD-Lösung) ist auf die Shapley-Lösung aufgebaut, und beachtet zudem noch, welche Koalition zu Stande kommt, indem man eine Partition P einführt.

Vorsicht: abgewandeltes Pareto-Axiom: \sum_{i \in C}\varphi_i^{AD}(v,P)=v(C) \forall C \in P

Für unser Beispiel folgt nun also für P = {{1,3},{2}} (Spieler 1 und 3 gehen also die Koalition ein):

\varphi_1^{AD}(v_{\lbrace1,2 \rbrace,\lbrace 3 \rbrace},P)+\varphi_3^{AD}(v_{\lbrace1,2 \rbrace,\lbrace 3 \rbrace},P)=1 und

\varphi_2^{AD}(v_{\lbrace1,2 \rbrace,\lbrace 3 \rbrace},P)=0

Folglich geht nun Spieler 2, der ohne Koalitionspartner auf seinem Handschuhe sitzen bleibt, leer aus. Spieler 1 und 3 dagegen teilen sich nun den Ertrag. Damit dabei wieder die ursprünglich relative Knappheit eines Handschuhs bedacht bleibt, nutzt man nun noch zeitgleich die Außenoptionslösung, die von der Anzahl der übrig gebliebenen rechten oder linken Handschuhe abhängt, und deren Werte man nachfolgender Tabelle entnehmen kann:

| L | = 0 | L | = 1 | L | = 2 | L | = 3
| R | = 1 0 0,50 0,66 0,75
| R | = 2 0 0,33 0,50 0,63
| R | = 3 0 0,25 0,36 0,50

(Die Tabelle zeigt die Lösung für den Besitzer eines rechten Handschuhs an)

Daher ergibt sich nun die fertige Lösung als Auszahlunsvektor (\frac{1}{3},0,\frac{2}{3}).

Von „http://wikiludia.math.lmu.de/wiki/index.php?title=Handschuh-Spiel“
Meine Werkzeuge