Koalitionsspiel: Charakteristische Funktion

Aus Wikiludia
Wechseln zu: Navigation, Suche

Die charakteristische Funktion eines kooperativen Spiels ordnet jeder Koalition C der Spielermenge N={1,...,n} den Gewinn zu, den die Koalitionäre maximal unter sich aufteilen können.

V: \mathcal{P}(N) \longrightarrow \R, \quad C \longmapsto V(C),

wobei P(N) die Menge aller nicht-leeren Teilmengen von N ist.
Die Potenzmenge \mathcal{P}(N) hat genau 2N Elemente und es gibt genau 2N − 1 Koalitionen, da die leere Menge nicht als Koalition betrachtet werden kann.

Inhaltsverzeichnis

Koalitionsspiel mit transferierbarem Nutzen

Definition

1. Ein Koalitionsspiel (N,v) bei transferierbarem Nutzen ist eine Spielermenge N \ne \varnothing mit der Koalitionsfunktion v: \mathcal{P}(N) \rightarrow \R , \ wobei \ v(\varnothing)=0 erfüllt sei.

2. Die Menge G_N:=\{(N,v): \ v \ ist \ Koalitionsfunktion \ \mathcal{P}(N) \rightarrow \R \ mit \ v(\varnothing)=0 \} ist die Menge aller Koalitionsspiele auf N.

3. Die Koalitionsfunktion v mit transferierbarem Nutzen ist superadditiv \Leftrightarrow \forall C, \ C' \subseteq N: \ C \cap C' \ne \varnothing \Rightarrow v(C) + v(C') \le v(C \cup C')

4. Das Koalitionsspiel v heißt einfach, wenn gilt:
- für alle Koalitionen C \subseteq N gilt: v(C) = 0 oder v(C) = 1 und
- C'\subseteq C'' \Rightarrow v(C')\le v(C'')

5. Sei v einfaches Spiel. Der Spieler i \in N heißt Veto-Spieler \Leftrightarrow v(N\setminus\{i\})=0; Der Spieler i heißt Diktator \Leftrightarrow \forall C \subseteq N: v(C)=1 \forall i \in C und 0 sonst.

Bemerkung

1. Koalitionen C, die v(C) = 1 erfüllen, heißen siegreich oder Gewinnerkoalitionen.
2. Koalitionen C, die v(C) = 0 erfüllen, heißen unterlegen oder Verlustkoalitionen.
3. Der Kooperationsgewinn ist (falls existent): v(C \cup C')-v(C)-v(C')
4. Veranschaulichung: Transferierbarkeit bedeutet, dass \forall \ Spieler \ 1 \le i \ne j \le N die Nutzen der Spieler direkt miteinander verglichen werden können, beispielsweise dann, wenn alle Spieler ihren Nutzen in Geldeinheiten messen. (abgrenzendes Beispiel siehe nicht transferierbarer Nutzen unten)
5. Beispielsweise das Handschuh-Spiel ist superadditiv

Beispiel APEX-Spiel

Ist ein APEX-Spieler ein Veto-Spieler oder ein Diktator?
Der APEX-Spieler ist kein Veto-Spieler, da sich alle Gegner gegen ihn verbünden können. Also ist er auch kein Diktator.

Koalitionsspiel ohne transferierbarem Nutzen

Definition

1. Ein Koalitionsspiel (N,V) bei nicht transferierbarem Nutzen ist eine Spielermenge N \ne \varnothing zusammen mit der Abbildung V: \mathcal{P}(N) \rightarrow \R^{|C|}, die jeder Koalition C \subseteq N eine Teilmenge des \R^{|C|} zuordnet, dass gilt:
- V(\varnothing)=\varnothing und
- V(C) \ne \varnothing,\ C \ne \varnothing
2. Die Koalitionsfunktion V ohne transferierbarem Nutzen heißt superadditiv, falls für alle Koalitionen C,C' \sub N gilt: C \cap C' = \varnothing , u_C \in V(C) sowie u_{C'} \in V(C') \Rightarrow (u_C,u_{C'}) \in V(C \cup C')

Bemerkung

1. Die Koalitionsfunktion ohne transferierbaren Nutzen bezeichnet man mit V, um sie vom Fall der transferierbaren Nutzen abzugrenzen (Koalitionsfunktion v).
2. V ordnet jeder Koalition C \ne \varnothing \ mit \ |C| Mitgliedern die Menge an Nutzenvektoren u_C:=(u_i)_{i\in C} \in \R^{|C|} zu. ui ist also die Auszahlung für Spieler i. V(C) enthält die Menge der Auszahlugsvektoren, die die Koalition erreichen kann.
3. Jede Koalitionsfunktion v kann auch als Koalitionsfunktion V geschrieben werden mit V(C):= \{x_C \in \R^{|C|}: \sum_{i\in C} x_i\ \le v(C)\}.
4. (uC,uC') ist der Vektor, der für die Koalitionäre von C bzw C' die Nutzenwerte enthält.
5. Die Superadditivität besagt, dass für zwei Spieler die jeweiligen Nutzen in der Koalition mindestens genauso hoch sind, wie wenn sie nicht koalieren würden.
6. Nicht transferierbarer Nutzen ist gegeben, wenn der Nutzen zwischen Spielern einer Koalition nicht angemessen verglichen werden können (siehe Heiratsmarktoder anderes Beispiel: Spieler 1 geht ins Fußballtraining, um sportlich ausgeglichen zu sein. Spieler 2 geht ins Training, da er in naher Zukunft Geld damit verdienen möchte.)

Beispiel Tauschökonomie

Konstruktion der Koalitionsfunktion

Für dieses Beispiel seien l Güter auf n Personen aufzuteilen. Diese n Personen können koalieren, und jede Person 1 \le i \le n: besitzt eine Anfangsausstattung dieser l Güter: 0 \le g_i=({g_i}^1,...,{g_i}^l) \in {{\R}_+}^l.
Für jede Koalition C muss die zugehörige Gütermenge ermittelt werden.
Anhand der Gütermenge definiere man die Nutzenwerte, die die Koalitionäre in C erreichen können.

Definition Tauschökonomie

1. Eine Allokation h={(h_i)}_{i \in N} heißt zulässig \Leftrightarrow \sum_{i\in N} h_i\ \leq \sum_{i \in N} g_i
2. Eine Allokation h={(h_i)}_{i \in N} heißt C-zulässig \Leftrightarrow \sum_{i\in C} h_i\ \leq \sum_{i \in C} g_i
3. Eine Tauschökonomie (N,{(g_i)}_{i \in N},{(U_i)}_{i \in N}) ist eine Menge von N Spielern mit einer Anfangsausstattung {(g_i)}_{i \in N} \in {{\R}_+}^l und Nutzenfunktionen {(U_i)}_{i \in N}, U_i: {{\R}_+}^l \rightarrow \R

Koalitionsfunktion

Die Koalitionsfunktion für die Tauschökonomie ohne transferierbarem Nutzen ist also: V(C)=\{u_C \in \R^{|C|}: \exists C-zulässige Allokation x mit u_i \le U_i(x_i) ,\ i \in C\}
In dieser Funktion sind durch uC auch alle {u_C}' \le u_C \in V(C) enthalten.

Beispiel Heiratsmarkt

zurück zu Koalitionsspiel
zurück zur Liste der Schlüsselwörter

Literatur: 

* Harald Wiese: Kooperative Spieltheorie. München 2005, ISBN 3-486-57745-X.
Von „http://wikiludia.math.lmu.de/wiki/index.php?title=Koalitionsspiel:_Charakteristische_Funktion“
Meine Werkzeuge