Elimination durch Dominanz:Extensive Form

Aus Wikiludia
Wechseln zu: Navigation, Suche

Bei der Elimination durch Dominanz bei Spielen extensiver Form mit vollkommener Information handelt es sich um ein schrittweises Verfahren, das ausgehend von den Auszahlungswerten an den terminalen Historien eines Spielbaums den Baum immer weiter verkürzt.
Dieser Algorithmus geht auf Zermelo zurück.
Ziel dieses Artikels ist es auch, den Algorithmus in der Folgendarstellung der extensiven Form präzise zu formalisieren.

Inhaltsverzeichnis

Beispiel

Folgendes Beispiel soll als Leitfaden für die weiteren Betrachtungen dienen (es handelt sich dabei um das Allokationsspiel oder Zuweisungsspiel, bei dem es darum geht zwei nicht teilbare, gleiche Güter auf zwei Akteure zu verteilen):
Spieler 1 stehen zu Beginn des Spiels drei Aktionen a,b,c zur Verfügung. Spieler 2 kann danach jeweils zwei Aktionen J,N wählen. An den terminalen Knoten befinden sich die Auszahlungen.
Der Baum sieht folgendermaßen aus:

                    1o                         
                   /|\                           
                  / | \                          
                 /  |  \                          
               a/  b|  c\                        
               /    |    \                   
              /     |     \      
             /      |      \      
            /       |       \            
           /        |        \    
         2o        2o        2o           
         / \       / \       / \               
       J/   \N   J/   \N   J/   \N
       /     \   /     \   /     \                          
     (2,0) (0,0)(1,1)(0,0)(0,2) (0,0)                       
                                 

Die Strategieprofile lassen sich in folgender Matrix anordnen:

J.J.J J.J.N J.N.J J.N.N N.J.J N.J.N N.N.J N.N.N
a (2,0) (2,0) (2,0) (2,0) (0,0) (0,0) (0,0) (0,0)
b (1,1) (1,1) (0,0) (0,0) (1,1) (1,1) (0,0) (0,0)
c (0,2) (0,0) (0,2) (0,0) (0,2) (0,0) (0,2) (0,0)

Das Spiel hat 9 Nash-Gleichgewichte.

Im folgenden Bild wird die Elimination durch iterierte Dominanz illustriert:


              1o                                     1o                            1o      
              /|\                                    /|\                           /|\
             / | \                                  / | \                         / | \
            /  |  \                                /  |  \                       /  |  \
          a/  b|  c\                             a/  b|  c\                    a/  b|  c\
          /    |    \                            /    |    \                   /    |    \
         /     |     \           -->            /     |     \        -->      /     |     \
        /      |      \                        /      |      \               /      |      \
       /       |       \                      /       |       \             /       |       \
      /        |        \                    /        |        \           /        |        \
    2o        2o        2o                  o         o         o         o         o         o
    / \       / \       / \                 |         |         |         2         1         0
  J/   \N   J/   \N   J/   \N              J|        J|        J|
  /     \   /     \   /     \               |         |         |
(2,0) (0,0)(1,1)(0,0)(0,2) (0,0)          (2,0)     (1,1)     (0,2)                   
                                                        

Im ersten Schritt wird bei den drei 'letzten' Entscheidungshistorien jeweils ein Nash-Gleichgewicht des Teilspiels unterhalb dieser Historie gewählt, und zwar durch Dominanz: Es werden jeweils Aktionen gewählt, die die Nutzenfunktion des Spielers 2 maximieren, hier J, J, J. Die anderen Aktionen an diesen Knoten werden alle eliminiert. Das ergibt den mittleren Spielbaum. Diesen kann man verkürzen, indem die jeweiligen letzten Aktionen weggelassen werden, da dort ja doch keine echte Entscheidung mehr stattfindet. Das ergibt den neuen Spielbaum auf der rechten Seite, in dem der Spieler 2 nicht mehr vorkommt. Der Spieler 1 wählt in diesem durch Elimination entstandenen Spiel ein Nash-Gleichgewicht (durch Dominanz). In unserem Falle ist a das einzige Nash-Gleichgewicht (wir haben strikte Dominanz), und man erhält insgesamt die Strategie (a,J.J.J) als teilspielperfektes Nash-Gleichgewicht mit dem Ausgang u(a,J.J.J)=(2,0). Natürlich kann man die drei unteren Teilspiele auch eines nach dem anderen durch Dominanz eliminieren.

