Spieltheorie - game theory: Extensive form games

Extensive form games (pdf file with images)

Gliederung:
0. Ziele
1. Einleitung
2. Wichtige Grundbegriffe
3. Perfect information extensive form games
4. Imperfect information extensive form games
5. Incomplete information extensive form games
6. Schlusswort
7. Zusammenfassung
8. Referenzen


1. Einleitung

Die Spieltheorie beschäftigt sich nicht nur mit der Beschreibung und Analyse von Spielen, sondern mit
der Konfliktsituation zwischen mehreren Beteiligten, die verschiedene Handlungsmöglichkeiten haben
und den Ausgang des Konflikts zu ihrem Gunsten beeinflussen können.
Anwendungsbereiche sind beispielsweise:
- Unternehmen, die um einen Markt konkurrieren
- politische Gruppen
- Gegner bei einem Kartenspiel
- Psychologisches Verhalten
- Tierverhalten
- Militärische Anwendungen
- Traffic balancing im Internet
- Zugriff von mehreren Benutzern auf beschränkte Ressourcen

Die Spieltheorie stellt eine Werkzeugsammlung zur Verfügung, um Ergebnisse (outcomes) für
konkurrierende Gegner vorherzusagen. Jede Aktion wirkt sich dabei auf die Auszahlungsbeträge
(payoffs) der anderen konkurrierenden Gegner aus.
Die Spieltheorie kann besonders dann erfolgreich eingesetzt werden, wenn die Anzahl der
Konkurrenten klein ist.
Die mathematische Komplexität wächst in der Regel NP-hart mit der Anzahl der konkurrierenden
Gegner – somit sind mit der wachsenden Zahl an Teilnehmern effiziente Algorithmen zur
Problemlösung notwendig.
Deshalb wird die Spieltheorie hauptsächlich in der Wirtschaft bei der Analyse von Industrien
eingesetzt, bei denen sich nur wenige Firmen einen Wettbewerb liefern. Jede Aktion einer Firma (wie
Änderungen in Preis, Produktionsmenge oder Marketing) hat eine direkte Auswirkung auf den
Umsatz aller konkurrierenden Firmen.


Vorgehensweise:

Zur mathematischen Modellierung muss zunächst ein Modell gebildet werden. Das Modell soll die
Situation, die Spieler, die Handlungsmöglichkeiten und Ziele möglichst real beschreiben.
Bei einem Gesellschaftsspiel mit festem Regelwerk ist diese Modellierung einfacher zu erstellen als
bei einer realen Situation, weil oft die Gewichtung für bestimmte Ereignisse vom Menschen selbst
abgeschätzt werden muss. Die Qualität der Ergebnisse eines Modells hängt also direkt von
dieser Abschätzung ab, was eine sehr vorsichtige Modellierung erfordet.
Um die verschiedenen Ausgänge und Strategien beurteilen und vergleichen zu können muss der
Gewinn und Nutzen für die Spieler am Ende des Spiels quantifizierbar sein. Das kann mithilfe
absoluter oder erwartbarer payoffs in Form von Geld, Kundenzufriedenheit oder Ansehen geschehen.
Zentrales Ziel der Spieltheorie ist neben der formellen Modellierung von Spielen die Analyse der
payoffs der einzelnen Spieler und die Entwicklung einer Strategie.
Bemerkung: Falls alle Spieler strikt ihre eigenes Ziel zur Gewinnmaximierung verfolgen, kann am
Spielende eine Situation entstehen, die für alle Spieler ungünstig ist (bsp.: Prisoner’s dilemma).
Die Rolle der Informatik in der Spieltheorie
In der Praxis sind Probleme in der Spieltheorie wesentlich komplexer als die in Lehrbücher zu
findenden Beispiele. Sowohl die Anzahl der Konkurrenten, die Anzahl der möglichen Spielzüge und
die Anzahl der zu betrachtenden Parameter sind in der Regel wesentlich höher – die Komplexität und
der Berechnungsaufwand steigt damit rapide an. In der Regel wird also ein Taschenrechner, Bleistift
und Papier nicht ausreichen um derartige Probleme mit angemessenem Zeitaufwand effektiv lösen zu
können.
Mithilfe der Informatik lassen sich die Methoden und Algorithmen der Spieltheorie automatisierten,
visualisieren, verifizieren und auswerten.
Man sollte aber immer im Hinterkopf behalten, dass die Qualität des Ergebnisses immer nur so gut
sein kann, wie die Qualität der Daten, mit denen das System gefüttert wird.


2. Wichtige Grundbegriffe

