Iterative Eliminierung strikt dominierter Strategien

Die iterative Eliminierung strikt dominierter Strategien auch iterative Elimination streng dominierter Strategien oder iterierte Elimination strikt dominierter Strategien ist in der Spieltheorie ein iteratives Verfahren zur Ermittlung von Nash-Gleichgewichten bei Spielen in Normalform.

Grundlagen

Um das Konzept der iterativen Eliminierung der strikt dominierten Strategien zu verstehen, muss zunächst das Wesen einer dominierten Strategie erläutertet werden. Eine dominierte Strategie ist eine Strategie, die dem Spieler keinen Nutzen stiftet und somit auch keine beste Antwort auf eine Strategie des Gegenspielers ist. Sie wird von einer sogenannten dominanten Strategie dominiert. Formal lässt sich strikte Dominanz wie folgt darstellen:

Sei $G=\{S_{1},S_{2};u_{1},u_{2}\}$ ein Zweipersonenspiel mit den Auszahlungsfunktionen $u_{1},u_{2}$ von Spieler 1 und 2 und den Strategieräumen $S_{1}$ und $S_{2}$ von Spieler 1 und 2. Seien weiterhin $s_{1}'$ und $s_{1}''$ mögliche Strategien für Spieler 1 (d. h. $s_{1}',s_{1}''\in S_{1}$).

Dann ist $s_{1}'$ strikt dominiert von $s_{1}''$, wenn gilt:

$u_{1}(s_{1}',s_{2})<u_{1}(s_{1}'',s_{2})$

für jede Strategie $s_{2}\in S_{2}$ des anderen Spielers.

Das Verfahren

Die iterative Eliminierung strikt dominierter Strategien bezeichnet die sukzessive Eliminierung dominierter Strategien, solange bis keine dominierten Strategien mehr existieren. Dieses Verfahren ermöglicht die Vereinfachung von Spielen auf ihre möglichen Realisierungen, im Idealfall soweit, dass nur noch eine Strategiekombination übrig bleibt. Auf diese Art und Weise können Nash-Gleichgewichte in Bimatrizen gefunden werden. Im Gegensatz zur iterativen Eliminierung schwach dominierter Strategien ist das Ergebnis der iterativen Eliminierung bei strikter Dominanz eindeutig (unabhängig von der Reihenfolge der Eliminierung). Im Allgemeinen bezeichnet man Strategien, die diese Eliminierung überleben als rationalisierbare Strategien.

→ Hauptartikel: Rationalisierbarkeit

Anwendung

Die iterative Eliminierung strikt dominierter Strategien wird vor allem bei komplexen Matrixspielen angewandt. Durch das Herausstreichen von irrelevanten bzw. unterlegenen Strategien wird die Dimension der Matrix vereinfacht, sodass man das Spiel einfacher handhaben kann.

Beispiel

Gegeben sei die folgende Bimatrix

	$y_{1}$	$y_{2}$
$x_{1}$	$5$ $3$	$6$ $6$
$x_{2}$	$4$ $2$	$5$ $4$

, wobei $x_{1}$,$x_{2}$ die Strategien von Spieler 1 und $y_{1}$, $y_{2}$ die Strategien von Spieler 2 darstellen. Wir beginnen bei Spieler 1. Für Spieler 1 wird die Strategie $x_{2}$ von der Strategie $x_{1}$ strikt dominiert ($x_{1}$ ist dominante Strategie). Aus diesem Grund kann man die Strategie $x_{2}$ streichen und die Bimatrix reduziert sich auf:

	$y_{1}$	$y_{2}$
$x_{1}$	$5$ $3$	$6$ $6$

Wir fahren bei Spieler 2 fort. Aus der Sicht von Spieler 2 wird $y_{1}$ strikt von $y_{2}$ dominiert und kann somit gestrichen werden. Es bleibt das folgende Nash-Gleichgewicht übrig:

	$y_{2}$
$x_{1}$	$6$ $6$

Somit wurde durch sukzessives eliminieren der dominierten Strategien das Nash-Gleichgewicht $NGG:(x_{1},y_{2})$ gefunden. Mit dieser Methode lassen sich auch komplexe Bimatrizen auf ihre Realisierungen reduzieren.

Siehe auch

• Lösungskonzept