Extensive Form

Aus Wikiludia
Wechseln zu: Navigation, Suche

Die extensive Form (oder dynamische Form) ist die Beschreibung eines Spiels, bei dem die Spielregeln so formuliert werden, dass die Spieler ihre Züge nacheinander ausführen. Das steht im Gegensatz zur Normalform eines Spiels, bei der alle Spieler gleichzeitig ziehen, ohne über den Ausgang der Züge der anderen Spieler informiert zu sein.

In diesem Beitrag werden einige verschiedene Ausprägungen des Begriffs der extensiven Form in einheitlicher Weise dargestellt und miteinander verglichen. Um den Vergleich zu ermöglichen, wird der Beitrag ausführlich auf verschiedene Definitionen eingehen und auch Wiederholungen zulassen.

Die Variationen zur extensiven Form haben ihren Ursprung in den verschiedenen grundlegenden Eigenschaften von Spielen, die zu unterschiedlichen Formulierungen führen. Zum Beispiel ist der einfachste Fall der, dass jeder Spieler genau einmal zum Zug kommt, und zwar in einer festen Reihenfolge nacheinander. Diese Situation findet sich in der Definition 1. In den nachfolgenden Definitionen 2 und 3 ist auch die Möglichkeit gegeben, dass einige Spieler mehrfach ziehen, in Definition 2 zunächst zeitlich geschichtet, in Definition 3 ganz allgemein. Weitere Formulierungen der extensiven Form werden gewählt, um den Fall der (nicht) vollkommenen Information, der (nicht) vollkommenen Erinnerung oder der (nicht) vollständigen Information zu erfassen, wie auch die Situationen zu beschreiben, die einen Einfluss von exogenen Wahrscheinlichkeiten des Spiels zulassen.

Auch der Fall von unendlich vielen Strategien sollte in der extensiven Form formuliert werden können.

Zu den Varianten gehören weiterhin die Stufenspiele, bei denen einerseits nacheinander gezogen wird aber auch die Beschreibung von Zügen erfolgt, die von einigen der Mitspieler simultan getätigt werden sollen, die Spiele mit gemischten Strategien und die Spiele in Bayes-Form.

Es werden in diesen Ausführungen keine interpretierten Modelle als Beispiele behandelt und auch keine Lösungskonzepte (z.B. Gleichgewichte) oder Existenzaussagen dazu vorgestellt.

In vielen Fällen wird bei der Beschreibung von Spielen in extensiver Form ein Spielbaum zugrundegelegt. Das wird in diesem Artikel ausführlich und sukzessiv dargestellt.

Eine andere wichtige Darstellungsform von extensiven Spielen basiert auf den Folgen von Aktionen, die jeweils die Historie der vorangegangenen Züge als Ausgangspunkt nehmen, erscheint zunächst abstrakter zu sein, ist aber letztlich einfacher, siehe: Extensive Form:Folgendarstellung.

Inhaltsverzeichnis

Spielbaum

Zur Veranschaulichung wird die extensive Form oft mit Hilfe eines Spielbaums beschrieben.


Definition: Ein Spielbaum B ist ein zusammenhängender (gerichteter) Graph ohne Schleifen, in dem einer der Knoten x0 als Wurzelknoten oder Anfangsknoten ausgezeichnet ist.
Dabei besteht ein gerichteter Graph B aus einer Menge K von Knoten und einer Menge A von Kanten mit der Eigenschaft, dass jede Kante a aus A genau einen Anfangsknoten b(a) aus K und einen Endknoten e(a) aus K hat.

Definition:

  1. Ein Pfad im Graphen B ist eine endliche Folge (a1, a2, ... ,am) bzw. eine unendliche Folge (am) von Kanten mit e(aj) = b(aj+1) oder b(aj) = e(aj+1) für alle j zwischen 1 und m-1 bzw. alle j.
  2. Der Graph B heißt zusammenhängend, wenn je zwei Knoten x und y des Graphen durch einen Pfad verbunden werden können. Das heißt, es gibt einen Pfad (a1, a2, ... ,am) mit b(a1) = x oder e(a1) = x und e(am) = y oder b(am) = y.
  3. Eine Schleife in einem Graphen B ist ein Pfad, der geschlossen ist, bei dem also der Anfangs- oder Endknoten der ersten Kante mit dem Anfangs- oder Endknoten der letzten Kante übereinstimmen: e(am) = b(a1), b(am) = b(a1), e(am) = b(a1) oder e(am) = e(a1). Darüber hinaus wird verlangt, dass der Pfad injektiv ist, d.h. hier, dass keine Kanten doppelt auftreten. (Ansonsten hätte man "triviale" Schleifen.)
  4. Ein Baum ist dann ein zusammenhängender Graph ohne Schleifen, in dem als Wurzel ein Knoten w mit der folgenden Eigenschaft ausgezeichnet ist: Der Anfangsknoten von w ist nicht Endknoten von irgendeiner anderen Kante aus A.