Arten der Spielrepräsentation
In der Spieltheorie gibt es zwei wichtige Arten der Spielrepräsentation:
- Normal form games
- Extensive form games
Bei normal form games treffen die Spieler ihre Entscheidungen zeitgleich.
Bei extensive form games treffen die Spieler ihre Entscheidungen zu unterschiedlichen Zeitpunkten.
Arten von Aktionen
In der Spieltheorie gibt es zwei Arten von Aktionen:
- pure actions
- mixed actions
Bei reinen Aktionen (pure actions) spielt jeder Spieler genau eine Aktion aus einer Menge von
verfügbaren Aktionen.
Bei gemischten Aktionen (mixed actions) spielt jeder Spieler jede Aktion mit einer gewissen
Wahrscheinlichkeit.
Arten von Informationen
Zwei Arten von Informationen spielen in der Spieltheorie eine Rolle:
- perfect information
- imperfect information
Bei einer perfekten Information hat der Spieler Wissen über die Entscheidungen der anderen Spieler.
Er kann somit seine Entscheidung in Abhängigkeit der Entscheidungen der anderen Spieler treffen.
Bei einer imperfekten Information hat er dieses Wissen nicht.


3. Perfect information extensive form games

Ein Spiel in Extensivform bezeichnet in der Spieltheorie ein Spiel, bei dem die Spieler zu
verschiedenen Zeitpunkten Entscheidungen treffen müssen und dabei die zuvor getätigten Züge
ihrer Gegenspieler kennen. Damit unterscheidet sich die Extensivform von der Normalform, bei der
sämtliche Spieler ihre Strategien gleichzeitig festlegen.
Ein Spiel in extensiver Form kann anhand einer Baumdarstellung repräsentiert werden. Diese
Baumdarstellung macht auch die zeitliche Struktur deutlich.
Im folgenden werden wir und dem Spezialfall der perfect information extensive form games widmen
und dann später zum allgemeineren Fall der imperfect information extensive form games übergehen.
Wir werden uns des weiteren auf endliche Spiele beschränken, also auf Spiele mit endlichen Bäumen.
Definition (informell): Perfect information extensive form games
Ein perfect information extensive form game ist ein Baum im Sinne der Graphentheorie. Jeder Knoten
repräsentiert eine Entscheidung von einem der Spieler, jede Kante repräsentiert eine mögliche Aktion.
Die Blätter repräsentieren die finalen Spielausgänge. Ihnen ist eine Nutzenfunktion zugeordnet (der
payoff).

Definition (mathematisch): Perfect information extensive form games

• Ein (endliches) perfect-information game (in extensiver form) ist ein Tupel G = (N, A, H, Z, x,
p, o, u), wobei
• N ist eine Menge von Spielern
• A = (A1,…., An) ist eine Menge von Aktionen für jeden Spieler
• H ist eine Menge von nicht-Endknoten
• Z ist eine Menge von finalen Knoten, Z und H sind disjunkt
• x: H -> 2A ist die Aktionsfunktion, welche jeder Knoten eine Menge von möglichen Aktionen
zuordnet
• p: H -> N ist die Spieler Funktion, welche jedem nicht-finalen Knoten einen Spieler i aus der
Menge N zuordnet, der an diesem Knoten eine Entscheidung trifft
• o: H x A -> H vereinigt mit Z ist die Nachfolgerfunktion, die einen Auswahlknoten und eine
Aktion zu einem neuen Auswahlknoten oder Endknoten so zuordnet, dass für alle h1, h2 aus
der Menge H und a1, a2 aus der Menge A gilt: Wenn o(h1,a2) = o(h2,a2), dann ist h1= h1 und a1
= a2 .
• u = (u1,…,un), wobei ui : Z -> R eine Gewichtungsfunktion für den Spieler i am Endknoten Z ist.
Weil die Auswahlknoten einen Baum bilden, können wir eindeutig einen Knoten Anhand seines
Pfades identifizieren. Dieser Pfad besteht aus einer Sequenz von Entscheidungen vom der
Wurzel bis zum Auswahlknoten.


Beispiel 1:

