Potenzial (Spieltheorie)

Ein Ordnungspotenzial oder eine Ordnungspotenzialfunktion ist in der Spieltheorie eine spezielle Funktion auf der Menge der Strategiekombinationen eines Spiels. Durch diese Funktion werden die Strategiekombination nach ihrer Auszahlung an die Spieler angeordnet. Eine Strategiekombination besitzt dabei genau dann einen höheren Wert, wenn sie für jeden Spieler zu einer höheren Auszahlung führt. Indem man Ordnungspotenzialfunktion strenger an die Auszahlungsfunktionen bindet, erhält man die Spezialfälle des gewichteten Potenzials und des exakten Potenzials. Letzteres wird auch einfach nur als Potenzial oder Potenzialfunktion bezeichnet.

Die meisten Spiele besitzen allerdings kein Ordnungpotenzial. Von Dov Monderer wurden deshalb 1988 bzw. 1996 die folgenden Klassen von Spielen eingeführt:<ref name="potential">Dov Monderer, Lloyd S. Shapley: Potential Games. In: Games and Economic Behavior 14, 1996, S. 124–143. doi:10.1006/game.1996.0044.</ref>

Spiel mit Ordnungspotenzial
Spiel mit gewichtetem Potenzial
Spiel mit (exaktem) Potenzial

Eine Potenzialfunktion wurde bei Spielen erstmals 1973 von Robert W. Rosenthal eingesetzt, um zu zeigen, dass Auslastungsspiele ein Nash-Gleichgewicht in reinen Strategien besitzen.<ref>Robert W. Rosenthal: A Class of Games Possessing Pure-Strategy Nash Equilibria. In: International Journal of Game Theory. Nr. 2, 1973, S. 65–67. doi:10.1007/BF01737559.</ref>

Definition

Bei allen drei Definitionen sei <math>\Gamma = (N, \Sigma, u)</math> ein Spiel in Normalform. Weiter sei <math>\sigma \in \Sigma</math> ein beliebiges aber festes Strategieprofil und <math>\sigma' := (\sigma^{-i}, \sigma_i')</math> das Profil, das durch den Wechsel der Strategie eines Spielers <math>i \in N</math> von <math>\sigma_i</math> zu <math>\sigma_i'</math> entsteht.

Ordnungspotenzial

Eine Ordnungspotenzialfunktion <math>P</math> ist eine Funktion <math>P: \Sigma \rightarrow \R</math>, für die gilt, dass

<math>u_i(\sigma') - u_i(\sigma) > 0 \quad \Leftrightarrow \quad P(\sigma') - P(\sigma) > 0</math>

Gewichtetes Potenzial

Eine gewichtete Potenzialfunktion <math>P</math> ist eine Funktion <math>P: \Sigma \rightarrow \R</math> bei der für jeden Spieler <math>i \in N</math> eine Zahl <math>w_i > 0</math> existiert, sodass stets gilt, dass

<math>u_i(\sigma') - u_i(\sigma) = w_i \cdot (P(\sigma') - P(\sigma))</math>

In diesem Fall nennt man <math>\Gamma</math> ein gewichtetes Potenzialspiel. Die Gewichte <math>w_1, w_2, \ldots, w_n</math> bilden einen Vektor <math>w</math>. Kennt man diese Zahlen, so nennt man <math>P</math> ein <math>w</math>-Potenzial und spricht von einem Spiel mit <math>w</math>-Potenzial.

Exaktes Potenzial

Eine (exakte) Potenzialfunktion <math>P</math> ist eine Funktion <math>P: \Sigma \rightarrow \R</math> für die gilt, dass

<math>u_i(\sigma') - u_i(\sigma) = P(\sigma') - P(\sigma)</math>

Die exakte Potenzialfunktion ist also ein Spezialfall einer gewichteten Potenzialfunktion, bei der alle Gewichte <math>w_i = 1</math> sind. Es gilt, dass jedes Auslastungsspiel eine exakte Potentialfunktion hat, umgekehrt ist jedes endliche Spiel, welches eine exakte Potentialfunktion besitzt, isomorph zu einem Auslastungsspiel.<ref name="potential" />

Eigenschaften

Jedes endliche Spiel mit Ordnungspotenzial besitzt ein Nash-Gleichgewicht in reinen Strategien.

Zwei Potenzialfunktionen <math>P_1</math> und <math>P_2</math> eines Spiels unterscheiden sich nur durch eine Konstante:

<math>P_1(\sigma) = P_2(\sigma) + c</math>

Das bedeutet, dass für zwei Strategiekombinationen <math>\sigma^*</math> und <math>\sigma^{**}</math> gilt

<math>P_1(\sigma^*) - P_1(\sigma^{**}) = P_2(\sigma^*) - P_2(\sigma^{**})</math>

Quellen