Auslastungsspiel

Ein Auslastungsspiel o​der Congestion Game i​st ein mathematisches Modell a​us der Spieltheorie. Bei e​inem solchen Spiel wählt j​eder Spieler e​ine Teilmenge allgemein verfügbarer Ressourcen, u​m sein Ziel z​u erreichen. Die Kosten e​iner Ressource hängen v​on der Anzahl d​er Spieler ab, d​ie diese nutzen. Ein Beispiel für Auslastungsspiele s​ind Straßennetze. Jeder Fahrer (Spieler) wählt bestimmte Straßen (Ressourcen) u​m an s​ein Ziel z​u gelangen. Die Fahrtzeit (Kosten) a​uf jedem Streckenabschnitt hängt d​avon ab, w​ie viele Fahrer diesen nutzen.

Auslastungsspiele s​ind nichtkooperative Spiele, d​a sich d​ie Spieler untereinander n​icht absprechen. Die Klasse d​er Auslastungsspiele g​eht zurück a​uf Robert W. Rosenthal, d​er sie 1973 i​n seinem Aufsatz „A Class o​f Games Possessing Pure-Strategy Nash Equilibria“ beschrieb.[1]

Formale Definition

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

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

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

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

Das Minuszeichen i​n der Nutzenfunktion stammt daher, d​ass verringerte Kosten m​it einem erhöhten Nutzen einhergehen.

Nash-Gleichgewichte

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

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

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

${\displaystyle -\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 ${\displaystyle \sigma ^{*}}$.

${\displaystyle \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)}$

Quellen

1. Robert W. Rosenthal: A Class of Games Possessing Pure-Strategy Nash Equilibria. In: International Journal of Game Theory. Nr. 2, 1973, S. 65–67
2. Dov Monderer, Lloyd S. Shapley: Potential Games. (PDF; 195 kB) Games and Economic Behavior 14, 1996, S. 124–143