Ein Beispiel für ein perfect information extensive form game ist das Sharing game:
Der Bruder und die Schwester sollen zwei identische, unteilbare Geschenke von ihren Eltern unter
sich aufteilen.
Zuerst schlägt der Bruder eine Aufteilung vor. Es gibt dabei 3 Möglichkeiten die Geschenke
untereinander aufzuteilen:
- Er behält beide
- Jeder bekommt ein Geschenk
- Die Schwester bekommt beide
Wenn sie die vom Bruder beschlossene Aufteilung annimmt, bekommt jeder die zugewiesenen
Geschenke. Nimmt sie die Aufteilung nicht an, bekommt keiner ein Geschenk.
Hinweis:
Im Gegensatz zum normal form game treffen hier beide Parteien ihre Entscheidungen nacheinander.
Prisoners dilemma: Der Gefangene 1 weiß zum Zeitpunkt seiner Aussage nicht, wie sich der
Gefangene 2 verhält. Daher kann er in seine Entscheidung die Entscheidung vom Gefangenen 2 nicht
einfließen lassen. Beide treffen somit ihre Entscheidung gleichzeitig und unabhängig voneinander.
Sharing game: Die Schwester weiß, wie der Bruder sich entscheiden hat. Sie trifft ihre Entscheidung
nachdem er eine Auswahl getroffen hat und trifft ihre Entscheidung in Abhängigkeit von seiner.
Eine mögliche Baumrepräsentation könnte wie folgt aussehen:


Beispiel 2:

Stufe 1: Firma A entscheidet, ob sie in den Markt eintritt oder nicht
Stufe 2: Firma B befindet sich entweder in der Situation mit A zu konkurrieren (Konten IIe) oder in
Monopol Stellung (Konten IIne)
An jedem der Knoten hat Firma B eine Knoten spezifische Aktionsmenge:
AIIe
B = {STAY, EXIT}
AIIne
B = {STAY, EXIT}
Definition (informell): Strategie
Eine Strategie für einen Spieler ist ein vollständiger Plan (eine Liste) von Aktionen.
Obwohl im vorangegangenen Beispiel sich Spieler B entweder in Knoten IIn oder IIn befindet,
spezifiziert eine Strategie für diesen Spieler, was er in jedem der Beiden Konten macht.
Es gibt also 4 mögliche Strategien:
(ENTER,STAY), (ENTER,EXIT), (NOT ENTER,STAY), (NOT ENTER,EXIT)
Spieltheorie - extensive form games Markus Feil 9
Beispiel:
Eine Strategie spezifiziert für den Spieler, was er in jedem der Beiden Konten macht.
Beispiel für die Strategie von zwei Spielern:

Normalformdarstellung von extensive form games
Lemma:
Jedes perfect information game kann in ein normal form game umgewandelt werden.
Firma B
SS SE ES EE
ENTER -2 -Firma A 2 -2 -2 3 -1 3 -1
NOT ENTER 0 3 0 -1 0 3 0 -1
In diesem Spiel gibt es 3 Nash Gleichgewichte:
(E, (ES)), (E,(EE)), (N, SS))
Beweis: Best response functions:
RA (aB) =
• N falls aB = SS
• N falls aB = SE
• E falls aB = ES
• E falls aB = EE
RB (aA) =
• ES, EE falls aA = E
• SS, ES falls aA = N
In unserem Beispiel gibt es also mehrere Nash Gleichgewichte. Unser Ziel ist es jedoch, ein Konzept
zu finden, das die Menge der Nash Gleichgewichte verkleinert.
Spieltheorie - extensive form games Markus Feil 11
Subgame perfect equilibrium
Wenn wir die Nash equilibrium Ergebnisse vom vorangegangen Beispiel betrachten, kann man sich
folgende Frage stellen:
Welche Nash-Gleichgewichte sind unwirtschaftlich?
Was sollte man Firma A raten?
Antwort:
ENTER: Hier würde Firma B den Markt mit (EXIT) verlassen, weil uB (S) = -2 und uB (E) = -1.
Firma A würde folglich uA = 3 anstatt uA = 0 erreichen.
Es soll ein Konzept erdacht werden, in dem der zuerst Agierende mit berücksichtigt, wie zukünftige
Mitstreiter auf seinen Spielzug reagieren. Der erste Spieler kann also sein Vorgehen optimieren,
indem er sich auf diejenige Menge von Aktionen beschrängt, welche ihm höhere payoffs garantiert
(SPE).
Definition (informell): Subgame
Ein subgame (Teilspiel) ist ein Teilbaum. Es ist ein Entscheidungsknoten des Orginalspiels mit den
zugehörigen Entscheidungsknoten die diesem Knoten folgen (descendants).
Definition (informell): Proper subgame
Ein subgame heißt proper subgame (echtes Teilspiel), wenn es sich vom Orginalspiel
unterscheidet.
Unser Beispiel beeinhaltet 3 subgames:
1) Das Orginalspiel selbst
2) Den linken Teilbaum mit Knoten IIe als Wurzel (proper subgame)
3) Den rechen Teilbaum mit Knoten IIn als Wurzel (proper subgame)
Definition (informell): Subgame perfect equilibrium – SPE
Ein Ergebnis heißt subgame perfect equilibrium („teilspielperfektes Gleichgewicht“), falls für jedes
subgame des Originalspiels ein Nash Gleichgewicht existiert. Das SPE ist eine Liste von Strategien
(für jeden Spieler jeweils eine), die sich aus den Aktionen der Spieler zusammensetzt, welche in
jedem Teilspiel das Nash Gleichgewicht bestimmen.
In Extensivformspielen existiert immer ein teilspielperfektes Gleichgewicht.

