\section{Spieltheorie I: Einführung}

In dieser und der folgenden Woche werden wir uns mit der Spieltheorie
beschäftigen. Die Spieltheorie kann man als Erweiterung der
Entscheidungstheorie auffassen, indem in der Spieltheorie teils sehr ähnliche
Techniken angewendet werden wie in der Entscheidungstheorie. So kann man
"`Spiele"' als Spielbäume oder Tabellen analog zu den Entscheidungsbäumen und
-tabellen der Entscheidungstheorie darstellen. Umgekehrt kann man die
Entscheidungstheorie als Spezialfall der Spieltheorie verstehen. Ein
Entscheidungsproblem ist dann einfach ein Spiel, bei dem einer der Spieler die
Natur ist.

Das wesentliche unterscheidende Merkmal der Spieltheorie gegenüber der
Entscheidungstheorie besteht darin, dass sich in der Spieltheorie die Spieler
strategisch aufeinander beziehen, d.h. die Spieler machen die Wahl der
Strategie, die sie spielen, davon abhängig, welche Strategien die Mitspieler
wählen bzw. von welchen Strategien sie erwarten, dass sie von ihren Mitspielern
gewählt werden. Eine ansatzweise ähnlich Situation gibt es in der
Entscheidungstheorie nur bei der "`kausalen Entscheidungstheorie"', wenn die
Wahrscheinlichkeit des Eintretens der Zufallsereignisse von der gewählten
Handlungsalternative abhängt.