Es lässt sich leicht zeigen:
Fakt: Ein zusammenhängender Graph hat genau dann keine Schleifen, wenn je zwei Knoten des Graphen durch genau einen Pfad verbunden werden können.
Ein Graph ist genau dann ein zusammenhängender Graph ohne Schleifen, wenn je zwei Knoten des Graphen durch einen eindeutig bestimmten Pfad verbunden werden können.

Ein zusammenhängender, gerichteter Graph B ohne Schleifen kann auch als eine Knotenmenge K zusammen mit einer Relation A, also einer Teilmenge des Produktes KxK, verstanden werden: Die Projektionen b:A → K und e:A → K bestimmen zu jeder Kante, also zu jedem Paar (x,y) aus A, den Anfangsknoten x = b(a) und den Endknoten y = e(a). Und es gilt für (x,y) aus a stets, dass (y,x) nicht in A liegt.

Ungerichtete Graphen: In mancher Hinsicht ist es einfacher, den Spielbaum nicht als gerichteten Graphen zu verstehen, die "Richtungen" der Kanten ergeben sich am Ende durch die Wahl der Wurzel.


Definition eines ungerichteten Spielbaums:

  1. In dieser Sicht ist ein Graph G = (K,A) eine Menge von "Knoten" K mit einer Menge A von Mengen der Form {x,y} mit x,y aus K und x verschieden von y. A ist die Menge der (ungerichteten) "Kanten" des Graphen.
  2. Ein Pfad in G ist eine (endliche oder unendliche) Folge (am) von Kanten, so dass am und am+1 stets genau einen Knoten gemeinsam haben.
  3. Ein Graph ist zusammenhängend, wenn sich je zwei Knoten des Graphen durch einen Pfad verbinden lassen.
  4. Ein Baum ist ein zusammenhängender Graph, in dem ein Knoten w , der "Wurzel", ausgezeichnet ist, und der keine Schleifen, also keine nichttrivialen geschlossenen Pfade hat.

Ein solcher Baum ist dann am Ende in natürlicher Weise gerichtet: Zu jeder Kante k = {x,y} gibt es einen eindeutig bestimmten Pfad der in w beginnt und der w mit den beiden Knoten von k verbindet und in einem der beiden auch endet. Endet er in y, so setze b(k) = x und e(k) = y. Ansonsten umgekehrt.


Zur Endlichkeit: Ein Graph in dieser Allgemeinheit ist nicht notwendig endlich, denn weder K noch A müssen endlich sein. Hier unterscheidet sich diese Darstellung von den meisten Definitionen in den Lehrbüchern zur Spieltheorie: Wir wollen auch unendliche Graphen zulassen, damit sich ein Spiel in Normalform stets als Spiel in extensiver Form darstellen lässt: Im Falle von unendlichen Strategiemengen ergibt sich bei dem Übergang von der Normalform zur extensiven Form ein Spielbaum mit unendlich vielen Knoten und Kanten.

Ebene endliche Graphen: Ein endlicher Graph B hat nur endliche viele Knoten und Kanten. Ein endlicher Spielbaum kann als ebener Graph realisiert werden, für den die Knoten Punkte der Ebene und die Kanten gerichtete Geradenstücke sind, die die jeweiligen Anfangs- und Endknoten miteinander verbinden.

Die terminalen Knoten und die Entscheidungsmenge: In einem endlichen Spielbaum B werden die Knoten, die nur als Endknoten einer Kante nicht aber als Anfangsknoten einer anderen Kante auftreten als terminale Knoten bezeichnet, und die Menge aller dieser Knoten wird mit Z bezeichnet . Die restlichen Knoten in E:=K\Z heißen die Entscheidungsknoten.