Mit Hilfe des Begriffs des 'teilspielperfektes Nash-Gleichgewichts' ist es möglich, nicht plausible Nash-
Gleichgewichte (z.B. unglaubwürdige Drohungen) auszuschließen.
Der Begriff des teilspielperfekten Nash-Gleichgewichts hat seine Bedeutung auch für ein extensives
Spiel ohne vollkommene Information, allerdings sind in einem solchen Spiel häufig wenig Teilspiele
vorhanden, so dass es hier zu unplausiblen teilspielperfekten Nash-Gleichgewichten kommen kann.
Minimax-Theorem
Jedes Endliche Zweipersonen-Nullsummenspiel besitzt ein Nash-Gleichgewicht in gemischten
Strategien.
Anmerkung:
Wenn man die Tatsache, dass in Extensivformspielen immer ein teilspielperfektes Gleichgewicht
(SPE) existiert (Kuhn’s Theorem), damit kombiniert, dass in Nullsummenspielen die Auszahlungen in
jedem Nash-GG den security levels entspechen (Minimax-Theorem), kommt man zur Beobachtung,
dass es in jedem solchen Spiel eine Strategie für einen der beiden Spieler geben muss, um ein
entsprechendes Ergebnis auch zu erreichen.
Anschaulich bedeutet das: Bei Schach gibt es entweder eine Gewinnstrategie für weiß oder für
schwarz, oder beide können ein Remis erzwingen.

Rückwärts Induktion
Eine Methode um SPE Ergebnisse zu finden stellt die Rückwärts Induktion (backward induction) dar:
(1) Suche nach den NE in den subgames, die zu den Endknoten führen.
(2) Diejenigen NE Aktionen, welche in den letzten subgames gespielt wurden, werden nun als
gegeben angenommen.
(3) Wiederhole (2) so lange bis der Wurzelknoten erreicht ist
(4) Sobald der Wurzelknoten erreicht wird, wählt man diejenige Aktion, die den payoff maximiert, der
durch die NE der anderen echten subgames gegeben ist.
Die Methode der Rückwärts Induktion wird in der Praxis oft bei großen Spielbäumen angewendet.
Der Berechnungsaufwand ist direkt proportional zur Größe der Spielrepräsentation.
Algorithmus in C++:
float backwardInduction(node h)
{
if (isElement(h,Z)) return u(h); // h ist Endknoten? Dann Abbruch
float best_util = -99999999.f; // “minus unendlich”
for (action a;a<maximumActions(h);a++) // Für alle Aktionen, die am Knoten h verfügbar sind
{f
loat child_util = backwardInduction( successorFunction(h,a) );
if (child_util > best_util)
best_util = child_util;
}
return best_util;
}

Centipede Spiel

Das Centipede Spiel wurde von Rosenthal 1982 eingeführt und wurde seitdem regelmäßig untersucht.
Binmore (1987), Kreps (1990), Reny (1988) und viele weitere haben sich über Centipede und seine
Derivate gedanken gemacht.
In seiner ursprünglichen Form besteht das Spiel aus einer Sequenz von 100 Spielzügen (darum der
name „Centipede“) mit linear wachsenden payoffs.

Beschreibung:

