$\Gamma = (I, X := \prod_{i\in I} X_i, (c_i)_{i\in I})$
$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.
$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$ |
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.
Jedes exakte Potentialspiel „ist“ ein ungewichtetes Auslastungsspiel. Monderer/Shapley'96
induziert Abbildung von Strategieprofilen: $\phi: X \to Y: x \mapsto$ $($$\phi_j$$(x_{\sigma(j)})$$)_{j \in J}$.
$(\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})$
Jedes exakte Potentialspiel ist kostenerhaltend isomorph zu einem ungewichteten Auslastungsspiel. Monderer/Shapley'96
$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
Jedes Spiel ist kostenerhaltend isomorph zu einem gewichteten Auslastungsspiel. Milchtaich'13
Jedes gewichtete Potentialspiel ist kostenerhaltend isomorph zu einem kostengewichtetes Auslastungsspiel.
Wie beim Satz von Monderer und Shapley (exakte Potentialspiele)
Jedes skalierte Potentialspiel ist exakt isomorph zu einem skalierten Auslastungsspiel.