Im Falle eines unendlichen Spielbaums kommen noch die (evtl.) unendlichen Pfade zur Menge Z hinzu, die als "virtuelle" Endknoten des jeweiligen unendlichen Pfades verstanden werden.

Zerlegung: Eine Zerlegung einer Menge X ist durch Untermengen Yj von X gegeben, deren Vereinigung X ist und die paarweise disjunkt sind, das heißt, der Durchschnitt von Yi und Yj ist stets leer für verschiedene Indizes i und j. Wir schreiben: X = Y1 + Y2 + ... + Ym, wenn die Zerlegung endlich ist und die Yj durch j aus {1,2, ... ,m} indiziert werden.

Die extensive Form mit endlichem Spielbaum

Extensive Form bei vollkommener Information

Es werden drei Definitionen bereitgestellt, die allgemeinste davon ist Definition 3, die auch dem üblichen Sprachgebrauch eines Spiels mit vollkommener Information in extensiver Form entspricht (vgl. Lektion 2 und Lektion 3).

Der einfachste Fall


Definition 1: Ein Spiel in extensiver Form ist im einfachsten Fall (mit n Spielern und n gleichförmigen Spielschritten) gegeben durch

  • eine endliche Menge {1, 2, ... , n} der Spieler,
  • einen endlichen Spielbaum B (mit Wurzelknoten x0 und der Menge der terminalen Knoten Z, siehe oben),
  • eine Zerlegung E = K1 + ... + Kn der Menge E = K\Z der Entscheidungsknoten (die Spielerzerlegung), die jedem Spieler seine Entscheidungsknoten zuordnet mit K1 = {x0} und der Eigenschaft, dass alle Kanten, die in Kj ihren Anfangsknoten haben, in Kj+1 ihren Endkonten haben, wenn j<n ist, und das alle Kanten, die in Kn ihren Anfangsknoten haben, in Z ihren Endknoten haben,
  • eine Auszahlungsfunktion u: Z → Rn.

Spielverlauf: Das Spiel vollzieht sich folgendermaßen:

  1. Das Spiel beginnt nun bei dem Knoten x0, indem der Spieler 1 (wegen K1 = {x0} ist 1 am Zug) sich für eine der von x0 ausgehenden Kanten, also für ein a1 entscheidet. Das Spiel gelangt so zu dem Knoten x1 := e(a1) in der Menge K2.
  2. Das Spiel befindet sich jetzt bei dem Knoten x1. Der Spieler 2 (da x1 in K2 liegt, ist 2 am Zug) entscheidet nun, indem er eine der von x1 ausgehenden Kanten, etwa a2 (mit b(a2) = x1) wählt. Dadurch gelangt das Spiel nach x2 := e(a2).
  3. Nach j-1 Zügen befindet sich das Spiel bei dem Knoten xj-1 und dieser Knoten liegt aufgrund der Definition der Spielerzerlegung in Kj. Spieler j ist am Zug und wählt eine von xj-1 ausgehende Kante aj als seine Aktion. Der zugehörige Knoten ist xj := e(aj).
  4. Durch sukzessive Wahl eines Zuges der Spieler j = 1,2, ... , n wird dadurch ein Pfad ausgezeichnet, der den Wurzelknoten mit einem Knoten z (=xn) aus Z verbindet. Die Auszahlung bzw. das Spielergebnis ist u(z) = (u1(z), u2(z), ... , un(z)):
  5. Der Spieler j erhält uj(z) als Auszahlung.

Aktionen, Aktionsmengen und Strategien: Jeder Entscheidungsknoten x liegt in einem Kj mit eindeutig bestimmtem Spielerindex j. Der Spieler j muss in x eine der ausgehenden Kanten aus Ax := {a : b(a) = x} = b-1(x) als Aktion (also als Spielzug) wählen. Diese Menge Ax heißt daher die Aktionsmenge zum Knoten x. Der Spieler j hat insgesamt die Menge Sj := {a : es gibt x aus Kj mit b(a) = x} = b-1(Kj) als Aktionsmenge oder Strategiemenge. Eine Strategie für den Spieler j besteht darin, dass er zu jedem Knoten seiner Knotenmenge Kj eine passende Aktion auswählt. Eine Strategie ist daher eine Funktion sj: Kj --> Sj mit der Bedingung, dass sj(x) stets in Ax liegen muss für alle x aus Kj. Ein Strategieprofil ist ein n-Tupel s = (s1, s1, ... , sn) von Strategien.