Das Centipede Spiel ist ein extensive form game, in dem zwei Spieler abwechselnd die Chance
bekommen den größeren Anteil einer wachsenden Menge an Geld zu nehmen. Sobald ein Spieler
sich entscheidet, das Geld zu nehmen, endet das Spiel. Derjenige, der das Geld nimmt, bekommt den
größeren Anteil, währen der andere den kleineren Anteil erhält. Ein sofortiges übergeben verringert
den payoff des Spieler, wenn der Gegner den nächsten Zug macht. Wenn der Gegner wieder
übergibt, befinden sich beide Spieler wieder in der selben Auswahlsituation – diesesmal aber mit
vertauschten Rollen und erhöhten payoffs. Das Spiel hat eine begrenzte Zhal an Spielzügen, die
beiden Spielern bekannt ist.
Eine 1 an einem Entscheidungsknoten (wo sich beide Linien schneiden) bedeutet eine
Entscheidungsmöglichkeit für Spieler 1. Eine 2 bedeutet, dass Spieler 2 entscheidungsträger ist.
Die obere Zahl bei einer vertikalen Linie steht für den payoff von Spieler 1, die untere für den payoff
von Spieler 2.
Spieler 1 beginnt das Spiel. Wählt er D, bekommen beide ein payoff von 1. Wählt er A, übergibt er die
Entscheidung an Spieler 2.
Spieler 2 macht den zweiten Spielzug. Wählt er D, dann bekommt Spieler 1 ein payoff von 0 und er
selbst ein payoff von 3. Wählt er A, dann wird die Entscheidung an Spieler 1...
Wählen beide Spieler immer A, bekommen sie ein payoff von 100.
Theoretische Vorhersage
Wenn beide Spieler immer A wählen bekommen sie ein payoff von 100. Wenn Spieler 1 sich beim
ersten Zug für D entscheiden, bekommen beide ein payoff von 1.
Die Spieltheorie sagt voraus, dass sich Spieler 1 im ersten Zug für D entscheiden wird und folglich
beide Spieler ein payoff von 1 erhalten werden.
Wie kommt es zu diesem Ergebnis?
Eine Auswertung mit der Rückwärts Induktion führt zur Vorhersage, dass Spieler 1 beim ersten Zug D
wählen wird.

Alle Nash Gleichgewichte machen dieselbe Vorhersage. Wir haben folglich eine eindeutige
theoretische Vorhersage.
Typische experimentelle Ergebnisse
Verschiedene Verhaltensstudien über das Centipede Spiel (4 Züge Versionen, 6 Züge Versionen und
Versionen mit hohem Payoff) von McKelvey und Palfrey (1992) haben gezeigt, dass sich die
Testpersonen selten den theoretischen Vorhersagen entsprechend verhalten.
In der Praxis entscheiden sich nur 7% der Spieler bei 4-Züge Spielen, 1% bei den 6-Züge Spielen und
15% bei den high-payoff Spielen dazu, beim ersten Zug D zu wählen. Ähnliche Versuchsergebnisse
haben auch Nagel und Tang 1998 erzielt.
Deutungsversuche des „unlogischen“ Verhaltens der
Versuchspersonen
Es gibt zwei Erklärungsversuche für das Verhalten der Versuchspersonen:
1) Die Versuchspersonen scheinen eine gewisse positive Gewichtung auf die payoff Funktion des
anderen Mitspielers zu legen.
Egoistische Spieler versuchen selbstlose Spieler zu täuschen, indem sie dem Mitspieler durch
selbstloses Verhalten (übergeben der Entscheidung an den anderen) vorgaukeln sie selbst seien
selbstlos.
2) Der zweite Erklärungsversuch zieht die Möglichkeit von Aktionsfehlern mit ein. Aktionsfehler (noisy
play) können entstehen, indem Spieler mit verschiedenen Strategien experimentieren.


Beispiel: Chomp

Chomp ist ein zwei Spieler Spiel, das auf einem rechteckigen Schokoladenriegel gespielt wird. Der
Schokoladenriegel besteht aus kleineren quadratischen Zellen. Die Spieler nehmen rundenweise eine
Block und essen ihn auf (von unten oder von rechts). Der obere linke Block ist vergiftet. Derjenige
Spieler, der ihn isst, hat verloren.
Spieler A verliert dieses Spiel, da er das vergiftete Stück essen muss.
Chomp gehört in die Kategorie der 2-Spieler Spiele mit perfekter Information und so kann an jeder
Position gesagt werden, ob Spieler 1 oder Spieler 2 gewinnt.
Es stellt sich heraus, dass Spieler 1 auf jeder rechteckigen Startposition größer als 1x1 gewinnen
kann. Dies kann durch das Argument des „Strategie Stehlens“ gezeigt werden: Wir nehmen an, dass
der zweite Spieler eine Gewinnstrategie für jeden anfänglichen Zug von Spieler 1 hat. Wir mutmaßen
dann, dass der erste Spieler nur das untere rechte Quadrat nimmt. Nach unserer Vorraussetzung, hat
der zweite Spieler eine Antwortstrategie, die den Sieg erzwingen wird. Aber wenn eine solche
Strategie existiert, könnte sie auch der erste Spieler gespielt haben und somit den Sieg erzwungen
haben. Folglich kann der zweite Spieler keine Gewinnstrategie dafür haben.


