Auslastungsspiel

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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 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[Bearbeiten]

Jedes Auslastungsspiel hat mindestens ein Nash-Gleichgewicht in reinen Strategien, da es eine Potenzialfunktion besitzt.[2] 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)

Quellen[Bearbeiten]

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