In diesem Beispiel der Allokation gibt es noch eine weitere Möglichkeit der Elimination. Denn in dem linken unteren Teilspiel ist auch N ein Nash-Gleichgewicht, und das bedeutet, dass wir ganz analog folgende Elimination durchführen können:



              1o                                     1o                            1o      
              /|\                                    /|\                           /|\
             / | \                                  / | \                         / | \
            /  |  \                                /  |  \                       /  |  \
          a/  b|  c\                             a/  b|  c\                    a/  b|  c\
          /    |    \                            /    |    \                   /    |    \
         /     |     \           -->            /     |     \        -->      /     |     \
        /      |      \                        /      |      \               /      |      \
       /       |       \                      /       |       \             /       |       \
      /        |        \                    /        |        \           /        |        \
    2o        2o        2o                  o         o         o         o         o         o
    / \       / \       / \                 |         |         |         0         1         0
  J/   \N   J/   \N   J/   \N              N|        J|        J|
  /     \   /     \   /     \               |         |         |
(2,0) (0,0)(1,1)(0,0)(0,2) (0,0)          (0,0)     (1,1)     (0,2)                   
                                                        


Jetzt ist b die einzige strikt dominante Aktion, 1 wählt als das Nash-Gleichgewicht b. Die Elimination führt dieses Mal zu dem teilspielperfekten Nash-Gleichgewicht (b,N.J.J) mit u(b,N.J.J)=(1,0).

Der Satz von Zermelo

Die Aussage des Satzes

Es gilt folgender Satz (Zermelo 1912):

In einem endlichen extensiven Spiel mit vollkommener Information
gibt es stets ein teilspielperfektes Nash-Gleichgewicht.

Diese Aussage wird mit dem im Beispiel angedeuteten Algorithmus beweisen.
Der Algorithmus wird im Abschnitt Formalisierung des Algorithmus genauer diskutiert.

Historische Notiz: Zermelo und das Schachspiel

Zermelo dachte an das Schachspiel, als er die Idee für den Algorithmus entwarf.
Für weitere Informationen siehe den Artikel [Zermelo, Anfänge der Formalen Spieltheorie]

Beweisidee

Vollständige Induktion nach der maximalen Länge der Historien:
Wir gehen aus von einem Spielbaum mit der Eigenschaft, dass alle Historien endlich mit einer Länge unterhalb eine festen Zahl n sind. Ohne Einschränkung der Allgemeinheit kann man n minimal wählen. Sei h eine Entscheidungshistorie der Länge n-1 und k=P(h) der Spieler, der dieser Historie zugeordnet ist. Wir bestimmen in dem Teilspiel, das unterhalb h liegt (mit nur einem Spieler, nämlich k), ein Nash-Gleichgewicht a durch Dominanz: a maximiert die Nutzenfunktion für k. Wir eliminieren die anderen Aktionen bei h und verkürzen den entstandenen Spielbaum, so dass jetzt h terminal ist und wir setzen u(h):= u(h,a). Das wird für alle Entscheidungshistorien der Länge n-1 nacheinander durchgeführt, bis es keine Entscheidungshistorie der Länge n-1 mehr in dem sukzessive verkürzten Spielbaum gibt. Das entstandene Spiel hat nur noch Historien der Länge kleiner oder gleich n-1. Nach Induktionsvoraussetzung hat das Spiel ein teilspielperfektes Nash-Gleichgewicht. Dieses Nash-Gleichgewicht wird an den Entscheidunghistorien h des ursprünglichen Spiels, die zu terminalen Knoten wurden, ergänzt um die Aktionen a, die als Nash-Gleichgewichte gewählt wurden. Das entstehende Strategieprofil ist dann das gesuchte teilspielperfekte Nash-Gleichgewicht.