4. Imperfect information extensive form games

Im Normalfall haben die Spieler nicht immer vollen Zugriff auf alle Informationen, die für ihre Auswahl
nötig sind. Extensive form games mit imperfekter Information bilden genau nach, welche
Informationen zum Zeitpunkt des Spielzuges verfügbar sind und welche nicht. Sie stellen also in
gewisser Weise eine Erweiterung des Modells der perfect information extensive form games dar.
Definition (informell): Imperfect information extensive form game
Ein extensive form game mit imperfekter Information ist ein extensive form game, in dem die
Auswahlknoten in information sets aufgeteilt sind.
Definition (mathematisch): Imperfect information extensive form
game
Ein extensive form game mit imperfekter Information ist ein Tupel (N,A,H,Z,x,p,o,u,I), mit
- (N,A,H,Z,x,p,o,u,I), ist ein perfect information extensive form game
- I = (I1,…,In), wobei Ii = (Ii,1,…,Ii,k1) eine Äquivalenzrelation auf (das ist eine Teilmenge) {h ist
Element von H : p(h) = i } mit der Eigenschaft, dass x(h) = x(h’) und p(h) = p(h’), wenn ein a j
existiert für das h Element von Ii,j und h’ Element von Ii,j ist.
Beispiel:
Im obrigen Beispiel hat Spieler 1 zwei Information sets: Das set das den obersten Auswahlknoten
beeinhaltet und das set, das die beiden unteren Auswahlknoten beeinhaltet. In unserem Beispiel
haben die beiden unteren Knoten das selbe set an möglichen Aktionen. Spieler 1 weiß nicht, ob
Spieler 2 A oder B gewählt hat, wenn er seine Entscheidung zwischen l und r trifft.

Relation zwischen perfect und imperfect information Game
Lemma (trivial):
Jedes perfect information game kann als Spezialfall eines imperfect information games angesehen
werden, in dem jede Äquivalenzklasse in jedem Teilbereich eindeutig ist.
Relation zwischen normal form game und imperfect information
game
Lemma:
Jedes normal form game kann in ein imperfect information game umgewandelt werden.
Beispiel:
Hinweis: Man hätte auch Spieler 2 den ersten Zug machen lassen können und Spieler 1 den zweiten
Zug.
Perfect Information games waren nicht mächtig genug, um das Prisoner’s dilemma modellieren zu
können. Alle normal form games können relativ einfach in imperfect information extensive form games
umgewandelt werden.

Definition (informell): Behavioural Strategy (Verhaltens Strategie)

Eine behavioural strategy (Verhaltens Strategie) ist eine Strategie, in der jeder Spieler
(möglicherweise nach Wahrscheinlichkeiten) bei jedem Knoten seine Wahl unabhängig von seiner
Wahl bei den anderen Knoten trifft.
Lemma: Perfect recall games
Die Mächtigkeit der Klasse der perfect recall games ist deckt sich mit der Mächtigkeit der
Gemischten- und Verhaltensstrategien. In dieser Klasse von Spielen vergisst kein Spieler irgendeine
Information, die er über die bisher gemachten Spielzüge weiß.
Jedes perfect-information game ist ein perfect-recall game.
4.8. Theorem: Kuhn’s Theorem
Ein Spieler mit perfektem Wiederaufruf (perfect recall) kann jede gemischte Strategie durch eine
Verhaltensstrategie ersetzen, die die gleiche Wahrscheinlichkeit hat, jeden Knoten im Spielbaum zu
erreichen - unabhängig davon, was der andere Spieler macht.
Eine Verhaltensstrategie ist eine "lokale" Wahrscheinlichkeitsverteilung auf den Zügen eines
Information sets. Im Gegensatz dazu steht die gemischte Strategie, die zuerst eine Verlosung
erfordert und dann eine komplette, reine Strategie für das gesamte restliche Spiel auswählt. Die
benötigt die Berechnung von weniger Wahrscheinlichkeiten als in einer gemischten Strategie.


5. Incomplete information extensive form games

