Extensive Form:Folgendarstellung

Aus Wikiludia
Wechseln zu: Navigation, Suche

Die extensive Form eines Spiels kann auf verschiedene Weise dargestellt werden. Sehr beliebt, weil auch sehr anschaulich, ist die Verwendung eines Spielbaums, auch wenn der Spielbaum nicht wirklich essentiell für die Begriffsbildung ist. Einige Varianten zum Begriff extensive Form findet man in dem gleichnamigen Artikel Extensive Form, sowohl mit endlichem als auch mit unendlichem Spielbaum.

In diesem Beitrag wird die abstraktere aber letztlich einfachere Darstellung von Spielen in extensiver Form mittels Folgen vorgestellt.

Inhaltsverzeichnis

Extensive Form in der Folgendarstellung mit vollkommener Information

Definition 1: Ein Spiel in extensiver Form mit vollkommener Information ist gegeben durch

  • eine endliche Menge M = {1, 2, ... , N} der Spieler,
  • eine Menge H von Folgen mit den Eigenschaften:
    • die leere Folge ist ein Element von H,
    • ist (ak)(0<k<M) eine endliche Folge aus H und L<M, so ist auch (ak)(0<k<L) ein Element von H,
    • ist (ak)(0<k) eine unendliche Folge aus H und L eine natürliche Zahl, so ist auch (ak)(0<k<L) ein Element von H,
    • ist (ak)(0<k) eine unendliche Folge, für die (ak)(0<k<L) ein Element von H ist für alle L, dann ist auch (ak)(0<k) in H,

(H ist die Menge der Historien.)

  • eine Spielerfunktion P: E → M, die jeder Entscheidungsfolge h aus E den Spieler P(h) = k aus M zuordnet, der am Zug ist. Dabei ist eine Entscheidungsfolge nach Definition eine endliche Folge (ak)(0<k<L) aus H, zu der es ein aL gibt, so dass (ak)(0<k<L+1) ein Element aus H ist. E ist die Menge der Entscheidungsfolgen und Z := H\E ist die Menge der terminalen Folgen.

Offenbar fehlt noch die Auszahlungsfunktion, wenn man den Vergleich mit der Definition 3 in dem Artikel zur extensiven Form anstellt.

Es ist aber durchaus sinnvoll, die Auszahlung nicht als Bestandteil der Form des Spieles zu betrachten, die Form also ganz separat zu verstehen als ein Regelwerk, nach dem die Spielzüge abzulaufen haben. Eine Form wird in diesem Sinne erst zu einem Spiel, wenn die Bewertung der terminalen Folgen Z und damit der Vergleich der verschiedenen Ergebnisse des Spieles erfolgen kann. Die Bewertung der Ergebnisse lässt sich typischerweise durch eine Auszahlungsfunktion uj : Z → R für jeden Spieler j beschreiben. Sie kann aber auch allgemeiner gegeben werden durch eine Ordnungsrelation Präferenzrelation auf Z (für jeden Spieler j).

Die Trennung von Form und Präferenz gibt im übrigen auch Sinn bei der extensiven Form des Spiels, die sich des Spielbaums bedient, und ebenso bei der strategischen Form des Spiels.

Im übrigen ist die Einbeziehung der leeren Folge in H ein Trick, der garantiert, dass wir einen klaren Ausgangspunkt haben, denn die leere Folge ist Anfangsstück von jeder Folge. Daher 'beginnen' alle Folge in H mit der leeren Folge!

Strategie:

Definition 2:
1° Eine Aktion zur Folge h = (an)(0<n<L) aus E ist jedes Element aL, für das (an)(0<n<L+1) eine Folge aus H ist.
2° Die zur Historie h gehörige Aktionsmenge ist A(h) = Ah := {aL : (an)(0<n<L+1) liegt in H}.
3° Im Falle P(h) = k hat der Spieler k daher die Aktionen aus Ah als Entscheidungsmöglichkeiten, und eine Strategie s = sk des Spielers k ist die Wahl einer Aktion a = sk(h) zu jedem h aus Ek := {h aus E mit P(h) = k}.