In diesem Spiel hat jeder Spieler insofern vollständige Information, als er neben dem Spielbaum und der Spielerzerlegung alle Auszahlungen kennt und auch weiß, dass die anderen Spieler diese Kenntnis haben und alle wissen, dass alle dieses Wissen haben, etc. Weiterhin hat jeder Spieler insofern vollkommene Information als er alle vorausgegangenen Züge kennt, wenn er an der Reihe ist, zu ziehen.

Extensive Form mit Zeitschichten


Definition 2: Ein Spiel in extensiver Form mit Zeitschichten ist gegeben durch

  • eine endliche Menge {1, 2, ... , n} der Spieler,
  • einen endlichen Spielbaum B,
  • eine Zerlegung E = K1 + ... + Kn der Menge E der Entscheidungsknoten (Spielerzerlegung), die jedem Spieler seine Entscheidungsknoten zuordnet mit K1 = {x0},
  • einer weiteren Zerlegung E = L1 + ... + Lm (die Zeitschichtenzerlegung), welche die Spielerzerlegung verfeinert (das bedeutet, dass es zu jedem k zwischen 1 und m ein j gibt, so dass Lk in Kj liegt), und L1 = {x0} erfüllt, sowie mit der Eigenschaft, dass alle Kanten, die in Lj ihren Anfangsknoten haben, in Lj+1 ihren Endkonten haben, wenn j<m ist, und dass alle Kanten, die in Lm ihren Anfangsknoten haben, in Z ihren Endknoten haben,
  • eine Auszahlungsfunktion u: Z → Rn.

Spielverlauf: Das Spiel vollzieht sich folgendermaßen:

  1. Das Spiel beginnt bei dem Knoten x0, indem der Spieler 1 (da L1 = {x0} in K1 liegt, ist 1 am Zug) sich für eine der von x0 ausgehenden Kanten, etwa für a1 entscheidet. Das Spiel gelangt so zu dem Knoten x1 := e(a1) in der Menge L2.
  2. Das Spiel befindet sich jetzt bei dem Knoten x1, der in L2 liegt. Es gibt einen eindeutig bestimmten Spieler j = j2, so dass L2 in Kj liegt. Der Spieler j ist daher am Zug und wählt eine der von x1 ausgehenden Kanten, etwa a2 (mit b(a2) = x1) wählt. Dadurch gelangt das Spiel nach x2 := e(a2) in der Zeitschicht L3.
  3. Nach k-1 Zügen befindet sich das Spiel bei dem Knoten xk-1 und dieser Knoten liegt in Lk. Zu k gibt es einen Spieler j = jk, so dass Lk in Kj liegt. j ist daher am Zug und wählt eine von xk-1 ausgehende Kante ak als seine Aktion. Der zugehörige Knoten ist xk := e(ak) und er liegt nach Definition der 'L-Zerlegung' in Lk+1.
  4. Durch sukzessive Wahl eines Zuges der Spieler, die auch mehrfach am Zug sein können, wird dadurch ein Pfad mit m Kanten ausgezeichnet, der den Wurzelknoten mit einem Knoten z (= xm) aus Z verbindet. Dieser Pfad repräsentiert die gesamte Historie des durchgeführten Spiels. Die Auszahlung bzw. das Spielergebnis ist u(z) = (u1(z), u2(z), ... , un(z)):
  5. Der Spieler j erhält uj(z) als Auszahlung.

Aktionen, Aktionsmengen und Strategien: Wie zuvor gilt, dass jeder Entscheidungsknoten x in einem Kj mit eindeutig bestimmtem Spielerindex j liegt. Der Spieler j hat in x als Spielzug eine Kante aus Ax := {a : b(a) = x} zu wählen. Ax heißt daher die Aktionsmenge zum Knoten x. Der Spieler j hat insgesamt die Menge Sj := {a : es gibt x aus Kj mit b(a) = x} als Strategiemenge. Eine (reine) Strategie für j ist eine Funktion sj: Kj → Sj mit der Bedingung, dass sj(x) stets in Ax liegen muss. Ein Strategieprofil ist ein n-Tupel s = (s1, s1, ... , sn) von Strategien.

In diesem Spiel hat wieder jeder Spieler vollständige Information wie auch vollkommene Information in dem Sinne, wie es weiter oben beschrieben wird.

