Elimination durch Dominanz:Normalform

Aus Wikiludia
Wechseln zu: Navigation, Suche

Die Elimination durch (strikte) Dominanz ist ein Algorithmus, der bei manchen Spielen in Normalform geeignet ist, konstruktiv die Existenz eines (eindeutigen strikten) Nash-Gleichgewichtes zu beweisen.

Es sei ein Spiel S in Normalform gegeben mit der Spielermenge I = {1,\dots,n}, den Strategieräumen Si für alle i\in I und den Auszahlungsfunktionen p_i:S_1\times\dots\times S_n \to \mathbb R für alle i\in I.

Inhaltsverzeichnis

Definition

Man sagt, eine Strategie s_i\in S_i eines Spielers i\in I werde durch die Strategie \tilde s_i\in S_i schwach dominiert, wenn gilt: für jede Wahl von s_{-i} \in S_1\times\dots\times\hat S_i\times\dots\times S_n ist p_i(s_i, s_{-i}) \le p_i(\tilde s_i, s_{-i}), und für mindestens ein s'_{-i} \in S_1\times\dots\times\hat S_i\times\dots\times S_n ist p_i(s_i, s'_{-i}) < p_i(\tilde s_i, s'_{-i}). Gilt sogar stets die strikte Ungleichung, so sagt man, si werde durch \tilde s_i strikt dominiert.

Anschaulich gesprochen, besagt das: unabhängig davon, wie sich die übrigen n − 1 Spieler verhalten, bietet die Entscheidung für si für den Spieler i niemals einen Vorteil gegenüber der Entscheidung für \tilde s_i. Ist die Dominanz sogar strikt, so ist die Entscheidung für si sogar stets ein Nachteil.

Somit ist \tilde s_i eine dominante Strategie, da sie dem Spieler unter allen verfügbaren Strategien den höchsten Nutzen ermöglicht, und zwar unabhängig davon, was die anderen Spieler tun.

Verfügt der Spieler über eine dominante Strategie, so besteht für ihn ja gar keine strategische Unsicherheit, denn um die eigene optimale Strategie zu finden, muß er sich nicht überlegen, welche Strategien seine Mitspieler verfolgen könnten.

Bestimmung von Nash-Gleichgewichten durch iterierte Elimination

Die zentrale Idee ist es, im Falle der Existenz einer dominierten Strategie eines Spielers diese Strategie aus dem Strategieraum des Spielers zu entfernen. Alle Nash-Gleichgewichte dieses vereinfachten Spieles sind auch Nash-Gleichgewichte des ursprünglichen Spiels; genauer gilt:

Satz

Es sei i_0\in I ein Spieler und s_{i_0}, \tilde s_{i_0} \in S_{i_0} Strategien, so daß s_{i_0} von \tilde s_{i_0} (strikt) dominiert werde. Es sei S' das Spiel mit der Spielermenge I, die Strategiemengen S'i mit S'i = Si für i\neq i_0 und S'_{i_0} = S_{i_0} \setminus {s_{i_0}} sowie die durch Einschränkung gewonnenen Auszahlungsfunktionen p'_i =
{p_i}_{|\tilde S_1\times\dots\times\tilde S_n}.

Dann gilt: die Nash-Gleichgewichte von S' sind (genau die) Nash-Gleichgewichte von S.

Beweis Dies folgt direkt aus der Definition der (strikten) Dominanz.

Folgerung

Die Strategiemengen Si seien alle endlich. Dann existiert ein Spiel \tilde S, das aus S durch wiederholte Elimination durch Dominanz hervorgeht, so daß \tilde S keine dominierten Strategien irgendeines Spielers mehr enthält.

Weiter ist dann jedes Nash-Gleichgewicht von \tilde S auch ein Nash-Gleichgewicht von S. (Sind insbesondere alle Strategiemengen von \tilde S einelementig, so ist das einzige noch vorhandene Strategieprofil ein Nash-Gleichgewicht von S). Entsteht zusätzlich \tilde S aus S ausschließlich durch Elimination strikt dominierter Strategien, so existieren für S keine weiteren Nash-Gleichgewichte außer denjenigen von \tilde S.
Beweis: Ausgehend von S gehe man iterativ durch Elimination einer dominierten Strategie zu neuen Spielen über. Dieses Verfahren muß spätestens dann abbrechen, wenn alle Strategiemengen einelementig geworden sind, da es dann nach Definition der Dominanz keine dominierten Strategien mehr geben kann. Die übrigen Aussagen ergeben sich unmittelbar aus dem Satz.

Beispiel

Aufgabenstellung

Gegeben sei ein Spiel in Normalform mit zwei Spielern 1 und 2, welche jeweils die Elemente der Menge S1 = {oben,mitte,unten} bzw. S2 = {links,mitte,rechts} als Aktionen besitzen. Die entsprechenden Auszahlungsfunktionen u1 und u2 auf dem Strategieraum S = S1xS2 seien durch folgende Matrizen gegeben:

 u_1 = \begin{pmatrix} 2 & 1 & 4 \\ 1 & 1 & 2 \\ 1 & 0 & 3 \end{pmatrix}            
 u_2 = \begin{pmatrix} 0 & 1 & 2 \\ 4 & 1 & 3 \\ 3 & 2 & 0 \end{pmatrix}

Man zeige, dass das Verfahren der Elimination der strikt dominierten Strategien hier immer zu einem Nash-Gleichgewicht führt.

Lösung

Zunächst lässt sich s1 = u eliminieren, da diese Strategie von s1 = o strikt dominiert wird.

Dies führt zu folgenden neuen Matrizen:

 u_1 = \begin{pmatrix} 2 & 1 & 4 \\ 1 & 1 & 2 \end{pmatrix}            
 u_2 = \begin{pmatrix} 0 & 1 & 2 \\ 4 & 1 & 3 \end{pmatrix}

Als nächstes lässt sich s2 = m eliminieren, da diese Strategie von s2 = r strikt dominiert wird.

Dies führt zu folgenden Matrizen:

 u_1 = \begin{pmatrix} 2 & 4 \\ 1 & 2 \end{pmatrix}            
 u_2 = \begin{pmatrix} 0 & 2 \\ 4 & 3 \end{pmatrix}

Nun eliminieren wir noch s1 = m (da sie von s1 = o dominiert wird) und s2 = l (da sie von s2 = r dominiert wird).

Übrig bleibt s1 = o und s2 = r mit den Auszahlungen: u1(o,r) = 4 und u2(o,r) = 2, was genau das Nash-Gleichgewicht dieses Spiels ist.

Meine Werkzeuge