Seminář z kooperativní teorie her

Created by Martin Černý

Jádro

Jádro $C(v)$ kooperativní hry $(N,v)$ je množina výplatních vektorů $C(v) = \left\{x \in \mathbb{R} \mid \forall S \subseteq N: \sum_{i \in S}x_i \geq v(S) \text{ a } \sum_{i \in N}x_i = v(N) \right\}$

Výplatní vektor $x \in \mathbb{R}^n$ leží v jádru, pokud je

eficientní: $\sum_{i \in N}x_i = v(N)$ ,
koaličně racionální: $\forall S \subseteq N: \sum_{i \in S}x_i \geq v(S)$

Množinový předpis

Na solution concept $\psi$ pro kooperativní hru $(N,v)$ lze nahlížet jako na množinu

$\psi(v) = \{x \in \mathbb{R}^n \mid P(x)\}$

kde $P(x)$ je pravdivostní predikát na vektorem $x$ .

Konvexní hra

Kooperativní hra $(N,v)$ je konvexní, pokud splňuje $\forall S, T \subseteq N: v(S) + v(T) \leq v(S \cap T) + v(S \cup T)$

Superadditivní hra

Kooperativní hra $(N,v)$ je superaditivní, pokud splňuje

$\forall S, T \subseteq N, S \cap T = \emptyset: v(S) + v(T) \leq v(S \cup T)$

Kooperativní hra

Kooperativní hra je uspořádaná dvojice $(N,v)$ , kde

$N$ … je množina všech hráčů (grandkoalice),
$S \subseteq N$ … je koalice,
$v \colon 2^N \to \mathbb{R}$ je charakteristická funkce,
$v(\emptyset)=0$ je vždy zafixovaná.

Množinu všech kooperativních her na $n$ hráčích budeme označovat $\Gamma^n$ .

Výplatní vektor

Vektor $x \in \mathbb{R}^n$ je výplatní vektor (payoff vector).

Výplatní vektor $x \in \mathbb{R}^n$ je eficientní, pokud

$\sum_{i \in N}x_i = v(N)$

Solution concept

Výplatní mechanismy, které splňují určitě vlastnosti se nazývají solution concept (koncept řešení).

Funkční předpis

Na solution concept $\psi$ pro kooperativní hru $(N,v)$ lze nahlížet jako na zobrazení

$\psi \colon \Gamma^n \to 2^{\mathbb{R}^n}$

mezi prostorem her $\Gamma^n$ a množinou všech podmnožin $\mathbb{R}^n$ .

Monotonní hra

Kooperativní hra $(N,v)$ je monotonní, pokud splňuje

$\forall S \subseteq T \subseteq N: v(S) \subseteq v(T)$

Shapley value

Shapleyho hodnota $\phi(v)$ kooperativní hry $(N,v)$ je definována pro hráče $i \in N$ jako

$\phi_i(v) = \sum_{S \subseteq N \setminus \{i\}}\gamma_S\left[v(S \cup i) - v(S)\right]$

kde

$\gamma_S = \frac{|S|!(|N|-|S|-1)!}{|N|!}.$

Předpis pomocí vlastností

Na solution concept $\psi$ pro kooperativní hru $(N,v)$ se dá nahlížet jako na výplatní vektor, který splňuje sadu vlastností.

Nástroje na práce s koop. hrami

Jednohlasné hry

Pro $S \subseteq N$ je jednohlasná hra $(N,u_S)$ definovaná jako

$u_S(T) = 1$ pokud $S \subseteq T$ a

$u_S(T)=0$ pokud $S \not\subseteq T$ .

Jednohlasné hry $(N,u_S)$ pro $\emptyset\neq S \subseteq N$ tvoří bázi prostoru her $\Gamma^n$ s koeficienty

$d_v(S) = \sum_{T \subsetneq S}(-1)^{|S|-|T|}v(T).$