Wenn m = n gilt, so folgt Kj = Lj nach geeigneter Umnummerierung. Ein Spiel nach Definition 2 mit m = n ist daher stets ein Spiel nach Definition 1.

Die allgemeine extensive Form (bei vollkommener Information)


Definition 3: Ein Spiel in extensiver Form ist gegeben durch

  • eine endliche Menge {1, 2, ... , n} der Spieler,
  • einen endlichen Spielbaum B,
  • eine Zerlegung E = K1 + ... + Kn der Menge der Entscheidungsknoten (Spielerzerlegung), die jedem Spieler seine Entscheidungsknoten zuordnet, wobei {x0} in K1 liegt,
  • eine Auszahlungsfunktion u: Z → Rn.

Spielverlauf: Das Spiel vollzieht sich folgendermaßen:

  1. Das Spiel beginnt bei dem Knoten x0, indem der Spieler 1 (da x0 in K1 liegt, ist 1 am Zug) sich für eine der von x0 ausgehenden Kanten, etwa für a1 entscheidet. Das Spiel gelangt so zu dem Knoten x1 := e(a1).
  2. Das Spiel befindet sich jetzt bei dem Knoten x1. Es gibt einen eindeutig bestimmten Spieler j = j2, so dass x1 in Kj liegt. Der Spieler j ist am Zug und wählt eine der von x1 ausgehenden Kanten, etwa a2 (mit b(a2) = x1). Dadurch gelangt das Spiel nach x2 := e(a2).
  3. Nach k-1 Zügen befindet sich das Spiel bei dem Knoten xk-1 und dieser Knoten ist ein terminaler Knoten aus Z oder er liegt in Kj für einen eindeutig bestimmten Spieler j = jk, denn die Kj bilden nach Definition eine Zerlegung von E. Im ersten Falle ist das Spiel beendet. Ansonsten ist der Spieler j am Zug und wählt eine von xk-1 ausgehende Kante ak als seine Aktion. Der zugehörige Knoten ist xk := e(ak).
  4. Durch sukzessive Wahl eines Zuges der Spieler, die auch mehrfach am Zug sein können, wird dadurch ein Pfad mit p Kanten ausgezeichnet, der den Wurzelknoten mit einem Knoten z (= xp) aus Z verbindet. Die Auszahlung bzw. das Spielergebnis ist u(z) = (u1(z), u2(z), ... , un(z)):
  5. Der Spieler j erhält uj(z) als Auszahlung.

Graphisch wird die Spielerzerlegung im Spielbaum dadurch zum Ausdruck gebracht, dass an jedem Entscheidungsknoten x die Nummer des Spielers j notiert, wenn x zu Kj gehört. Zum Beispiel:

                             o 1
                            / \
                           /   \
                          /     o 2
                         /     / \
                        /     /   \
                       /     /     o 1
                      /     /     / \
                     /     /     /   \
                    o     o     o     o
                        Beispiel 1


Aktionen, Aktionsmengen und Strategien: Wie zuvor gilt, dass jeder Entscheidungsknoten x in einem Kj mit eindeutig bestimmtem Spielerindex j liegt. Der Spieler j hat in x als Spielzug eine Kante aus Ax := {a : b(a) = x} zu wählen. Ax heißt daher die Aktionsmenge zum Knoten x. Der Spieler j hat insgesamt die Menge Sj := {a : es gibt x aus Kj mit b(a) = x} als Strategiemenge. Eine (reine) Strategie für j ist eine Funktion sj: Kj → Sj mit der Bedingung, dass sj(x) stets in Ax liegen muss. Ein Strategieprofil ist ein n-Tupel s = (s1, s1, ... , sn) von Strategien.

In diesem Spiel hat wieder jeder Spieler vollständige Information wie auch vollkommene Information in dem Sinne, wie es weiter oben beschrieben wird.



Extensive Form ohne vollkommene Information

Die Definitionen 1 - 3 sind zunehmend allgemeiner. Jedes Spiel nach Definition 1 ist auch eines nach Definition 2 mit Lj = Kj. Und jedes Spiel in extensiver Form nach Definition 2 ist auch eines nach Definition 3. Das sieht man, indem man die durch die Lj gegebene Zusatzstruktur der Zeitschichten einfach fortlässt.