Bemerkung: Die Durchführung des Beweise wird etwas leichter, wenn die Induktion nach der Anzahl der Historien geführt wird. Der beschriebene Beweis funktioniert allerdings auch für bestimmte Spiele mit endlichem Horizont, in dem die Suprema der Nutzenfunktionen über gewisse Mengen von terminalen Historien immer angenommen werden.


Beweis zum Satz von Zermelo:(mit Rückwärtsinduktion)

Sei G =\left(N,H,P,u_i\right) ein extensives Spiel mit perfekter Information. Wir konstruieren ein teilperfektes Gleichgewicht von P durch Induktion auf \ l(G(h)) und wir definieren eine Funktion \ R auf jede Historie h \in H die eine Endhistorie mit allen Historien verbindet, und zeigen dass diese Historie ein teilspielperfektes Gleichgewicht des Teilspiels \ G(h).


Für \ l(G(h)=0 definiere \ R(h)=h.

Wir nehmen an, dass \ R(h) für alle \ h \in H definiert ist mit \ l(G(h))\le k, wobei \ k \ge 0.

Sei \ h^* Historie mit \ l(G(h^*))= k+1 und sei \ G(h^*))= i.

Da \ l(G(h^*))= k+1 haben wir \ l(G(h^*,a)) \le k, für alle \ a \in A(h^*).

Definiere jetzt \ s_i^*(h^*) als \ maxu_i(a) von \ R(h^*,a) über \ a \in A(h^*) und definiere \ R(h^*)=R(h^*,s_i^*(h^*)).

Mit Induktion haben wir jetzt die Strategie \ s \in G definiert.


Wir müssen noch zeigen dass diese Startegie \ s^* teilspielperfektes Gleichgewicht ist.


Beweis:


Falls \ s^* perfektes Gleichgewicht von \ G ist, dann ist es auch teilspielperfektes Gleichgewicht. Wir nehmen jetzt an dass \ s^* kein Gleichgewicht von \ G ist:

Wir nehmen an, Spieler \ i kann sich durch Abweichungen in Teilspiel \ G(h^') verbessern. Dann existiert eine neue Strategie \ s_i für denn Spieler \ i in \ G(h^'), und es gilt für Strategie \ s_i:


\ s_i(h)\not= (s_i^*|h^')(h)


wobei die Länge der Historie \ h, die nicht länger als Länge \ G(h^') ist. Da \ G, endlich, ist die Länge von \ h, auch endlich.


Für alle abweichende Strategien, in denen sich Spieler \ i verbessert, nehmen wir Strategie \ s_i für welche die Länge der Historie \ h(so dass \ s_i(h)\not= (s_i^*|h^')(h) ) minimal ist. Sei \ h^* die längste Historie \ h von \ G(h^') so dass \ s_i(h)\not= (s_i^*|h^')(h)


Dann ist die Anfangshistorie \ G(h^*) die einzige Historie in \ G(h-teilspielperfekt-^*) in welche die Aktion, beschrieben mit \ s_i, abweicht von Aktion beschrieben mit \ s^*|h^'.

Weiter ist \ s_i|h^* eine profitable Abweichung in \ G(h^*), sonst wäre profitable Abweichung in \ G(h^'), was ein Widerspruch ist zu \ s_i^*|h^'.


Diese Strategie \ s_i|h^* ist eine profitable Abweichung in \ G(h^*) die von \ s_i^*|h^' abweicht, nur in die Aktion die beschrieben ist nach der Historie \ G(h^*).


Formalisierung des Algorithmus

Meine Werkzeuge