Idee
Es gibt Fälle, in denen der Spieler nicht genau über die payoffs bescheid weiß, oder von welchem Typ
seine Gegner sind. Diese Art von Spiel hat also inkomplette Information. Dies wird in extensiver
Form durch die Notation der god’s choice (die Wahl Gottes) oder nature’s choice (die Wahl der
Natur) dargestellt.
Stellen wir uns ein Spiel vor, das darin besteht ob ein Arbeitgeber einen Bewerber für einen Job
einstellt oder nicht. Die Kompetenz des Bewerbers soll entweder hoch oder niedrig sein. Seine
Kompetenz ist zufällt bestimmt : Mit einer Wahrscheinlichkeit von 2/3 ist sie hoch und mit einer
Wahrscheinlichkeit von 1/3 ist sie niedrig. In diesem Fall ist es üblich, die Natur als zusätzlichen
Spieler zu modellieren. Die Spielerarten nehmen die Kompetenz des Bewerbers entsprechend der
Wahrscheinlichkeitsverteilung an. Die Natur hat natürlich keine payoffs.
Darstellung
Die god’s choice wird im Spielbaum durch einen ungefüllten Kreis als Knoten dargestellt. Die Kanten,
die von diesem Knoten ausgehen werden mit der Wahrscheinlichkeit des Ereignisses markiert. Diese
Repräsentation ist das Ergebnis der Harsanyi Transformation.
Beispiel
Das Spiel im Beispiel hat inkomplette Information. Der Anfangsknoten befindet sich in der Mitte und
wird durch den Kreis dargstellt. Die Natur macht also den ersten Zug. Die Natur wählt mit der gleichen
Wahrscheinlichkeit (p=0.5) den Typ vom Spieler 1 (welcher in diesem Spiel gleichbedeutend dazu ist,
welche payoffs in den subgames gewählt werden) – also t1 oder t2. Spieler 1 weiß von sich selbst
genau, von welchem Typ er ist (das muss aber nicht immer so sein). Spieler 2 kann die Wahl der

Natur selbst nicht sehen. Er kennt den Typ vom Spieler 1 folglich nicht. In diesem Spiel beobachtet er
jedoch die Aktionen von Spieler 1 – darüber besitzt er perfekte Information. In der Tat ist es jetzt
angemessen, die gegebene Definition für perfekte Information abzuändern: Zu jedem Zeitpunkt im
Spiel weiß jeder Spieler was von allen anderen Spielern gespielt worden ist. Im Falle der kompletten
Information, weiß jeder Spieler was von der Natur gespielt worden ist.
Information sets werden wie üblich mit gestrichelten Linien dargestellt.
Wenn in diesem Spiel die Natur t1 als Typ von Spieler 1 wählt, läuft das Spiel wie üblich ab, bis auf
die Tatsache, dass Spieler 2 es nicht weiß (und weil gerade dies in seine Information sets durchbricht,
kann er selbst den subgame Status nicht mehr berechnen).
Wenn beide Typen (t1 und t2) die selbe Aktion spielen (pooling), kann kein equilibrium aufrecht
gehalten werden. Wenn beide D spielen, kann Spieler 2 lediglich wissen, dass er in einem der beiden
Knoten mit einer Wahrscheinlichkeit von ½ ist. Spieler 2 maximiert sein payoff, indem der D’ spielt.
Wenn er jedoch D’ spielt , wird Typ2 es vorziehen U zu spielen. Das kann kein equlibrium sein. Wenn
beide typen U spielen, trifft Spieler 2 wieder die Annahme, dass er an einem der beiden Knoten mit
einer Wahrscheinlichkeit von ½ ist. In diesem Fall wird Spieler 2 D’ spielen, aber dann wird Typ1 es
vorziehen D zu spielen.
Wenn Typ1 U spielt und Typ2 D, dann wird Spieler 2 D’ spielen, egal was er beobachtet, aber dann
wird Typ1 wohl D bovorzugen. Das einzige Gleichgewicht besteht hier darin, dass Typ1 D spielt, Typ2
U spielt und Spieler 2 U’ spielt, wenn er D beobachtet und einen zufälligen Zug macht, wenn er U
beobachtet. Durch sein Handeln hat Spieler 1 seinen Typ and Spieler 2 verraten.


6. Schlusswort