Man beachte, dass bei den Spielen nach Definition 1 bzw. 2, die Pfade, die den Wurzelknoten mit einem der terminalen Knoten verbinden und damit die Historie einer möglichen regelkonformen Zugfolge beschreiben, immer die gleiche Länge n bzw. m haben. Das muss bei den Spielen nach Definition 3 nicht mehr gelten: Man kann einfache Spielbäume angeben, die das zeigen (siehe Beispiel 1).

In der Tat ist die Eigenschaft der konstanten Länge das wesentliche Unterscheidungsmerkmal zwischen Spielen nach Definition 2 und 3. Wenn im Falle der Definition 3 Konstanz vorliegt, so lässt sich durch Hinzufügen von Knoten und Kanten ein äquivalentes Spiel konstruieren, das der Definition 2 genügt.

Die bisher definierten Spiele in extensiver Form haben nicht nur vollständige Information sondern auch vollkommene Information, insofern, als jeder Spieler, der am Zug ist, über alle vorangehenden Züge informiert ist. Man kann sich das so vorstellen, dass er sich bei einem einzigen Knoten befindet, wenn er sich entscheiden muss.

Nicht mehr vollkommen ist die Information, wenn der Spieler zum Beispiel über den unmittelbar vorangehenden Zug keine Information hat, es für ihn also nicht klar ist, von welchem Knoten aus er entscheidet. Er weiß lediglich, dass er am Zug ist, und dass mehrere Knoten als Entscheidungsknoten in Frage kommen, von denen aus er zu entscheiden hat. Dieser Mangel an Information wird durch sogenannte Informationsbezirke (auch Informationsmengen genannt) modelliert, die sich ergeben, wenn die möglichen Knoten, die erreicht worden sein könnten, zusammengefasst werden. Das führt dazu, dass jede Menge Kj der Spielerzerlegung noch einmal in Informationsbezirke zerlegt ist: Kj = Ij,1 + Ij,2 +... + Ij,m(j). Für alle Knoten x aus dem Informationsbezirk Ij,p muss dann die Anzahl der Knoten in Ax dieselbe sein. Darüber hinaus müssen Ax und Ay vollständig miteinander identifiziert werden für alle Paare (x,y) von Entscheidungsknoten aus Ij,p. Das wird durch Bijektionen fx : Ax → Aj,p Bewirkt, wobei Aj,p eine feste Menge von möglichen 'Aktionen' für j im Informationsbezirk Ij,p ist.


Definition 4: Ein Spiel in extensiver Form ist gegeben durch

  • eine endliche Menge {1, 2, ... , n} der Spieler,
  • einen endlichen Spielbaum B,
  • eine Zerlegung E = K1 + .... + Kn der Entscheidungsknoten (Spielerzerlegung), die jedem Spieler seine Entscheidungsknoten zuordnet, wobei {x0} in K1 liegt,
  • eine Informationszerlegung Kj = Ij,1 + Ij,2 + ... + Ij,m(j) zu jedem j aus {1,2, ... ,n} und zu jedem Paar (j,p) ( j zwischen 1 und n und p zwischen 1 und m(j) ) eine Menge Aj,p von Aktionen zu Ij,p mit Bijektionen fx : Ax → Aj,p für alle x aus Ij,p,
  • eine Auszahlungsfunktion u: Z → Rn


Spielverlauf: Das Spiel vollzieht sich folgendermaßen:

  1. Das Spiel beginnt bei dem Knoten x0, indem der Spieler 1 (da x0 in K1 liegt, ist 1 am Zug) sich für eine der von x0 ausgehenden Kanten, etwa für a1 entscheidet. Das Spiel gelangt so zu dem Knoten x1 := e(a1).
  2. Das Spiel befindet sich jetzt bei dem Knoten x1. Es gibt einen eindeutig bestimmten Spieler j = j2, so dass x1 in Kj liegt. Der Spieler j ist am Zug und wählt eine Aktion a aus Aj,p, wenn x1 in Ij,p liegt. Dieser Aktion a entspricht über fx1 : Ax1 → Aj,p eine eindeutig bestimmte Kante a2 aus Ax1. Dadurch gelangt das Spiel nach x2 := e(a2).
  3. Nach k-1 Zügen befindet sich das Spiel bei dem Knoten xk-1 und dieser Knoten ist ein terminaler Knoten aus Z oder er liegt in Kj für einen eindeutig bestimmten Spieler j = jk, denn die Kj bilden nach Definition eine Zerlegung von E. Im ersten Falle ist das Spiel beendet. Ansonsten ist der Spieler j am Zug und wählt eine Aktion a aus Aj,p, wenn xk-1 in Ij,p liegt. Dieser Aktion a entspricht über fxk-1 : Axk-1 → Aj,p eine eindeutig bestimmte Kante ak aus Axk-1. Der zugehörige Knoten ist xk := e(ak).
  4. Durch sukzessive Wahl eines Zuges der Spieler, die auch mehrfach am Zug sein können, wird dadurch ein Pfad mit p Kanten ausgezeichnet, der den Wurzelknoten mit einem Knoten z (= xp) aus Z verbindet. Die Auszahlung bzw. das Spielergebnis ist u(z) = (u1(z), u2(z), ... , un(z)):
  5. Der Spieler j erhält uj(z) als Auszahlung.

