Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Auslastungsspiel aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Auslastungsspiel

Ein Auslastungsspiel oder Congestion Game ist in der Spieltheorie ein Spiel, bei dem jeder Spieler eine Menge allgemein verfügbarer Ressourcen wählt, 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ängen davon ab, wieviele 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.Robert W. Rosenthal: [http://www.springerlink.com/index/J5T4730452755627.pdf A Class of Games Possessing Pure-Strategy Nash Equilibria.] In: International Journal of Game Theory. Nr. 2, 1973, S. 65?67

Formale Definition

Es sei $R\; =\; \backslash \{r\_1,\; r\_2,\; \backslash ldots,\; r\_t\; \backslash \}$ eine Menge von $t$ Ressourcen und $c\_j:\backslash N\_0\; \backslash to\; \backslash R$ jeweils die Kostenfunktion der Ressource $r\_j$. Ein Auslastungsspiel $\backslash Gamma\; =\; (N,\; \backslash Sigma,\; u)$ ist ein Spiel_in_Normalform mit
* Menge der Spieler $N=\backslash \{1,2,\backslash ldots,n\backslash \}$
* Strategieraum $\backslash Sigma\; =\; \backslash \{\backslash Sigma\_1,\; \backslash Sigma\_2,\; \backslash ldots,\; \backslash Sigma\_n\backslash \}$ mit $\backslash Sigma\_i\; \backslash subseteq\; \backslash mathcal\{P\}(R)$
* Nutzenfunktionen
*::$u\_i(\backslash sigma)\; =\; -\; \backslash sum\_\{r\_j\; \backslash in\; \backslash sigma\_i\}\; c\_j(x\_j(\backslash sigma))$
*: $x\_j(\backslash sigma)$ ist dabei die Anzahl der Spieler ist, die $r\_j$ in der Strategkiekombination $\backslash 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.Dov Monderer, Lloyd S. Shapley: [http://ie.technion.ac.il/~dov/potential.pdf Potential Games.] Games and Economic Behavior 14, 1996, S. 124?143 Eines dieser Nash-Gleichgewichte ist eine Strategiekombination $\backslash sigma^*$, die den Ausdruck
:$\backslash sum\_\{j=0\}^t\; \backslash sum\_\{y=0\}^\{x\_j(\backslash sigma)\}\; c\_j(y)$
minimiert. Denn angenommen $\backslash sigma^*$ wäre kein Nash-Gleichgewicht, dann existiert ein Spieler $i$ und eine Strategie $\backslash sigma\text{'}\; =\; (\backslash sigma\_i\text{'},\; \backslash sigma\_\{-i\}^*)$ bei der sich dieser Spieler besser stellt:
:$-\; \backslash sum\_\{r\_j\; \backslash in\; \backslash sigma\_i\text{'}\; \backslash atop\; r\_j\; \backslash notin\; \backslash sigma\_i^*\}\; c\_j(x\_j(\backslash sigma^*)\; +\; 1)\; >\; -\; \backslash sum\_\{r\_j\; \backslash in\; \backslash sigma\_i^*\; \backslash atop\; r\_j\; \backslash notin\; \backslash sigma\_i\text{'}\}c\_j(x\_j(\backslash sigma^*))$
Dies führt zu einem Widerspruch zur Minimalität von $\backslash sigma^*$.
:

Quellen

       VIDEO-NEWS UND ANGEBOTE