Iterative Eliminierung strikt dominierter Strategien

Die iterative Eliminierung strikt dominierter Strategien, auch iterative Elimination streng dominierter Strategien oder iterierte Elimination strikt dominierter Strategien genannt, 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äutert 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 ${\displaystyle G=\{S_{1},S_{2};u_{1},u_{2}\}}$ ein Zweipersonenspiel mit den Auszahlungsfunktionen ${\displaystyle u_{1},u_{2}}$ von Spieler 1 und 2 und den Strategieräumen ${\displaystyle S_{1}}$ und ${\displaystyle S_{2}}$ von Spieler 1 und 2. Seien weiterhin ${\displaystyle s_{1}'}$ und ${\displaystyle s_{1}''}$ mögliche Strategien für Spieler 1 (d. h. ${\displaystyle s_{1}',s_{1}''\in S_{1}}$).

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

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

für jede Strategie ${\displaystyle 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 so weit, dass nur noch eine Strategiekombination übrig bleibt.^[1] 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.^[2]

→ 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

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

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

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

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

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

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