In diesem Spiel hat wieder jeder Spieler vollständige Information, allerdings nicht mehr vollkommene Information, es sei denn alle Informationsbezirke sind einelementig.

Aktionen, Aktionsmengen und Strategien: Wie zuvor gilt, dass jeder Entscheidungsknoten x in einem Kj mit eindeutig bestimmtem Spielerindex j liegt. Darüber hinaus liegt x in einem eindeutig bestimmten Informationsbezirk Ij,p. Der Spieler j hat in x als Spielzug eine Aktion aus Aj,p zu wählen. Aj,p heißt daher die Aktionsmenge zur Informationmenge Ij,p. Der Spieler j hat insgesamt die Menge Aj := Aj,1 + Aj,2 + ... + Aj,m(j) als Menge von Aktionen. Eine (reine) Strategie für j ist eine Funktion sj: {Ij,1, Ij,2, ... , Ij,m(j)} → Aj mit der Bedingung, dass sj(Ij,p, ) stets in Aj,p liegen muss. Die Strategiemenge Sj von j ist die Menge aller dieser Abbildungen. Ein Strategieprofil ist ein n-Tupel s = (s1, s1, ... , sn) von Strategien und die Menge aller dieser Strategieprofile, also das Produkt der Strategiemengen Sj, ist der Strategieraum S des Spiels. Jedes Strategieprofil s aus S legt über den Spielverlauf einen eindeutig bestimmten Pfad des Spielbaums fest und damit auch einen terminalen Vektor z(s). Daher wird jedem Strategieprofil s eine Auszahlung u(s) := u(z(s)) zugeordnet. Diese wird auch als Erwartungswert bezweichnet. Damit gilt das im nächsten Abschnitt formulierte Resultat.

Normalform eines Spiels in extensiver Form

Satz: Jedes Spiel in extensiver Form kann auch in Normalform dargestellt werden.

Das ist zum Schluss des letzten Abschnitts vorweggenommen worden: Strategiemengen, Strategieraum und Auszahlungen ergeben sich direkt aus den Daten des Spiels in extensiver Form.

Die Begriffe für Spiele in Normalform wie Nash-Gleichgewicht, Beste Antwort, Dominanz, gemischte Strategie etc. übertragen sich somit auf die Spiele in extensiver Form.


Extensive Form mit Zufallspieler

Im Vergleich zum Begriff des Spieles in extensiver Form nach Definition 3 kommt noch ein Zufallsspieler hinzu, der durch den Index 0 repräsentiert wird. Der Zufallsspieler trifft keine strategische Entscheidungen, stattdessen passiert eine Aktion nach Wahrscheinlichkeiten, wenn der Spieler 0 am Zuge ist. Der Zufallspieler wird auch oft als Natur oder Umwelt bezeichnet


Definition 5: Ein Spiel in extensiver Form (mit Zufallsspieler) ist gegeben durch

  • eine endliche Menge {1, 2, ... , n} der Spieler,
  • einen endlichen Spielbaum B,
  • eine Zerlegung E = K0 + K1 + .... + Kn der Entscheidungsknoten (Spielerzerlegung), die jedem Spieler seine Entscheidungsknoten zuordnet, wobei {x0} in K1 liegt,
  • eine Informationszerlegung Kj = Ij,1 + Ij,2 + ... + Ij,m(j) zu jedem j aus {1,2, ... ,n} und zu jedem Paar (j,p) ( j zwischen 1 und n und p zwischen 1 und m(j) ) eine Menge Aj,p von Aktionen zu Ij,p mit Bijektionen fx : Ax → Aj,p für alle x aus Ij,p,
  • eine Wahrscheinlichkeitsverteilung auf Ax := b-1(x) zu jedem Knoten x aus K0,
  • eine Auszahlungsfunktion u: Z → Rn


