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 1 Spielbaum 2 Die extensive Form mit endlichem Spielbaum 2.1 Extensive Form bei vollkommener Information 2.1.1 Der einfachste Fall 2.1.2 Extensive Form mit Zeitschichten 2.1.3 Die allgemeine extensive Form (bei vollkommener Information) 2.2 Extensive Form ohne vollkommene Information 2.3 Normalform eines Spiels in extensiver Form 2.4 Extensive Form mit Zufallspieler 3 Die extensive Form mit unendlichem Spielbaum 4 Die extensive Form in der Folgendarstellung 5 Stufenspiel

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: 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. 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. 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.) 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: 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. 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. Ein Graph ist zusammenhängend, wenn sich je zwei Knoten des Graphen durch einen Pfad verbinden lassen. 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 Y_j von X gegeben, deren Vereinigung X ist und die paarweise disjunkt sind, das heißt, der Durchschnitt von Y_i und Y_j ist stets leer für verschiedene Indizes i und j. Wir schreiben: X = Y₁ + Y₂ + ... + Y_m, wenn die Zerlegung endlich ist und die Y_j 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 x₀, indem der Spieler 1 (wegen K₁ = {x₀} ist 1 am Zug) sich für eine der von x₀ ausgehenden Kanten, also für ein a₁ entscheidet. Das Spiel gelangt so zu dem Knoten x₁ := e(a₁) in der Menge K₂.
2. Das Spiel befindet sich jetzt bei dem Knoten x₁. Der Spieler 2 (da x₁ in K₂ liegt, ist 2 am Zug) entscheidet nun, indem er eine der von x₁ ausgehenden Kanten, etwa a₂ (mit b(a₂) = x₁) wählt. Dadurch gelangt das Spiel nach x₂ := e(a₂).
3. Nach j-1 Zügen befindet sich das Spiel bei dem Knoten x_j-1 und dieser Knoten liegt aufgrund der Definition der Spielerzerlegung in K_j. Spieler j ist am Zug und wählt eine von x_j-1 ausgehende Kante a_j als seine Aktion. Der zugehörige Knoten ist x_j := e(a_j).
4. Durch sukzessive Wahl eines Zuges der Spieler j = 1,2, ... , n wird dadurch ein Pfad ausgezeichnet, der den Wurzelknoten mit einem Knoten z (=x_n) aus Z verbindet. Die Auszahlung bzw. das Spielergebnis ist u(z) = (u₁(z), u₂(z), ... , u_n(z)):
5. Der Spieler j erhält u_j(z) als Auszahlung.

Aktionen, Aktionsmengen und Strategien: Jeder Entscheidungsknoten x liegt in einem K_j mit eindeutig bestimmtem Spielerindex j. Der Spieler j muss in x eine der ausgehenden Kanten aus A_x := {a : b(a) = x} = b^-1(x) als Aktion (also als Spielzug) wählen. Diese Menge A_x heißt daher die Aktionsmenge zum Knoten x. Der Spieler j hat insgesamt die Menge S_j := {a : es gibt x aus K_j mit b(a) = x} = b^-1(K_j) als Aktionsmenge oder Strategiemenge. Eine Strategie für den Spieler j besteht darin, dass er zu jedem Knoten seiner Knotenmenge K_j eine passende Aktion auswählt. Eine Strategie ist daher eine Funktion s_j: K_j --> S_j mit der Bedingung, dass s_j(x) stets in A_x liegen muss für alle x aus K_j. Ein Strategieprofil ist ein n-Tupel s = (s₁, s₁, ... , s_n) 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 x₀, indem der Spieler 1 (da L₁ = {x₀} in K₁ liegt, ist 1 am Zug) sich für eine der von x₀ ausgehenden Kanten, etwa für a₁ entscheidet. Das Spiel gelangt so zu dem Knoten x₁ := e(a₁) in der Menge L₂.
2. Das Spiel befindet sich jetzt bei dem Knoten x₁, der in L₂ liegt. Es gibt einen eindeutig bestimmten Spieler j = j₂, so dass L₂ in K_j liegt. Der Spieler j ist daher am Zug und wählt eine der von x₁ ausgehenden Kanten, etwa a₂ (mit b(a₂) = x₁) wählt. Dadurch gelangt das Spiel nach x₂ := e(a₂) in der Zeitschicht L₃.
3. Nach k-1 Zügen befindet sich das Spiel bei dem Knoten x_k-1 und dieser Knoten liegt in L_k. Zu k gibt es einen Spieler j = j_k, so dass L_k in K_j liegt. j ist daher am Zug und wählt eine von x_k-1 ausgehende Kante a_k als seine Aktion. Der zugehörige Knoten ist x_k := e(a_k) und er liegt nach Definition der 'L-Zerlegung' in L_k+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 (= x_m) aus Z verbindet. Dieser Pfad repräsentiert die gesamte Historie des durchgeführten Spiels. Die Auszahlung bzw. das Spielergebnis ist u(z) = (u₁(z), u₂(z), ... , u_n(z)):
5. Der Spieler j erhält u_j(z) als Auszahlung.