\subsection{Was "`Spiele"' im Sinne der Spieltheorie sind}

Spiele im Sinne der Spieltheorie ähneln im wirklichen Leben am ehesten
einfachen Brett- oder Kartenspielen, wie Mühle oder Schach oder Skat. Einer oder
mehrere Spieler spielen dabei gegeneinander, wobei sie in einer Folge von
Runden aus einer wohldefinierten Menge von möglichen Spielzügen entsprechend
ihrer Strategie jeweils einen Zug wählen. Das Ergebnis des Spiels (Gewinn oder
Verlust bzw. die Höhe des Gewinns oder des Verlusts) hängt dabei von den Zügen
aller Spieler und bei manchen Spielen zusätzlich vom Zufall (z.B. der Würfel
oder Kartenverteilung) ab.

Ein Spiel im Sinne der
Spieltheorie besteht dabei immer mindestens aus folgenden Komponenten: 

\begin{enumerate}
  \item Zwei oder mehrere {\em Spieler}. Je nachdem wie groß die Anzahl der
  Spieler ist, spricht mann von einem 2-Personen, 3-Personen oder $N$-Personen
  Spiel. 
  \item Mengen möglicher Spiel-{\em Züge}. Für jeden Spieler gibt es dabei eine
  eigene Menge möglicher Züge.
  \item Die Menge der möglichen {\em Ergebnisse} bzw. "`Auszahlungen"'. Das
  Ergebnis eines jeden Spielers hängt dabei von den Zügen des Spielers selbst
  und von den Zügen des Gegenübers ab.
\end{enumerate}

Bei bestimmten Arten von Spielen kommen noch weitere Komponenten hinzu:

\begin{enumerate}
  \setcounter{enumi}{3}
  \item Eine endliche oder unendliche Anzahl von Spiel-{\em Runden}. 
  
  \begin{footnotesize}
  Hat ein
  Spiel mehrere Runden und stehen jedem Spieler in jeder Runde dieselben
  möglichen Züge offen, dann spricht man auch von einem {\em wiederholten
  Spiel}. Grundsätzlich kann man jedes wiederholte Spiel auch als ein komplexes
  einfaches Spiel auffassen. Es ist eher eine Frage der Konvenienz, ob man
  solche Spiele als wiederholte Spiele analysiert.
  \end{footnotesize}

  \item Eine Menge von {\em Strategien}. Die Strategie eines Spielers
  spezifiziert für jede Runde und jede Spielsituation (i.e. jede Folge
  vorhergehender Züge), welcher Zug gespielt werden soll. Ggf. kann dabei auch
  zwischen mehreren möglichen Zügen zufällig ausgewählt ("`randomisiert"')
  werden. 

  \begin{footnotesize}  
  Bei einfachen Spielen bestehen die Strategien nur aus einem Zug, so
  dass Züge und Strategien zusammenfallen. Man kann in diesen Fällen die
  Ausdrücke "`Zug"' und "`Strategie"' auch Synonym gebrauchen.
  \end{footnotesize}

  \item Eine Menge von {\em Zufallsereignissen}, die neben den gewählten Zügen
  bzw. Strategien der Spieler die Ergebnisse des Spiels für die Spieler beeinflussen.
 
  \begin{footnotesize}
  Zufallsereignisse können dabei so modelliert werden, dass ein zusätzlicher
  Spieler "`Natur"' eingeführt wird, dessen Züge die zufälligen Ereignisse
  repräsentieren und der über seine Züge mit den Wahrscheinlichkeiten der
  Zufallsereignisse randomisiert. Es ist zu berücksichtigen, dass für die
  Spielerin "`Natur"' keine Rationalität vorausgesetzt werden kann. Eine
  alternative Art der Modellierung des Einflusses von Zufallsereignissen besteht 
  darin, die Ergebnisse der Spieler durch Lotterien über Ergebnisse 
  entsprechend den Wahrscheinlichkeiten der Zufallsereignisse zu ersetzen.
  \end{footnotesize}
\end{enumerate}

Es könnte an dieser Stelle die Frage auftreten, wo die für
Spiele im Alltagsleben (z.B. Brettspiele oder Kartenspiele) konstitutiven
{\em Regelwerke} in die Theorie eingehen. Solche Regelwerke werden implizit bei
der Angabe der möglichen Züge und bei der Angabe der Ergebnisse berücksichtigt.
Die möglichen Züge beim Sachspiel sind eben alle diejenigen Züge, 
die nach den Regeln für das Schachspiel erlaubt sind. Die Ergebnisse (Gewinn,
Verlust, Remis) sind ebenfalls durch das Regelwerk festgelegt, d.h.
umgekehrt: Indem man festlegt, wann welcher Spieler welches Ergebnis erhält,
hat man automatisch die entsprechenden Regeln bezüglich Gewinn und Verlust
des Spiels in der Spielspezifikation berücksichtigt. Daher bildet das Regelwerk
in der Spieltheorie keine eigene Komponente der Spielspezifikation.

Ähnlich wie schon bei der Entscheidungstheorie bildet das Problem der richtigen
Problemspezifikation eine keinesfalls triviale Schwierigkeit bei der Anwendung
der Spieltheorie auf empirisch auftretende Beispiele von strategischer
Interaktion. So wie man etwa bei der Entscheidungstheorie {\em alle} in Frage
kommenden Handlungsalternativen {\em und alle} für das Ergebnis kausal
relevanten Zufallsereignisse angeben muss, ist es bei der Anwendung der Spieltheorie
in der Regel erforderlich alle strategischen Optionen zu kennen und anzugeben.
Will man die Spieltheorie etwa auf die strategische Interaktion zwischen
verfeindeten Armeen im Krieg anwenden, dann kann die Erfindung neuer Taktiken
und Strategien der spieltheoretischen Kalkulation einen Strich durch die
Rechnung machen. Auf derartige Probleme sei hier jedoch nur hingewiesen. Im
Folgenden beschäftigen wir uns zunächst mit der "`reinen"' Spieltheorie als
solcher. Anwendungsbeispiele werden wir in der nächsten und in der letzten
Vorlesung besprechen.

Was die Spieltheorie leisten kann, sofern es uns gelingt einen empirischen
Fall strategischer Interaktion angemessen zu spezifizieren ist zweierlei:

\begin{enumerate}
  \item Die Spieltheorie stellt eine Art standardisierte Sprache zur
  {\em Beschreibung strategischer Interaktion bereit.} Dies erleichtert die
  Darstellung und den Vergleich unterschiedlicher Interaktionssituationen und
  kann selbst in solchen Fällen von Nutzen sein, in denen sich die
  spieltheoretischen Lösungsverfahren als inadäquat erweisen. 
  
  \begin{footnotesize}
  Es ist jedoch zu
  beachten, dass die spieltheoretische Beschreibung strategischer Interaktion
  nicht immer möglich ist, z.B. wenn keine Klarheit über die verfügbaren
  strategischen Optionen besteht. Und auch wenn sie möglich ist, besteht die
  Gefahr, dass die spieltheoretische Beschreibung die wesentlichen Aspekte des
  empirischen Problems eher verdeckt, z.B. indem die außerhalb der
  Wirtschaftswissenschaften oft schwierigen Probleme der Bewertung von
  Ergebnissen in den Auszahlungsparametern (bzw. den Nuzenwerten)
  "`versteckt"' werden.
  \end{footnotesize}

  \item Die Spieltheorie stellt {\em Lösungsverfahren} für Spiele bereit. Eine
  Lösung im Sinne der Spieltheorie ist die Menge derjenigen Strategien, die
  die Spieler wählen werden bzw. wählen sollten, wenn sie ihren Nutzen
  maximieren wollen.
  
  \begin{footnotesize}
  In der Empirie zeigt sich jedoch, dass das beobachtbare
  Spielerverhalten von der spieltheoretischen Lösung häufig stark abweicht.  
  \end{footnotesize}
\end{enumerate}

\subsubsection{Beispiele}

Am besten lässt sich das, was man in der Spieltheorie unter einem Spiel
versteht, anhand von einigen Beispielen darstellen.

\paragraph{Beispiel 1: Das Knobelspiel}

Beim Knobeln wählen zwei Spieler gleichzeitig eines der drei Symbole {\em
Stein}, {\em Schere}, {\em Papier}. Dabei gelten die Regeln: 1.Stein schleift
Schere. 2.Schere schneidet Papier und 3.Papier wickelt Stein. Mit jeder Option
kann man also ebenso gut gewinnen wie verlieren. Das Spiel sieht als Tabelle
dargestellt folgendermaßen aus:

\begin{center}
\begin{tabular}{cc|c|c|c|}
& \multicolumn{1}{c}{} & \multicolumn{3}{c}{{\bf Spaltenspieler}} \\
& \multicolumn{1}{c}{} & \multicolumn{1}{c}{Stein} 
& \multicolumn{1}{c}{Schere} &  \multicolumn{1}{c}{Papier}  \\
\cline{3-5} 
& Stein              & 0,0     & 1,-1   &  -1,1 \\
\cline{3-5} {\bf Zeilenspieler}  
& Schere             & -1,1    & 0,0    & 1,-1 \\ \cline{3-5}
& Papier             & 1,-1    & -1,1   & 0,0 \\ \cline{3-5}
\end{tabular}
\end{center}

Dabei repräsentiert die erste der beiden Zahlen in jeder Zelle im inneren der
Tablle das Ergebnis des "`Zeilenspielers"'. Die zweite Zahl ist das Ergebnis des
"`Spaltenspielers"'. Bei dieser Repräsentation des Spiels steht eine 1 für den
Gewinn des Spiels eine -1 für den Verlust und 0 für Unentschieden.

Eine etwas einfachere Variante desselben Spiels ist das sogenannte
"`Passende Münzen"'-Spiel ("`Matching Pennies"'). Beim "`Passende Münzen"'-Spiel
legen beide Spieler verdeckt eine Münze auf den Tisch. Der erste Spieler gewinnt,
wenn beide Münzen Kopf oder beide Münzen Zahl zeigen. 
Der zweite Spieler gewinnt dagegen, wenn
beide Münzen dasselbe zeigen. In Tabellenform dargestellt, sieht das Spiel
folgendermaßen aus:

\begin{center}
\begin{tabular}{cc|c|c|}
& \multicolumn{1}{c}{} & \multicolumn{2}{c}{\bf Spieler 2} \\
& \multicolumn{1}{c}{} & \multicolumn{1}{c}{Kopf} & \multicolumn{1}{c}{Zahl}
\\ \cline{3-4} 
& Kopf                 & 1,-1                      & -1,1  \\ \cline{3-4}
\raisebox{1.5ex}[-1.5ex]{{\bf Spieler 1}} 
& Zahl                 & -1,1                      & 1,-1 \\ \cline{3-4}
\end{tabular}
\end{center}

Beide Spiele (Knobeln und Passende Münzen) fallen übrigens in die Kategorie der
{\em Nullsummenspiele}, weil der Gewinn des einen der Verlust des anderen ist.

\paragraph{Beispiel 2: Vertrauensspiel}

Genauso wie in der Entscheidungstheorie gibt es in der Spieltheorie
neben der Tabellenform auch andere Darstellungsformen von Spielen. Besonders
wenn die Spielzüge sukzessive aufeinander folgen, bietet sich oft die
anschaulichere Baumdarstellung an. Ein Beispiel ist das sogennante
Vertrauensspiel, bei dem ein Spieler zunächst entscheidet, ob er einem anderen
"`Vertrauen"' schenkt und der andere Spieler, sofern ihm Vertrauen geschenkt
wurde, entscheidet, ob er das Vertrauen belohnt oder den Vertrauenden betrügt.
Das Vertrauensspiel gibt die typische Situation bei Internet-Auktionen wieder,
bei denen zunächst der Käufer das Geld für den ersteigerten Gegenstand
überweist und der Vekäufer anschließend den Gegenstand verschickt. Das
Vertrauensspiel lässt sich sehr einfach und anschaulich als Baum darstellen:

\setlength{\unitlength}{1cm}
\begin{picture}(10,8)(-1,0)
\put(2,7){\makebox(6,1){Spieler 1}}
\put(5,7){\line(-1,-1){5}}
\put(5,7){\line(1,-1){2}}
\put(4,4){\makebox(6,1){Spieler 2}}
\put(7,4){\line(-1,-1){2}}
\put(7,4){\line(1,-1){2}}

\put(2,5.5){\makebox(1,1){{\small vertraue nicht}}}
\put(6.5,5.5){\makebox(1,1){{\small vertraue}}}

\put(4.5,2.5){\makebox(1,1){{\small belohne}}}
\put(8.5,2.5){\makebox(1,1){{\small betrüge}}}

\put(-0.5,1){\makebox(1,1){3, 3}}
\put(4.5,1){\makebox(1,1){4, 4}}
\put(8.5,1){\makebox(1,1){0, 5}}
\end{picture}

Die erste Zahl am unteren Ende des Spielbaums gibt hier wiederum das Ergebnis
für den ersten Spieler an, und die zweite Zahl das Ergebnis für den zweiten
Spieler. Damit es sich um ein "`Vertrauensspiel"' handelt, muss die Belohnung
größer sein als das Ergebnis in dem Fall, dass kein Vertrauen geschenkt wird.
Zugleich muss für den zweiten Spieler die Alternative Betrügen einen höheren
Ertrag liefern als Belohnen. 
Nur dann nämlich ist von Spieler 1 tatsächlich Vertrauen gefragt, wenn er in
Interaktion mit Spieler 2 tritt.

Das Vertrauensspiel ist ebenso wie die folgenden Spiele ein
Nicht-Nullsummen-Spiel, d.h. beide Spieler können bei dem Spiel gewinnen (oder
verlieren). In diesem Fall liefert belohntes Vertrauen beiden ein besseres
Ergebnis als wenn gar kein Vertrauen geschenkt wird.

\paragraph{Beispiel 3: Das Hirschjagd-Spiel}
\label{Hirschjagdspiel}

Beim Hirschjagd-Spiel geht es um folgende Geschichte: Drei Jäger (es können auch
zwei oder mehr als drei Jäger sein) gehen gemeinsam auf die Jagd, um einen Hirsch zu jagen. 
Den Hirsch können sie nur erlegen, wenn sie alle drei zusammenarbeiten. In dem
Wald, wo sie den Hirsch jagen möchten, gibt es aber auch jede Menge Hasen. Einen Hasen
könnte notfalls jeder alleine fangen. Nur gibt ein Hase eben einen kleineren
Braten ab als ein Drittel Hirsch. Jeder Jäger steht also vor der Wahl, ob er
lieber einen Hasen fängt, den er sicher hat, oder ob er, auf die anderen 
Jäger vertrauend, seinen Teil dazu
leistest, den Hirsch zur Strecke zu bringen. 

Bei drei Spielern handelt es sich bereits um ein $N$-Personen Spiel. Um ein
solches Spiel in Tabellenform darzustellen benötigt man eigentlich eine
$N$-Dimensionale Matrix. Man kann das Spiel aber auch durch mehrere
$N-1$-dimensionale Matrizen darstellen, wie im Folgenden. Jede der Matrizen
stellt dabei die möglichen Ergebnisse für jeweils eine bestimmte Handlung (bzw.
einen bestimmten "`Zug"') von Jäger drei dar.

\begin{center}
\begin{tabular}{cc|c|c| c|c|c|}

& \multicolumn{1}{c}{} & \multicolumn{2}{c}{\bf Jäger 2} 
& \multicolumn{1}{c}{} & \multicolumn{2}{c}{\bf Jäger 2} \\
& \multicolumn{1}{c}{} 
& \multicolumn{1}{c}{Hirsch} & \multicolumn{1}{c}{Hase} 
& \multicolumn{1}{c}{} 
& \multicolumn{1}{c}{Hirsch} & \multicolumn{1}{c}{Hase} 
\\ \cline{3-4} \cline{6-7}
 
& Hirsch   & 5, 5, 5 & 0, 2, 0 & &  0, 0, 2 & 0, 2, 2 \\
\cline{3-4} \cline{6-7}
\raisebox{1.5ex}[-1.5ex]{{\bf Jäger 1}} 
& Hase     & 2, 0, 0 & 2, 2, 0 & &  2, 0, 2 & 2, 2, 2 \\
\cline{3-4} \cline{6-7}
\multicolumn{7}{c}{} \\
& \multicolumn{1}{c}{} & \multicolumn{2}{c}{{\small {\bf Jäger 3}: Hirsch}}
& \multicolumn{1}{c}{} & \multicolumn{2}{c}{{\small {\bf Jäger 3}: Hase}} \\


\end{tabular}
\end{center}

Da ein Hirschbraten, auch wenn man ihn sich zu dritt teilen muss, wesentlich
besser ist als ein Hasenbraten wurde dafür der Nutzenwert 5 veranschlagt. Den
Wert 2 bekommt, wer einen Hasen fängt. Und 0 erhält, wer gar nichts fängt, also
ein Jäger, der versucht einen Hirsch zu fangen, während sich einer oder alle
anderen davon machen, um Hasen zu jagen, so dass der Hirsch entwischt\ldots


\paragraph{Beispiel 4: Gefangenendilemma}
\label{Gefangenendilemma}

Es musste ja kommen: Das Gefangenendilemma. Zum Gefangenendilemma gibt es
folgende Geschichte: Zwei Bankräuber werden von der Polizei aufgegriffen. 
Die Polizei kann ihnen
jedoch nichts nachweisen. Daher stellt sie jeden der Bankräuber vor folgende
Wahl: Entweder Du verrätst Deinen Komplizen, oder wir sperren Dich für vier
Wochen wegen Landstreicherei ein. Wenn Du Deinen Komplizen verrätst und er Dich
nicht verrät, dann kommst Du sofort frei und Dein Komplize bekommt 10 Jahre
aufgebrummt. Verrät Dich Dein Komplize ebenfalls, dann kommst Du immerhin mit 5
Jahren davon, weil Du ausgesagt hast. 

\begin{center}
\begin{tabular}{cc|c|c|}
& \multicolumn{1}{c}{} & \multicolumn{2}{c}{\bf Gefangener 2} \\
& \multicolumn{1}{c}{} & \multicolumn{1}{c}{Schweigen} &
\multicolumn{1}{c}{Aussagen} \\ \cline{3-4} 
& Schweigen                 & 4 Wochen, 4 Wochen     & 10 Jahre, frei \\
\cline{3-4}
\raisebox{1.5ex}[-1.5ex]{{\bf Gefangener 1}} 
& Aussagen                  & frei, 10 Jahre         & 5 Jahre, 5 Jahre \\
\cline{3-4}
\end{tabular}
\end{center}

Wenn man solche Faktoren wir die Ganovenehre außer Acht lässt, dann werden
beide Gefangenen aussagen, weil diese Strategie ihnen das relativ bessere
Ergebnis liefert sowohl, wenn der andere aussagt, als auch, wenn er schweigt.
Die Strategie "'Schweigen"' wird von der Strategie "`Aussagen"' strikt
dominiert.

Das Beispiel des Gefangenendilemmas führt zugleich eine erste offensichtliche
Lösungsstrategie für Spiele vor Augen, nämlich die Lösung durch {\em Dominanz}. 
Wenn man annimmt,
dass die Spieler ihren Nutzen maximieren wollen, dann sollten sie auf keinen Fall
eine Strategie wählen, die dominiert wird. Dominiert wird eine Strategie dann,
wenn es eine Alternativ-Strategie gibt, die in mindestens einem Fall ein
besseres Ergebnis liefert und in allen anderen Fällen wenigstens ein genauso
gutes. Wie schon bei der Entscheidungstheorie
kann man von der eben beschriebenen {\em schwachen} Dominanz
noch die {\em starke} bzw. {\em strikte} Dominanz unterscheiden. Eine Strategie
wird durch eine andere stark dominiert, wenn die andere Stratwegie in jedem
Fall ein besseres Ergebnis liefert. 

Außer davon, dass eine Strategie dominiert wird (wenn es eine eindeutig bessere
gibt), kann man auch davon sprechen, dass eine Strategie dominant ist, nämlich
dann, wenn sie eindeutig besser ist als aller anderen Strategien. Bei schwacher
Dominanz bedeutet "`eindeutig besser"' sein, dass sie im paarweisen Vergleich
mit jeder anderen Strategie wenigstens in einem Fall ein besseres Ergebnis
liefert als die anderen Strategien und in allen anderen Fällen ein mindestens
gleich Gutes. Bei starker Dominanz ist "`eindeutig besser"' so zu interpretieren,
dass sie in allen Fällen besser sein muss als alle anderen Strategien. 

Dabei ist zu beachten: Wenn eine Strategie durch eine andere dominiert wird, so
bedeutet dies noch längst nicht, dass die andere Strategie eine dominante
Strategie ist. Denn dazu müsste sie auch alle übrigen Strategien dominieren.
Dazu ein Beispiel:

\begin{center}
\begin{tabular}{c|c|c|c|c|}
\multicolumn{1}{c}{} & 
\multicolumn{1}{c}{$S_1$} &
\multicolumn{1}{c}{$S_2$} &
\multicolumn{1}{c}{$S_3$} &
\multicolumn{1}{c}{$S_4$} \\ \cline{2-5}

$Z_1$ & 4 & 4 & 2 & 6  \\ \cline{2-5}
$Z_2$ & 2 & 4 & 0 & 5 \\ \cline{2-5}
$Z_3$ & 3 & 2 & 1 & 2 \\ \cline{2-5}
$Z_4$ & 0 & 2 & 1 & 2 \\ \cline{2-5}

\end{tabular}
\end{center}

Bei diesem Spiel wird die Strategie $Z_4$ durch die Strategie $Z_3$ schwach
dominiert. Trotzdem ist die Strategie $Z_3$ keine dominante Strategie, da sie
die Strategie $Z_2$ nicht dominiert, und zudem ihrerseits durch die Strategie
$Z_1$ stark dominiert wird. Die Strategie $Z_1$ ist eine schwach dominante
Strategie, das sie alle anderen Strategien dominiert, aber die Strategie $Z_2$
nur schwach dominiert.

Im Gefangenendilemma ist Nicht-Kooperation mit dem Mitspieler in jedem Fall
eindeutig besser als Kooperation. Also ist Nicht-Kooperation im
Gefangendilemma eine strikt dominante Strategie.

\subsection{Nullsummenspiele}

Nullsummenspiele sind Spiele, bei denen die Summe der Gewinne und Verluste aller
Spieler immer gleich 0 ist. Das Schachspiel ist ein Nullsummenspiel, das
Knobelspiel ist ebenfalls ein Nullsummenspiel. Die Tatsache, dass bei
Nullsummenspielen der Gewinn des einen immer der Verlust des anderen ist,
erlaubt bei 2-Personen Nullsummenspielen eine nochmals vereinfachte
Darstellung: Man gibt in der Spieltabelle nicht mehr die Gewinne und Verluste
der beiden Spieler durch Kommata getrennt nebeneinander an, sondern man trägt
nur noch die Gewinne des Zeilenspielers ein. Die Gewinne des Spaltenspielers
sind dann der entsprechende negative Wert. Man kann die Situation auch so
auffassen, dass der Zeilenspieler die Werte innerhalb der Tabelle immer
maximieren will, der Spaltenspieler sie aber immer minimieren will.
Eine Spieltabelle könnte dann folgendermaßen aussehen:

\begin{center}
\setlength{\parskip}{0.5cm}
\begin{tabular}{c|c|c|c|c|}
\multicolumn{1}{c}{} & 
\multicolumn{1}{c}{$S_1$} &
\multicolumn{1}{c}{$S_2$} &
\multicolumn{1}{c}{$S_3$} &
\multicolumn{1}{c}{$S_4$} \\ \cline{2-5}

$Z_1$ & 0 & 1 & 7 & 7  \\ \cline{2-5}
$Z_2$ & 4 & 1 & 2 & 10 \\ \cline{2-5}
$Z_3$ & 3 & 1 & 0 & 25 \\ \cline{2-5}
$Z_4$ & 0 & 0 & 7 & 10 \\ \cline{2-5}

\end{tabular}

{\footnotesize Quelle: Resnik, Choices, S.128 \cite[]{resnik:1987}}
\end{center}

Dieses Spiel lässt sich nicht unmittelbar durch Dominanzüberlegungen lösen.
Allerdings kann man es ebenso wie schon in der Entscheidungstheorie durch
{\em sukzessive} Dominanz lösen. So wird die Strategie $S_4$ des Spaltenspielers
offensichtlich von allen anderen Alternativen dominiert, denn er möchte die
Auszahlungen für den Zeilenspieler, die seine Verluste sind, ja möglichist
minimieren. Da die Strategie $C_4$ also nicht in Frage kommt können wir sie
streichen. Ist die Strategie $C_4$ aber erst einmal gestrichen, dann wird
bezüglich der verbleibenden Möglichkeiten die Strategie $Z_3$ dominiert
(nämlich von $Z_2$) und kann ebenfalls gestrichen werden usf. Als Ergebnis
bleibt das Strategiepaar ($R_2$, $S_2$) übrig (Übungsaufgabe). 
Dieses Strategiepaar bildet die {\em Lösung}
des Spiels nach Dominanz. Die Auszahlung, die ein Spieler erhält, wenn beide
Spieler die Lösungsstrategie spielen, wird auch der {\em Wert des Spiels} für den
entsprechenden Spieler genannt. In diesem Beispiel ist der Wert des Spiels für
den Zeilenspieler 1 und für den Spaltenspieler -1.

Allgemein hat {\em eine} Lösung eines Spiels immer die Form
eines Tupels von Strategien, das für jeden Spieler eine Strategie erhält. Je
nach Lösungsverfahren kann keine, eine oder mehrere Lösungen geben. Der Wert
des Spiels kann bei mehreren Lösungen von Lösung zu Lösung variieren. In diesem
Fall kann man sinnvollerweise von dem "`maximalen"' oder auch "`optimalen"' Wert
eines Spiels für einen Spieler sprechen.

\subsubsection{Das Nash-Gleichgewicht}

Die (sukzessive) Dominanz ist ein ebenso einfaches wie einleuchtendes
Lösungsverfahren. Nur lässt es sich nicht immer anwenden. Das folgende Spiel
weist keine dominierten Strategien auf, die man streichen könnte:

\begin{center}
\setlength{\parskip}{0.5cm}
\begin{tabular}{c|c|c|c|}
\multicolumn{1}{c}{} & 
\multicolumn{1}{c}{$S_1$} &
\multicolumn{1}{c}{$S_2$} &
\multicolumn{1}{c}{$S_3$} \\ \cline{2-4}

$Z_1$ & 8,-8 & 8,-8   & 7,-7 \\ \cline{2-4}
$Z_2$ & 0,0  & 10,-10 & 4,-4 \\ \cline{2-4}
$Z_3$ & 9,-9 & 0,0    & 1,-1 \\ \cline{2-4}

\end{tabular}

{\footnotesize Quelle: Resnik, Choices, S.129 \cite[]{resnik:1987}. Aus Gründen
der Anschaulichkeit wurden die entsprechenden negativen Auszahlungen für den
Spaltenspieler explizit eingetragen.}
\end{center}

Trotzdem existiert ein Strategiepaar, dass man durch eine naheliegende
Überlegung in besonderer Weise auszeichnen kann. Dieses Strategiepaar ist das
Paar ($Z_1$, $S_3$). Die Überlegung, die zur Auszeichnung dieses
Strategiepaares führt ist die folgende: Angenommen der Zeilenspieler hätte sich
(aus irgendwelchen Gründen) auf die Strategie $Z_1$ festgelegt. Dann ist das
beste, was der Spaltenspieler tun kann, die Strategie $S_3$ zu wählen, weil er
so noch am meisten bekommt (-7 anstelle von -8 bei den Alternativen $S_1$ und
$S_2$). Man sagt auch, dass die Strategie $S_3$ die {\em beste Antwort} auf die
Strategie $Z_1$ ist. Umgekehrt gilt: Hat der Spaltenspieler die Strategie $S_3$
gewählt, so ist die Strategie $Z_1$ die beste Antwort, die der Zeilenspieler
wählen kann, um sein Ergebnis zu maximieren. Die Strategien $Z_1$ und $S_3$
sind also wechselseitig beste Antworten aufeinander. Keiner der Spieler hätte
eine Motivation, im Alleingang von seiner Strategie abzuweichen. Das
Strategiepaar ($Z_1, S_3$) bildet in diesem Sinne ein {\em Gleichgewicht}. Die
mit diesem Gleichgewicht assoziierten Auszahlungen sind die "`Gleichgewichtswerte"'
des Spiels.

Diese Art von Gleichgewicht nennt bezeichnet man auch nach ihrem Erfinder als
{\em Nash-Gleichgewicht}. Das Konzept des Nash-Gleichgewicht kann folgendermaßen
motiviert werden: Wir nehmen an, dass die Spieler frei und unabhängig
voneinander sind, d.h. jeder Spieler kann seine eigene Strategie wählen aber
niemand kann seinen Gegenüber verpflichten eine bestimmte Strategie zu wählen.
Dann werden die Spieler, wenn sie sich nutzenmaximierend verhalten, immer
diejenige Strategie wählen, die eine beste Antwort auf die Strategie ihres
Gegenübers bzw. auf die Strategie, die sie bei ihrem Gegenüber vermuten, ist. 

Man könnte nun die Frage aufwerfen, ob sich die Spieler nicht gegebenenfalls
dazu verabreden könnten, ihre Strategien gleichzeitig zu wechseln. Aber
einerseits würden sie das vermutlich nur tun, wenn mindestens einer der Spieler
einen Vorteil davon hat und der andere nach dem Wechsel wenigstens nicht
schlechter da steht. Da im Nullsummenspiel der Vorteil des einen immer der Nachteil 
des anderen ist, wird ein Spieler immer gegen den solchen Wechsel sein.
Bei einem Nicht-Nullsummenspiel ist ein solcher Wechsel immerhin vorstellbar,
sofern es den Spielern gelingt, sich in irgendeiner Weise zu koordinieren.

Um alle Nashgleichgewichte in reinen Strategien zu bestimmen, gibt es bei
endlichen Spielen eine zugegebenermaßen krude aber zugleich todsicher Methode:
Man probiert einfach jedes mögliche Strategietupel durch.

Dass es auch im Nullsummenspiel mehrere Gleichgewichte geben kann, zeigt das
folgende Beispiel:

\begin{center}
\setlength{\parskip}{0.5cm}
\begin{tabular}{c|c|c|c|c|}
\multicolumn{1}{c}{} & 
\multicolumn{1}{c}{$S_1$} &
\multicolumn{1}{c}{$S_2$} &
\multicolumn{1}{c}{$S_3$} &
\multicolumn{1}{c}{$S_4$} \\ \cline{2-5}

$Z_1$ & 1,-1 & 2,-2 & 3,-3 & 1,-1  \\ \cline{2-5}
$Z_2$ & 0,0  & 5,-5 & 0,0  & 0,0 \\ \cline{2-5}
$Z_3$ & 1,-1 & 6,-6 & 4,-4 & 1,-1 \\ \cline{2-5}

\end{tabular}

{\footnotesize Quelle: Resnik, Choices, S.131 \cite[]{resnik:1987}, leicht
abgewandelt}
\end{center}

Man kann sich leicht davon überzeugen, dass $(S_1,Z_1)$, $(S_4,Z_1)$,
$(S_1,Z_3), $$(S_4,Z_3)$ Gleichgewichte sind. 
Auffällig ist, dass alle Gleichgewichte
denselben Gleichgewichtswert haben. Dass es sich dabei nicht nur um eine
Zufälligkeit handelt, sondern dass ein Gesetz dahinter steckt, beweist der
folgende Satz (Vgl. Resnik \cite[S. 131]{resnik:1987}):

\begin{quote}
{\em Koordinationstheorem für Nullsummenspiele}: Seien $(S_i, Z_m)$ und $(S_j,
Z_n)$ zwei Gleichgewichte eines Nullsummenspiels. Dann sind auch $(S_i, Z_n)$
und $(S_j, Z_m)$ Gleichgewichte und alle vier Gleichgewichte haben denselben
Wert.
\end{quote}

{\em Beweis} (nach Resnik \cite[S. 131]{resnik:1987}): Seien $v_{im}, v_{jn},
v_{in}, v_{jm}$ die den entsprechenden Strategiepaaren zugeordneten Werte des
Spiels für den Zeilenspieler. Da $(S_i, Z_m)$ und $(S_j, Z_n)$ Gleichgewichte
sind, müssen $v_{im}, v_{jn}$ jeweils minimale Werte ihrer Zeile und maximale
Werte ihrer Spalte sein. Dann gilt aber auch:
\begin{enumerate}
  \item $v_{im} \leq v_{in}$, da beide Werte in derselben Zeile stehen und
  $v_{im}$ als Gleichgewichtswert ein minimaler Wert der Zeile sein muss.
  \item $v_{in} \leq v_{jn}$, da beide Werte in derselben Spalte stehen und
  $v_{jn}$ als Gleichgewichtswert ein maximaler Wert der Spalte sein muss.
  \item $v_{jn} \leq v_{jm}$, da beide Werte in derselben Zeile stehen und
  $v_{jn}$ als Gleichgewichtswert ein minimaler Wert der Zeile sein muss. 
  \item $v_{jm} \leq v_{im}$, da beide Werte in derselben Spalte stehen und
  $v_{in}$ als Gleichgewichtswert ein maximaler Wert der Spalte sein muss. 
\end{enumerate}

Zusammengefasst ergibt sich daraus die Ungleichung:
\[ v_{im} \leq v_{in} \leq v_{jn} \leq v_{jm} \leq v_{im} \]
Da am Ende der Ungleichungskette dieselbe Variable steht wie am Anfang gilt die
Gleichheit:
\[ v_{im} = v_{in} = v_{jn} = v_{jm} = v_{im} \]
Daraus lässt sich unmittelbar ableiten, dass in Nullsummenspielen alle reinen
Gleichgewichte denselben Wert haben müssen.

\subsubsection{Gemischte Strategien und gemischte Gleichgewichte}

Als reine Strategien bezeichnet man Strategien, bei denen die Auswahl der Züge
eindeutig durch die Strategie festgelegt ist und nicht zufällig vorgenommen
wird. Umgekehrt bezeichnet man als gemischte Strategien solche Strategien bei
denen zwischen reinen Strategien randomisiert wird. (Was dasselbe ist, als wenn
man sagen würde, dass innerhalb der Strategie zwischen alternativen Zügen
randomisiert wird.) Ein gemischtes Gleichgewicht ist dementsprechend ein
Gleichgewicht, in dem mindestens zwei gemischte Strategien vorkommen. (Bei
einem 2-Personen Spiel heißt dies, dass das Gleichgewicht nur aus gemischten
Strategien bestehen darf.)
 
Ein einfaches Beispiel für ein gemischtes Gleichgewicht liefert das 
"`Passende Münzen"'-Spiel:

\begin{center}
\begin{tabular}{cc|c|c|}
& \multicolumn{1}{c}{} & \multicolumn{2}{c}{\bf Spieler 2} \\
& \multicolumn{1}{c}{} & \multicolumn{1}{c}{Kopf} & \multicolumn{1}{c}{Zahl}
\\ \cline{3-4} 
& Kopf                 & 1,-1                     & -1,1   \\ \cline{3-4}
\raisebox{1.5ex}[-1.5ex]{{\bf Spieler 1}} 
& Zahl                 & -1,1                     & 1,-1  \\ \cline{3-4}
\end{tabular}
\end{center}

Bei diesem Spiel hat jede reine Strategie, die ein Spieler spielt, den
Erwartungswert -1. Der {\em Erwartungswert} einer Strategie ist diejenige
Auszahlung, die ein Spieler erhält, wenn der Gegenspieler seine beste Antwort auf die
Strategie spielt. (Der Erwartungswert von Strategien in der Spieltheorie ist
also nicht zu verwechseln mit dem Erwartungswert in der Entscheidungstheorie!)

Wenn Spieler 1 aber mit einer 50\% Wahrscheinlichkeit über beide reinen
Strategien randomisiert, dann hat seine gemischte Strategie (50\% Kopf, 50\%
Zahl) einen Erwartungswert von 0, da er -- ganz gleich, welche reine oder
gemischte Strategie der andere Spieler spielt -- immer in der Hälfte der
möglichen Fälle eine Auszahlung von 1 und in der anderen Hälfte der Fälle eine
Auszahlung von -1 bekommt. Den Erwartungswert von 0 erhält Spieler 1 aber
tatsächlich nur, wenn er mit einer Wahrscheinlichkeit von 0.5 zwischen seinen Strategien 
wählt. Würde er eine andere Wahrscheinlichkeit wählen, so würde sein Mitspieler
diejenige Strategie wählen, die die beste Antwort auf die von Spieler 1 häufiger gewählte
reine Strategie wäre. Wenn Spieler 1 also z.B. (60\% Kopf, 40\% Zahl) spielt,
dann würde Spieler 2 am erfolgreichsten sein, wenn er immer Zahl spielte.

Wie kann man aber generell das gemischte Gleichgewicht berechnen, sofern eins
vorhanden ist? Im einfachsten Fall, d.h. bei 2-Personen Spielen mit jeweils zwei
Handlungsoptionen, sieht die Tabelle folgendermaßen aus:

\begin{center}
\begin{tabular}{cc|c|c|}
& \multicolumn{1}{c}{} & \multicolumn{2}{c}{\bf Spaltenspieler} \\
& \multicolumn{1}{c}{} & \multicolumn{1}{c}{$S_1$} & \multicolumn{1}{c}{$S_2$}
\\ \cline{3-4} 
& $Z_1$                 & $A_z, A_s$          &  $B_z, B_s$   \\
\cline{3-4}
\raisebox{1.5ex}[-1.5ex]{{\bf Zeilenspieler}} 
& $Z_2$                 & $C_z, C_s$          &  $D_z, D_s$  \\
\cline{3-4}
\end{tabular}
\end{center}

Bei Nullsummenspielen gilt natürlich immer: $A_z = A_s$,$B_z = B_s$,$C_z = C_s$,
$D_z = D_s$. Aber darauf werden wir bei der Bestimmung des gemischten
Gleichgewichts nicht zurückgreifen, so dass der folgende Ansatz für alle
einfachen 2-Personen Spiele mit zwei Handlungsoptionen tauglich ist. 

Wie aus den Überlegungen zum "`Passende Münzen"'-Spiel bereits deutlich
geworden ist, kann eine gemischte Strategie nur dann eine
Gleichgewichtsstrategie sein, wenn der Gegenspieler indifferent ist, mit
welcher seiner beiden reinen Strategien er die gemischte Strategie
"`beantworten"' soll. Wäre er nämlich nicht indifferent, dann würde er
diejenige reine Strategie wählen, die die bessere Antwort ist. Darauf würde der
erste Spieler wiederum mit einer reinen Strategie antworten können, die
mindestens so gut ist wie seine gemischte Strategie. Ein gemischtes
Gleichgewicht könnte dann nur noch in dem Sonderfall vorliegen, in dem er
indifferent zwischen seinen reinen und gemischten Strategien ist. (Siehe dazu
die entsprechende Übungsaufgabe zur nächsten Vorlesung auf Seite
\pageref{gemischteStrategienAufgabe}) Im Normallfall kommt ein gemischtes
Gleichgewicht im 2-Personen Spiel mit zwei Handlungsoptionen also nur in der
Form vor, in der beide Spieler eine gemischte Strategie spielen.

Wenn wir also bestimmen wollen, mit welcher Wahrscheinlichkeit der
Zeilenspieler im gemischten Gleichgewicht über seine reinen Strategien
randomisieren muss, dann müssen wir die Rechnung für Erwartungswerte des {\em
Spalten}spielers aufstellen. Die Erwartungswerte des Spaltenspielers hängen
nämlich von der Wahrscheinlichkeit ab, mit der der Zeilenspieler randomisiert.

Die Erwartungswerte des Spaltenspielers bezüglich der gemischten Strategie
des Zeilenspielers berechnen sich nach:
\[ EW_{S1} = p \cdot A_s + (1-p) \cdot C_s \]
\[ EW_{S2} = p \cdot B_s + (1-p) \cdot D_s \]
Da beide Werte gleich sein müssen, können wir die Gleichung aufstellen:
\[ p \cdot A_s + (1-p) \cdot C_s = p \cdot B_s + (1-p) \cdot D_s \]
Die Lösung dieser Gleichung liefert uns das gesuchte Randomisierungsgewicht $p$.

Um das Randomisierungsgewicht des Spaltenspielers $q$ zu berechnen, müssen wir
umgekehrt die Erwartungswerte der reinen Strategien des Zeilenspielers
bestimmem:
\[ EW_{Z1} = q \cdot A_z + (1-q) \cdot B_z \]
\[ EW_{Z2} = q \cdot C_z + (1-q) \cdot D_z \]
Daraus ergibt sich die Gleichung:
\[ q \cdot A_z + (1-q) \cdot B_z = q \cdot C_z + (1-q) \cdot D_z \]

Sofern die beiden Gleichungen lösbar sind und für $p$ und $q$ bestimmte Werte
zwischen 0 und 1 liefern, lautet das gemischte Gleichgewicht: 
\[ ( (p,Z_1; 1-p,Z_2), (q,S_1; 1-q,S_2) ) \]
Da bei 2-Personen Spielen mit zwei Handlungsoptionen aber klar ist, zwischen
welchen Strategien randomisiert wird, würde es bereits genügen, die beiden
Wahrscheinlichkeiten für den Zeilen- und Spaltenspieler $p$ und $q$ anzugeben,
um das gemischte Gleichgewicht genau zu spezifizieren.