Die extensive Form mit unendlichem Spielbaum

Trennt man sich von der Vorstellung eines ebenen endlichen Graphen, so kann man auch unendliche Graphen als Spielbäume zulassen: Sie müssen allerdings weiterhin gerichtet sein, einen ausgezeichneten Wurzelknoten x0 besitzen, der mit allen weiteren Knoten durch einen (gerichteten) Pfad verbunden ist, und sie dürfen keine Schleifen haben.

Definition 1 kann dann ohne Änderung übernommen werden. Das Ergebnis ist ein Spielbaum, in dem die Pfade von der Wurzel zu den terminalen Knoten wieder stets die Länge n haben, bei dem allerdings unendliche Entscheidungsmengen auftreten können.

Definition 2 kann ebenso übernommen werden.

Das gilt auch für die Definitionen 3, 4 und 5, wenn der Spielbaum keine unendlich langen Pfade hat.

Auf diese Weise lässt sich zum Beispiel in Umkehrung der Aussage das Satzes zeigen, dass jedes Spiel in Normalform eine extensive Form (mit nicht vollkommener Information) hat.

Zu der Definition 2 (wie auch zu den Definitionen 3, 4 und 5) gibt es eine interessante Verallgemeinerung, mit der dann auch unendlich oft iterierte Spiele beschrieben werden können. Dazu wird zunächst die Menge Z' der unendlich langen Pfade gebraucht:

Definition: Gegeben sei ein Spielbaum. Z' sei die Menge aller Folgen (ak) von Kanten des Spielbaums, die in der Wurzel x0 beginnen, d.h. b(a0) = x0 erfüllen, und die jeweils unmittelbare Verlängerung voneinander sind im Sinne von e(ak+1) = b(ak) für alle k aus der Menge N der natürlichen Zahlen.

Im Falle, dass Z' leer ist, kann Definition 2 direkt übernommen werden, wir sind in der oben bereits beschriebenen Situation. Wenn Z' nicht leer ist, so soll E in eine unendliche Anzahl von Mengen Lj zerlegt sein, mit j aus N, die ansonsten den Eigenschaften wie in Definition 2 genügen. Es gibt dann keine terminalen Knoten und die Nutzenfunktion wird auf Z' definiert: u: Z' → Rn.

Die analoge Modifikation der Definition muss man für Definition 3 durchführen, wenn es unendlich lange Pfade gibt. Das sieht so aus:



Definition 6: Ein Spiel in extensiver Form bei vollkommener Information (und mit unendlich langen Pfaden) ist gegeben durch

  • eine endliche Menge {1, 2, ... , n} der Spieler,
  • einen Spielbaum B,
  • eine Zerlegung E = K1 + ... + Kn der Menge der Entscheidungsknoten (Spielerzerlegung), die jedem Spieler seine Entscheidungsknoten zuordnet, wobei {x0} in K1 liegt,
  • eine Auszahlungsfunktion u: Z+Z' → Rn.

Der Spielverlauf in all diesen Spielen ist klar entsprechend der im vorangehenden Abschnitt gemachten Ausführungen. Es können allerdings Sequenzen mit unendlich vielen Zügen auftreten, die nie zu einem Ende kommen. Sie werden in der Definition dennoch mit einer Auszahlung belegt.

Auch bei Spielen mit nicht vollkommener Information sowie bei Spielen mit Zufallspieler lassen sich die Definitionen für den Fall von unendlichen Spielbäumen abwandeln.


Die extensive Form in der Folgendarstellung

Dieses Thema wird wegen der Länge des aktuellen Artikels in einem eigenen Artikel abgehandelt, auch wenn das Thema sehr eng mit der extensiven Form verbunden ist und die Folgendarstellung als Weiterentwicklung der extensiven Form mit unendlichem Spielbaum verstanden werden kann.

Stufenspiel

Auch dieses Thema wird wegen der Länge des vorliegenden Artikels in einem eigenen Artikel abgehandelt.
Von „http://wikiludia.math.lmu.de/wiki/index.php?title=Extensive_Form
Ansichten
Meine Werkzeuge
Navigation
Werkzeuge