Zusammenhänge von
Auslastungsspielen und Potentialspielen

Kolloquium zur Masterarbeit
18. Mai 2017

Lukas Graf

Oberseminar zur Optimierung

Endliche (nichtkooperative) Spiele

$\Gamma = (I, X := \prod_{i\in I} X_i, (c_i)_{i\in I})$

Ein endliches (nichtkooperatives) Spiel (in strategischer Form) ist gegeben durch

$I$	Spielermenge (endlich)
$X_i$	spielerspezifischen Strategiemengen (endlich) und
$c_i: X \to \mathbb{R}$	spielerspezifischen Kostenfunktionen.

Dabei heißen $X := \prod_{i\in I}X_i$ Strategieprofilraum und $x = (x_i)_{i\in I} \in X$ Strategieprofile.

Ein Strategieprofil $x \in X$ ist ein Nash-Gleichgewicht, wenn jeder Spieler $i \in I$ sich durch Wahl einer Alternativstrategie $\hat{x}_i \in X_i$ nicht verbessern kann, d.h. $c_i(x\mid \hat{x}_i) \geq c_i(x)$.

Ein Spiel $\Gamma$ ist ein Koordinationsspiel, wenn alle Spieler eine gemeinsame Kostenfunktion verwenden, d.h. $c_i = c_{\hat{\imath}}$ für alle Spieler $i, \hat{\imath} \in I$.

Auslastungsmodell

$M = (I, R, (S_i)_{i\in I}, (g_r)_{r \in R})$

$I$	Spielermenge
$R$	Ressourcenmenge
$S_i \subseteq \mathcal{P}(R)$	für Sp. $i$ zulässige Ressourcenwahlen
$g_r: \mathbb{R}_{\geq 0} \to \mathbb{R}$	Ressourcenkosten für Ressource $r$

(ungewichtetes) Auslastungsspiel

$\Gamma(M) := (I, S := \prod_{i\in I}S_i, (c_i)_{i\in I})$

Lastfunktion: $l_r(s) := \#\{i \in I | r \in s_i\}$
Kostenfunktion: $c_i(s) := \sum_{r \in s_i} g_r(l_r(s))$

Jedes (ungewichtete) Auslastungsspiel besitzt ein Nash-Gleichgewicht. Rosenthal'73

Definiere ein Potential:

$P: S \to \mathbb{R}: s \mapsto \sum_{r \in R}\sum_{k=1}^{l_r(s)} g_r(k)$

Für jede Abweichung $s \to (s\mid \hat{s}_i)$ gilt:

$c_i(s) - c_i(s\mid \hat{s}_i) =$$\,P(s) - P(s\mid \hat{s}_i)$

Jeder Verbesserungsschritt verringert also auch das Potential.

Ein Minimum von $P$ entspricht daher einem Nash-Gleichgewicht.

exaktes Potential

$P: X \to \mathbb{R}$ mit
$c_i(x) - c_i(x\mid \hat{x}_i) = P(x) - P(x\mid \hat{x}_i)$
f.a. $x \in X, i \in I, \hat{x}_i \in X_i$

$\Gamma$ besitzt genau dann ein exaktes Potential, wenn die Gesamtänderung entlang aller $4$-Zykel null ist. Monderer/Shapley'96

Jedes exakte Potentialspiel „ist“ ein ungewichtetes Auslastungsspiel. Monderer/Shapley'96

Morphismen von Spielen

