www.wikidata.de-de.nina.az

Iterative Eliminierung strikt dominierter Strategien Die iterative Eliminierung strikt dominierter Strategien auch itera

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 Bearbeiten

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 ein Zweipersonenspiel mit den Auszahlungsfunktionen von Spieler 1 und 2 und den Strategieräumen und von Spieler 1 und 2. Seien weiterhin und mögliche Strategien für Spieler 1 (d. h. ).

Dann ist strikt dominiert von , wenn gilt:

für jede Strategie des anderen Spielers.

Das Verfahren Bearbeiten

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.

Anwendung Bearbeiten

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 Bearbeiten

Gegeben sei die folgende Bimatrix

 




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

 




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

 




Somit wurde durch sukzessives eliminieren der dominierten Strategien das Nash-Gleichgewicht gefunden. Mit dieser Methode lassen sich auch komplexe Bimatrizen auf ihre Realisierungen reduzieren.

Einzelnachweise Bearbeiten

  1. Manfred J. Holler, Gerhard Illing: Einführung in die Spieltheorie S. 105
  2. Florian Bartholomae, Marcus Wiens: Spieltheorie: Ein anwendungsorientiertes Lehrbuch S. 71

Siehe auch Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 Inhaltsverzeichnis 1 Grundlagen 2 Das Verfahren 3 Anwendung 4 Beispiel 5 Einzelnachweise 6 Siehe auchGrundlagen BearbeitenUm das Konzept der iterativen Eliminierung der strikt dominierten Strategien zu verstehen muss zunachst das Wesen einer dominierten Strategie erlautert 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 lasst sich strikte Dominanz wie folgt darstellen Sei G S1 S2 u1 u2 displaystyle G S 1 S 2 u 1 u 2 nbsp ein Zweipersonenspiel mit den Auszahlungsfunktionen u1 u2 displaystyle u 1 u 2 nbsp von Spieler 1 und 2 und den Strategieraumen S1 displaystyle S 1 nbsp und S2 displaystyle S 2 nbsp von Spieler 1 und 2 Seien weiterhin s1 displaystyle s 1 nbsp und s1 displaystyle s 1 nbsp mogliche Strategien fur Spieler 1 d h s1 s1 S1 displaystyle s 1 s 1 in S 1 nbsp Dann ist s1 displaystyle s 1 nbsp strikt dominiert von s1 displaystyle s 1 nbsp wenn gilt u1 s1 s2 lt u1 s1 s2 displaystyle u 1 s 1 s 2 lt u 1 s 1 s 2 nbsp fur jede Strategie s2 S2 displaystyle s 2 in S 2 nbsp des anderen Spielers Das Verfahren BearbeitenDie iterative Eliminierung strikt dominierter Strategien bezeichnet die sukzessive Eliminierung dominierter Strategien solange bis keine dominierten Strategien mehr existieren Dieses Verfahren ermoglicht die Vereinfachung von Spielen auf ihre moglichen Realisierungen im Idealfall soweit dass nur noch eine Strategiekombination ubrig bleibt 1 Auf diese Art und Weise konnen Nash Gleichgewichte in Bimatrizen gefunden werden Im Gegensatz zur iterativen Eliminierung schwach dominierter Strategien ist das Ergebnis der iterativen Eliminierung bei strikter Dominanz eindeutig unabhangig von der Reihenfolge der Eliminierung Im Allgemeinen bezeichnet man Strategien die diese Eliminierung uberleben als rationalisierbare Strategien 2 Hauptartikel RationalisierbarkeitAnwendung BearbeitenDie 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 BearbeitenGegeben sei die folgende Bimatrix y1 displaystyle y 1 nbsp y2 displaystyle y 2 nbsp x1 displaystyle x 1 nbsp 5 displaystyle 5 nbsp 3 displaystyle 3 nbsp 6 displaystyle 6 nbsp 6 displaystyle 6 nbsp x2 displaystyle x 2 nbsp 4 displaystyle 4 nbsp 2 displaystyle 2 nbsp 5 displaystyle 5 nbsp 4 displaystyle 4 nbsp wobei x1 displaystyle x 1 nbsp x2 displaystyle x 2 nbsp die Strategien von Spieler 1 und y1 displaystyle y 1 nbsp y2 displaystyle y 2 nbsp die Strategien von Spieler 2 darstellen Wir beginnen bei Spieler 1 Fur Spieler 1 wird die Strategie x2 displaystyle x 2 nbsp von der Strategie x1 displaystyle x 1 nbsp strikt dominiert x1 displaystyle x 1 nbsp ist dominante Strategie Aus diesem Grund kann man die Strategie x2 displaystyle x 2 nbsp streichen und die Bimatrix reduziert sich auf y1 displaystyle y 1 nbsp y2 displaystyle y 2 nbsp x1 displaystyle x 1 nbsp 5 displaystyle 5 nbsp 3 displaystyle 3 nbsp 6 displaystyle 6 nbsp 6 displaystyle 6 nbsp Wir fahren bei Spieler 2 fort Aus der Sicht von Spieler 2 wird y1 displaystyle y 1 nbsp strikt von y2 displaystyle y 2 nbsp dominiert und kann somit gestrichen werden Es bleibt das folgende Nash Gleichgewicht ubrig y2 displaystyle y 2 nbsp x1 displaystyle x 1 nbsp 6 displaystyle 6 nbsp 6 displaystyle 6 nbsp Somit wurde durch sukzessives eliminieren der dominierten Strategien das Nash Gleichgewicht NGG x1 y2 displaystyle NGG x 1 y 2 nbsp gefunden Mit dieser Methode lassen sich auch komplexe Bimatrizen auf ihre Realisierungen reduzieren Einzelnachweise Bearbeiten Manfred J Holler Gerhard Illing Einfuhrung in die Spieltheorie S 105 Florian Bartholomae Marcus Wiens Spieltheorie Ein anwendungsorientiertes Lehrbuch S 71Siehe auch BearbeitenLosungskonzept Abgerufen von https de wikipedia org w index php title Iterative Eliminierung strikt dominierter Strategien amp oldid 240649083