Jede Strategie sk kann also auch als das Element

 \left(s_k(h)\right)_{h\in E_k} \in  \prod_{h\in E_k} A_h

verstanden werden unabhängig davon, ob die Aktionsmenge Ah endlich oder unendlich ist.

Die Menge der Strategien für den Spieler k sei  \mathcal S_k, und es sei

 \mathcal S := \mathcal S_1 \times \ldots \times \mathcal S_N = \prod_{k=1}^N \mathcal S_k

der zugehörige Strategieraum.

Folgendarstellung versus Darstellung mittels eines Spielbaums

Die Menge H der Historien in einem extensiven Spiel stellt einen abstrakten Spielbaum dar (vgl. Extensive Form) und umgekehrt. Wir beschreiben den Spielbaum G(H) zu einem Spiel mit der Menge H der Historien:
Die Menge der Knoten K = K(H) sei die Menge der endlichen Folgen aus H mit der leeren Folge als Wurzel w. Die Menge E der Entscheidungshistorien ist dann in K enthalten. Eine Kante von h aus E nach (h,a) für a aus Ah ist durch {h,(h,a)} gegeben: A ist einfach die Menge der {h,(h,a)} mit h aus E und a aus Ah. Man prüft nach, dass dadurch ein (ungerichteter) Baum G(H) definiert wird.
Da umgekehrt jeder Baum B im Sinne der Definition in Extensive Form in eindeutiger Weise eine Menge H = H(B) von Folgen mit den oben geforderten Eigenschaften definiert (H = H(B) ist die Menge der endlichen und unendlichen Pfade, die bei w beginnen), erweisen sich die Definitionen von extensiven Spielen in Extensive Form und in dem aktuellen Artikel als äquivalent.

Unvollkommene Information

Auch Zufallsspieler und unvollkommene Information lassen sich in die Definition einbinden (vgl. Extensive Form):