Aktionen, Aktionsmengen und Strategien: Wie zuvor gilt, dass jeder Entscheidungsknoten x in einem K_j mit eindeutig bestimmtem Spielerindex j liegt. Der Spieler j hat in x als Spielzug eine Kante aus A_x := {a : b(a) = x} zu wählen. A_x heißt daher die Aktionsmenge zum Knoten x. Der Spieler j hat insgesamt die Menge S_j := {a : es gibt x aus K_j mit b(a) = x} als Strategiemenge. Eine (reine) Strategie für j ist eine Funktion s_j: K_j → S_j mit der Bedingung, dass s_j(x) stets in A_x liegen muss. Ein Strategieprofil ist ein n-Tupel s = (s₁, s₁, ... , s_n) 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 K_j = L_j 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 x₀, indem der Spieler 1 (da x₀ in K₁ liegt, ist 1 am Zug) sich für eine der von x₀ ausgehenden Kanten, etwa für a₁ entscheidet. Das Spiel gelangt so zu dem Knoten x₁ := e(a₁).
2. Das Spiel befindet sich jetzt bei dem Knoten x₁. Es gibt einen eindeutig bestimmten Spieler j = j₂, so dass x₁ in K_j liegt. Der Spieler j ist am Zug und wählt eine der von x₁ ausgehenden Kanten, etwa a₂ (mit b(a₂) = x₁). Dadurch gelangt das Spiel nach x₂ := e(a₂).
3. Nach k-1 Zügen befindet sich das Spiel bei dem Knoten x_k-1 und dieser Knoten ist ein terminaler Knoten aus Z oder er liegt in K_j für einen eindeutig bestimmten Spieler j = j_k, denn die K_j 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 x_k-1 ausgehende Kante a_k als seine Aktion. Der zugehörige Knoten ist x_k := e(a_k).
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 (= x_p) aus Z verbindet. Die Auszahlung bzw. das Spielergebnis ist u(z) = (u₁(z), u₂(z), ... , u_n(z)):
5. Der Spieler j erhält u_j(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 K_j 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 K_j mit eindeutig bestimmtem Spielerindex j liegt. Der Spieler j hat in x als Spielzug eine Kante aus A_x := {a : b(a) = x} zu wählen. A_x heißt daher die Aktionsmenge zum Knoten x. Der Spieler j hat insgesamt die Menge S_j := {a : es gibt x aus K_j mit b(a) = x} als Strategiemenge. Eine (reine) Strategie für j ist eine Funktion s_j: K_j → S_j mit der Bedingung, dass s_j(x) stets in A_x liegen muss. Ein Strategieprofil ist ein n-Tupel s = (s₁, s₁, ... , s_n) 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 L_j = K_j. Und jedes Spiel in extensiver Form nach Definition 2 ist auch eines nach Definition 3. Das sieht man, indem man die durch die L_j 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 K_j der Spielerzerlegung noch einmal in Informationsbezirke zerlegt ist: K_j = I_j,1 + I_j,2 +... + I_j,m(j). Für alle Knoten x aus dem Informationsbezirk I_j,p muss dann die Anzahl der Knoten in A_x dieselbe sein. Darüber hinaus müssen A_x und A_y vollständig miteinander identifiziert werden für alle Paare (x,y) von Entscheidungsknoten aus I_j,p. Das wird durch Bijektionen f_x : A_x → A_j,p Bewirkt, wobei A_j,p eine feste Menge von möglichen 'Aktionen' für j im Informationsbezirk I_j,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 x₀, indem der Spieler 1 (da x₀ in K₁ liegt, ist 1 am Zug) sich für eine der von x₀ ausgehenden Kanten, etwa für a₁ entscheidet. Das Spiel gelangt so zu dem Knoten x₁ := e(a₁).
2. Das Spiel befindet sich jetzt bei dem Knoten x₁. Es gibt einen eindeutig bestimmten Spieler j = j₂, so dass x₁ in K_j liegt. Der Spieler j ist am Zug und wählt eine Aktion a aus A_j,p, wenn x₁ in I_j,p liegt. Dieser Aktion a entspricht über f_x1 : A_x1 → A_j,p eine eindeutig bestimmte Kante a₂ aus A_x1. Dadurch gelangt das Spiel nach x₂ := e(a₂).
3. Nach k-1 Zügen befindet sich das Spiel bei dem Knoten x_k-1 und dieser Knoten ist ein terminaler Knoten aus Z oder er liegt in K_j für einen eindeutig bestimmten Spieler j = j_k, denn die K_j 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 A_j,p, wenn x_k-1 in I_j,p liegt. Dieser Aktion a entspricht über f_xk-1 : A_xk-1 → A_j,p eine eindeutig bestimmte Kante a_k aus A_xk-1. Der zugehörige Knoten ist x_k := e(a_k).
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 (= x_p) aus Z verbindet. Die Auszahlung bzw. das Spielergebnis ist u(z) = (u₁(z), u₂(z), ... , u_n(z)):
5. Der Spieler j erhält u_j(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 K_j mit eindeutig bestimmtem Spielerindex j liegt. Darüber hinaus liegt x in einem eindeutig bestimmten Informationsbezirk I_j,p. Der Spieler j hat in x als Spielzug eine Aktion aus A_j,p zu wählen. A_j,p heißt daher die Aktionsmenge zur Informationmenge I_j,p. Der Spieler j hat insgesamt die Menge A_j := A_j,1 + A_j,2 + ... + A_j,m(j) als Menge von Aktionen. Eine (reine) Strategie für j ist eine Funktion s_j: {I_j,1, I_j,2, ... , I_j,m(j)} → A_j mit der Bedingung, dass s_j(I_j,p, ) stets in A_j,p liegen muss. Die Strategiemenge S_j von j ist die Menge aller dieser Abbildungen. Ein Strategieprofil ist ein n-Tupel s = (s₁, s₁, ... , s_n) von Strategien und die Menge aller dieser Strategieprofile, also das Produkt der Strategiemengen S_j, 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 x₀ 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 (a_k) von Kanten des Spielbaums, die in der Wurzel x₀ beginnen, d.h. b(a₀) = x₀ erfüllen, und die jeweils unmittelbare Verlängerung voneinander sind im Sinne von e(a_k+1) = b(a_k) 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 L_j 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' → Rⁿ.

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.