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.[1]

Formale Definition

Es sei R = \{r_1, r_2, \ldots, r_t \} eine Menge von t Ressourcen und c_j:\N_0 \to \R jeweils die Kostenfunktion der Ressource rj. Ein Auslastungsspiel Γ = (N,Σ,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))
    xj(σ) ist dabei die Anzahl der Spieler, die rj in der Strategkiekombination σ 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.[2] Eines dieser Nash-Gleichgewichte ist eine Strategiekombination σ * , die den Ausdruck

\sum_{j=0}^t \sum_{y=0}^{x_j(\sigma)} c_j(y)

minimiert. Denn angenommen σ * 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 σ * .

\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. Games and Economic Behavior 14, 1996, S. 124–143

Wikimedia Foundation.

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”