Definition 3: Ein Spiel in extensiver Form ist gegeben durch

  • eine endliche Menge {1, 2, ... , N} der Spieler, 0 ist gegebenenfalls Zufallsspieler,
  • eine Menge H von Folgen mit den Eigenschaften:
    • die leere Folge ist ein Element von H,
    • ist (an)(0<n<M) eine endliche Folge aus H und L<M, so ist auch (an)(0<n<L) ein Element von H,
    • ist (an)(0<n) eine unendliche Folge aus H und L eine natürliche Zahl, so ist auch (an)(0<n<L) ein Element von H,
    • ist (an)(0<n) eine unendliche Folge, für die (an)(0<n<L) ein Element von H ist für alle L, dann ist auch (an)(0<n) in H,
  • eine Spielerfunktion P: E → {0,1,2, ... ,N}, die jeder Entscheidungsfolge den Spieler zuordnet, der am Zug ist. Dabei ist eine Folge (an)(0<n<L) aus H eine Entscheidungsfolge, wenn sie endlich ist und es ein aL gibt, so dass (an)(0<n<L+1) ein Element aus H ist. E ist die Menge der Entscheidungsfolgen und Z := H\E ist die Menge der terminalen Folgen. Es wird noch verlangt, dass die leere Folge nicht schon eine terminale Folge ist, dass also die leere Folge in E liegt. A(h) = Ah sei für h = (an)0<n<L wie zuvor (vgl. Definition 2) die Aktionsmenge {aL : (an)0<n<L+1 ist in H}.
  • eine Wahrscheinlichkeitsverteilung fh = f( |h) auf jedem Ah mit P(h) = 0 ('0' ist der Zufallspieler),
  • zu jedem Spieler k aus {1,2, ... ,n} eine Zerlegung von Ek := {h aus E : P(h) = k} in Informationsbezirke (auch Informationsmengen genannt) Il(k) mit der Eigenschaft, dass stets A(h) = A(h') für h,h' aus Il(k) gilt. Mit A(Il(k)) = A(h) wird dann die entsprechende Aktionsmenge bezeichnet.


Bemerkung: Der Zufallsspieler muss nicht immer Teil des Spiels sein, viele Spiele ohne vollkommene Information haben keine Zufallszüge. Zur Modellierung einer echten unvollständigen Information im Rahmen eines extensiven Spiels (mit vollständiger Information aber ohne vollkommene Information) wird allerdings der Zufall gebraucht.

Spielverlauf

1. Das Spiel beginnt bei der leeren Folge  h=\emptyset \in H mit der folgenden Alternative: P(h) = 0 oder P(h) > 0.

  • Im Falle P(h) = k > 0 wählt der Spieler k in seinem Zug ein Element a = a1 aus der Aktionsmenge Ah und das Spiel befindet sich nach diesem Zug (in dem Zustand bzw.) in der Historie h1 = (a) = (a1).
  • Im Falle P(h) = 0 spielt der Zufall: Mit der Wahrscheinlichkeit fh(a) = f(a|h) wählt er a = a1 aus der Aktionsmenge Ah und das Spiel hat nach diesem Zug (mit der Wahrscheinlichkeit ph(a)) die Historie h1 = (a) = (a1). (In diesem Fall tritt also eine Verzweigung statt, wenn die Wahrscheinlichkeit keine Wahrscheinlichkeit ist, die genau einen Punkt mit der Wahrscheinlichkeit 1 belegt.)

2. Nach n Zügen sei das Spiel bei der Historie hn = (a1, ... ,an) angekommen.
Es liegt dann zunächst die folgende Alternative vor: hn liegt in Z oder hn liegt in E.

  • Im Falle, dass hn terminal ist, also in Z liegt, endet das Spiel mit der Historie hn als Ergebnis, oder Endstand, oder Spielpfad, gegebenenfalls randomisiert mit den auftretenden Wahrscheinlichkeiten f(am+1|hm), m < n. Ebenso spricht man von u(hn) als dem Ergebnis oder der Auszahlung, gegebenenfalls randomisiert. (Im Falle von unendlichen Aktionsmengen werden die Aktionsmengen als kompakt vorausgesetzt und die Randomisierung muss mit Integralen ausgedrückt werden.)
  • Im Falle, dass hn eine Entscheidungshistorie ist, tritt wieder eine Alternative auf: P(hn) = 0 oder P(hn) > 0.
    • Wenn P(hn) = k > 0 gilt, so liegt hn zunächst in der Menge Ek, die in die Informationsmengen Il(k) zerlegt ist. Also liegt hn in genau einer dieser Informationsmengen Il(k). (k weiß nicht, dass hn der aktuelle Spielstand ist, k weiß lediglich, dass Il(k) erreicht worden ist und er am Zug ist.) Der Spieler k wählt als seinen Zug eine Aktion a = an+1 aus der Aktionsmenge A(Il(k)), und das Spiel hat nun aktuell die Historie hn+1 = (a1, ... ,an,an+1).
    • Im Falle P(hn) = 0 wird durch den Zufall mit der Wahrscheinlichkeit f(a|hn) die Aktion a = an+1 aus der Aktionsmenge A(hn) ausgewählt. Das Spiel hat nach diesem Zug (mit der Wahrscheinlichkeit f(an+1|hn) ) die Historie hn+1 = (a1, ... ,an,an+1).

3. Wenn (in einer der durch den Zufall bedingten Verzweigungen) durch Iteration von 2. eine unendliche Folge h =(an) auftreten sollte, so liefert diese terminale Folge das Ergebnis, Endstand, bzw. u(h), gegebenenfalls wieder randomisiert. Dabei kann es nötig sein, eine Konvergenzbedingung einzuführen.

Strategien und Normalform

Definition 4:
Eine Strategie s = sk des Spielers k ist in dieser allgemeinen Situation eine Abbildung, die jeder Informationsmenge I der Zerlegung von Ek eine Aktion a = sk(I) aus A(I) zuordent. Wenn  \mathcal J_k die Menge der Informationsmengen in Ek bezeichnet, so ist sk eine Abbildung auf  \mathcal J_k mit Werten in der Vereinigung der Informationsmengen:

 s_k : \mathcal J_k \to \bigcup \{A(I) : I \in \mathcal J_k\} mit  s_k(I) \in A(I)\,,\, I\in \mathcal J_k.

Jede Strategie sk kann also auch als das Element

 \left(s_k(I)\right)_{I\in \mathcal J_k} \in  \prod_{I\in \mathcal J_k} A(I)

verstanden werden unabhängig davon, ob die Aktionsmenge A(I) endlich oder unendlich ist.

Die Menge der Strategien für den Spieler k sei  \mathcal S_k, und es sei

 \mathcal S := \mathcal S_1 \times \ldots \times \mathcal S_N = \prod_{k=1}^N \mathcal S_k

der zugehörige Strategieraum.

Der oben beschriebene Spielverlauf legt zu jeder Strategiekombination ein Ergebnis (Outcome, Endstand, Erwartungswert) fest. Wir wollen diese Festlegung im Folgenden für endliche Spiele ausführlich darstellen, auch um zu präzisieren, was wieter oben unter der Randomisierung über die vorhandenen Wahrscheinlickeiten zu verstehen ist.

Ergebnis, Erwartungswert:
Sei also Γ = (M,H,P,J,f,u) ein endliches, extensives Spiel, das bedeutet, dass H eine endliche Menge ist.
1° Es sei zunächst  s = (s_1,s_2, \ldots ,s_N) \in \mathcal S eine reine Strategiekombination. Dann wird jeder terminalen Historie h aus Z eine Wahrscheinlichkeit p(h) zugeordnet, die die Wahrscheinlichkeit ist, mit der h erreicht wird: Sei  h = (a^1,a^2, \ldots ,a^n) und setze  h_\nu := (a^1, \ldots ,a^\nu)\,,\, \nu = 1,2, \ldots ,n\,.. Dann wird

 p(h) := \prod_{\nu=1}^n p_\nu(h_\nu)

definiert, wobei

  • im Falle  P(h_{\nu-1}) = 0\,:  p_\nu(h_\nu) := f(a^\nu |h_{\nu-1})\,,
  • im Falle P(hν − 1) = k > 0 (echter Spieler aus der Spielermenge M):
    •  p_\nu(h_\nu) := 1 \,, falls aν = sk(I) für die eindeutig bestimmte Informationsmenge  I \in \mathcal J_k mit  h_{\nu -1} \in I\,,
    •  p_\nu(h_\nu) := 0 \,, falls  a^\nu \neq s_k(I)\,.

Das Ergebnis (der Endstand, der Ausgang) ist jetzt

 h(s)=z(s): = \sum_{h\in Z} p(h)h

und der Erwartungswert der Auszahlung (das Ergebnis, der Ausgang, Outcome) ist entsprechend

 u(s) := \sum_{h\in Z} p(h)u(h)\,.

2° Für gemischte Strategieprofile  \sigma = (\sigma_1,\sigma_2, \ldots ,\sigma_N) \in \Delta \mathcal S_1 \times \ldots \times \Delta \mathcal S_N analog: Wir haben  \sigma = \sum_{s\in\mathcal S} \pi(s) s mit geeigneten  \pi(s) \in \mathbb R und setzen

z(\sigma) : = \sum_{s\in \mathcal S} \pi(s) z(s) (Endstand)
u(\sigma) : = \sum_{s\in \mathcal S} \pi(s) u(s) (Erwartungswert)

mit z(s), u(s) wie in 1°.


Wir haben damit unter anderem gezeigt:

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

Die zu Γ assoziierte Normalform ist dann (M,\mathcal S,u) mit u wie in 1°.

Beispiel: Als Beispiel eines extensiven Spiels mit Zufallsspieler und mit unvollkommener Information kann das Kartenspiel dienen. In diesem Artikel ist auch die assoziierte Normalform angegeben.

Auf diese Weise kann man wieder unmittelbar definieren, was ein Nash-Gleichgewicht ist. Wichtiger sind allerdings die Verfeinerungen des Konzepts Nash-Gleichgewicht wie teilspielperfektes Gleichgewicht, sequentielles Gleichgewicht und perfektes Gleichgewicht.

Meine Werkzeuge