Auslastungsspiel

Ein Auslastungsspiel oder Congestion Game ist ein mathematisches Modell aus der Spieltheorie. Bei einem solchen Spiel wählt jeder Spieler eine Teilmenge allgemein verfügbarer Ressourcen, um sein Ziel zu erreichen. Die Kosten einer Ressource hängen von der Anzahl der Spieler ab, die diese nutzen. Ein Beispiel für Auslastungsspiele sind Straßennetze. Jeder Fahrer (Spieler) wählt bestimmte Straßen (Ressourcen), um an sein Ziel zu gelangen. Die Fahrtzeit (Kosten) auf jedem Streckenabschnitt hängt davon ab, wie viele Fahrer diesen nutzen.

Auslastungsspiele sind nichtkooperative Spiele, da sich die Spieler untereinander nicht absprechen. Die Klasse der Auslastungsspiele geht zurück auf Robert W. Rosenthal, der sie 1973 in seinem Aufsatz „A Class of Games Possessing Pure-Strategy Nash Equilibria“ beschrieb.

Formale Definition

Es sei $R=\{r_{1},r_{2},\ldots ,r_{t}\}$ eine Menge von $t$ Ressourcen und $c_{j}\colon \mathbb {N} _{0}\to \mathbb {R}$ jeweils die Kostenfunktion der Ressource $r_{j}$. Ein Auslastungsspiel $\Gamma =(N,\Sigma ,u)$ ist ein Spiel in Normalform mit

• Menge der Spieler $N=\{1,2,\ldots ,n\}$
• Strategieraum $\Sigma =\{\Sigma _{1},\Sigma _{2},\ldots ,\Sigma _{n}\}$ mit $\Sigma _{i}\subseteq {\mathcal {P}}(R)$
• Nutzenfunktionen

  $u_{i}(\sigma )=-\sum _{r_{j}\in \sigma _{i}}c_{j}(x_{j}(\sigma ))$

  $x_{j}(\sigma )$ ist dabei die Anzahl der Spieler, die $r_{j}$ in der Strategiekombination $\sigma$ gewählt haben.

Das Minuszeichen in der Nutzenfunktion stammt daher, dass verringerte Kosten mit einem erhöhten Nutzen einhergehen.

Nash-Gleichgewichte

Jedes Auslastungsspiel hat mindestens ein Nash-Gleichgewicht in reinen Strategien, da es eine Potenzialfunktion besitzt. Eines dieser Nash-Gleichgewichte ist eine Strategiekombination $\sigma ^{*}$, die den Ausdruck

$\sum _{j=0}^{t}\sum _{y=0}^{x_{j}(\sigma )}c_{j}(y)$

minimiert. Denn angenommen $\sigma ^{*}$ wäre kein Nash-Gleichgewicht, dann existieren ein Spieler $i$ und eine Strategie $\sigma '=(\sigma _{i}',\sigma _{-i}^{*})$, bei der sich dieser Spieler besser stellt:

$-\sum _{r_{j}\in \sigma _{i}' \atop r_{j}\notin \sigma _{i}^{*}}c_{j}(x_{j}(\sigma ^{*})+1)>-\sum _{r_{j}\in \sigma _{i}^{*} \atop r_{j}\notin \sigma _{i}'}c_{j}(x_{j}(\sigma ^{*}))$

Dies führt zu einem Widerspruch zur Minimalität von $\sigma ^{*}$.

$\sum _{j=0}^{t}\sum _{y=0}^{x_{j}(\sigma ')}c_{j}(y)=\sum _{j=0}^{t}\sum _{y=0}^{x_{j}(\sigma ^{*})}c_{j}(y)+\sum _{r_{j}\in \sigma _{i}' \atop r_{j}\notin \sigma _{i}^{*}}c_{j}(x_{j}(\sigma ^{*})+1)-\sum _{r_{j}\in \sigma _{i}^{*} \atop r_{j}\notin \sigma _{i}'}c_{j}(x_{j}(\sigma ^{*}))<\sum _{j=0}^{t}\sum _{y=0}^{x_{j}(\sigma ^{*})}c_{j}(y)$