Die Spieltheorie stellt eine mächtige Werkzeugsammlung zur Verfügung, um Ergebnisse für
konkurrierende Gegner vorherzusagen. Sie kann besonders dann erfolgreich eingesetzt werden,
wenn die Anzahl der Konkurrenten klein ist.
Mithilfe des Models der perfect information extensive form games können wir Spiele simulieren, in
denen die Gegner ihre Entscheidungen zu verschiedenen Zeitpunkten treffen und die zuvor getätigten
Züge ihrer Gegenspieler kennen. Damit unterscheidet sich die Extensivform von der Normalform, bei
der sämtliche Spieler ihre Strategien gleichzeitig festlegen. Ein Spiel in extensiver Form kann anhand
einer Baumdarstellung repräsentiert werden. Diese Baumdarstellung macht auch die zeitliche Struktur
deutlich.
Das Modell der imperfect information extensive form games ist eine Erweiterung der perfect
information extensive form games. Sie ermöglichen uns eine Modellierung von Spielen, bei denen die
Spieler nicht immer vollen Zugriff auf alle Informationen haben, die für ihre Auswahl nötig sind. Sie
bilden genau nach, welche Informationen zum Zeitpunkt des Spielzuges verfügbar sind und welche
nicht.
Das Centipede Spiel hat gezeigt, dass man die Vorhersagen, die mit der Spieltheorie gemacht werden
immer mit Vorsicht zu genießen muss – nicht immer verhalten sich die Agenten, wie man es der
Theorie nach erwarten würde.
In der Praxis sind Probleme in der Spieltheorie wesentlich komplexer als die in Lehrbücher zu
findenden Beispiele. Sowohl die Anzahl der Konkurrenten, die Anzahl der möglichen Spielzüge und
die Anzahl der zu betrachtenden Parameter sind in der Regel wesentlich höher – die Komplexität und
der Berechnungsaufwand steigt damit rapide an. Mithilfe der Informatik lassen sich die Methoden und
Algorithmen der Spieltheorie automatisierten, visualisieren, verifizieren und auswerten.
Die Qualität der Ergebnisse eines spieltheoretischen Modells hängt direkt von der Qualität der
einprogrammierten Parameter ab, was eine sehr vorsichtige Modellierung erfordet. Oft spielen
psychologische oder Gesellschaftliche Aspekte eine Rolle, solche menschlichen Werte lassen sich
jedoch nicht immer einfach als Zahlen darstellen. Die Spieltheorie hat auch gezeigt, dass falls alle
Spieler strikt ihre eigenes Ziel zur Gewinnmaximierung verfolgen, am Spielende eine Situation
entstehen kann, die für alle Spieler ungünstig ist (bsp.: Prisoner’s dilemma).
Man sollte immer im Hinterkopf behalten, dass die Qualität des Ergebnisses immer nur so gut sein
kann, wie die Qualität der Daten, mit denen das System gefüttert wird.


7. Zusammenfassung

Extensive form games besitzen im Gegensatz zu normal form games eine zeitliche Struktur und
werden anhand eines Baums dargestellt. Jeder Knoten repräsentiert eine Entscheidung von einem
der Spieler, jede Kante repräsentiert eine mögliche Aktion. Die Blätter repräsentieren die finalen
Spielausgänge. Ihnen ist eine Nutzenfunktion zugeordnet (der payoff).
Ein Nash Gleichgewicht (Nash equilibrium) beschreibt den Zustand im Spiel, in dem kein Spieler
einen Vorteil im Spiel gegenüber den anderen erreicht, wenn er alleine seine Strategie ändert.
Ein Ergebnis heißt subgame perfect equilibrium („teilspielperfektes Gleichgewicht“), falls für jedes
subgame des Originalspiels ein Nash Gleichgewicht existiert. Das SPE ist eine Liste von Strategien
(für jeden Spieler jeweils eine), die sich aus den Aktionen der Spieler zusammensetzt, welche in
jedem Teilspiel das Nash Gleichgewicht bestimmen. In Extensivformspielen existiert immer ein
teilspielperfektes Gleichgewicht.
Extensive form games mit imperfekter Information sind eine Erweiterung der extensive form games.
Sie bilden genau nach, welche Informationen zum Zeitpunkt eines Spielzuges verfügbar sind und
welche nicht.
Fälle, in denen der Spieler nicht genau über die payoffs oder den Typ seiner Gegner bescheid weiß,
können mit incomplete information games modelliert werden. Dies wird in extensiver Form durch die
Notation der god’s choice (die Wahl Gottes) oder nature’s choice (die Wahl der Natur) dargestellt.


8. Referenzen

Stöcker: Taschenbuch mathematischer Formeln und moderner Verfahren
Yishay Mansour: Computational Game Theory, Lecture 7
John von Neumann, Oscar Morgenstern: Theory of Games and Economic Behaviour
Christian Rieck: Spieltheorie - eine Einführung
Fuldenberg, Drew and Jean Tirole: Game Theory
Jim Ratliff: Game Theory
Gerald Röhrling: Grundkonzepte der Spieltheorie
Wikipedia.org
Shoham and Leyton-Brown: Multi Agent Systems