$(\sigma, \phi): (I, X, (c_i)) \to (J, Y, (d_j))$ Morphismus von Spielen (vgl. Lapitsky'99):

$\sigma: I \leftarrow J$ Spielerabbildung
$\phi_j: X_{\sigma(j)} \to Y_j$ Strategieabbildung von Spieler $j$

induziert Abbildung von Strategieprofilen: $\phi: X \to Y: x \mapsto$ $($$\phi_j$$(x_{\sigma(j)})$$)_{j \in J}$.

$(\sigma, \phi): \Gamma \to \Delta$ Isomorphismus, wenn es einen Morphismus $(\tau, \psi): \Delta \to \Gamma$ gibt mit:

$(\tau, \psi)\circ(\sigma, \phi) := (\sigma\circ\tau, \psi\circ\phi) = (\mathrm{id}, \mathrm{id})$ und $(\sigma, \phi)\circ(\tau, \psi) = (\mathrm{id},\mathrm{id})$

Verträglichkeit mit den Kostenfunktionen

$(\sigma, \phi): \Gamma \to \Delta$ Morphismus von Spielen heißt:

kostenerhaltend, wenn f.a. $x \in X, j \in J: c_{\sigma(j)}(x) = d_j(\phi(x))$
exakt, wenn f.a. $x \in X, j \in J, \hat{x}_{\sigma(j)}$ gilt:
$c_{\sigma(j)}(x) - c_{\sigma(j)}(x \mid \hat{x}_{\sigma(j)}) = d_j(\phi(x)) - d_j(\phi(x \mid \hat{x}_{\sigma(j)}))$
monoton/ordinal/ ...

Jedes exakte Potentialspiel ist kostenerhaltend isomorph zu einem ungewichteten Auslastungsspiel. Monderer/Shapley'96

Definiere $M := (I, R, S, (g_r))$ mittels $R := R_K \cup R_D \subseteq \prod_{i \in I}\mathcal{P}(X_i)$ wobei

$R_K := \{(\{x_i\})_{i \in I} | x_i \in X_i \}$, $R_D := \{(Y_i)_{i \in I} | \exists \hat{\imath} \in I: Y_{\hat{\imath}} = X_{\hat{\imath}}, \forall i \neq \hat{\imath}: \vert X_i \setminus Y_i\vert = 1\}$

\[g_r(k) := \begin{cases} P(x), &r = \left(\{x_i\}\right)_{i \in I} \in R_k \text{ und } k=N \\ c_{\hat{\imath}}(x) - P(x), &r = \left(X_i\setminus\{x_i\}\right)_{i \in I\setminus\{\hat{\imath}\}} \times X_{\hat{\imath}} \in R_D, x_{\hat{\imath}} \in X_{\hat{\imath}} \text{ bel. und } k=1 \end{cases} \]

und Strategiemengen $S_i := \{ \{r \in R | x_i \in r_i\} | x_i \in X_i \}$.

Dann ist $(\mathrm{id}, \phi): \Gamma \to \Gamma(M)$ mit $\phi_i(x_i) := \{r \in R | x_i \in r_i\}$ ein kostenerhaltender Iso.

Jedes exakte Potentialspiel ist kostenerhaltend isomorph zu einem ungewichteten Auslastungsspiel. Monderer/Shapley'96

gewichtetes Potential

$c_i(x) - c_i(x\mid \hat{x}_i) =\,$$w_i\cdot$$\big(P(x) - P(x\mid \hat{x}_i)\big)$
mit Gewichtsvektor $(w_i)_{i \in I} \in \mathbb{R}^I_{\gt 0}$.

gewichtetes
Auslastungsspiel

$l_r(s) := \sum\{w_i | r \in s_i\}$
$c_i(s) := \sum_{r \in s_i} w_i g_r(l_r(s))$

nur aff.-lin. $g_r$

nur aff.-exp. $g_r$

Sei $C$ eine Menge stetiger Funktionen. Genau dann besitzt jedes gewichtete Auslastungsspiel mit Ressourcenkosten aus $C$ ein gewichtetes Potential, wenn $C$

entweder nur Funktionen der Form $g(k) = a_g \cdot k + d_g$ enthält
oder nur Funktionen der Form $g(k) = a_g\cdot b^k + d_g$ (mit gemeinsamem $b > 0$).

Alle Spiele besitzen genau dann sogar ein exaktes Potential, wenn $C$ ausschließlich affin-lineare Funktionen enthält.
Harks/Klimm/Möhring'11