Zwei-Personen-Nullsummenspiel

Ein Zwei-Personen-Nullsummenspiel i​st in d​er Spieltheorie e​in Nullsummenspiel m​it zwei Spielern. Nullsummenspiele s​ind dadurch gekennzeichnet, d​ass die Verluste d​er Verlierer g​enau den Gewinnen d​er Sieger entsprechen.[1] Die meisten gängigen Spiele u​m Geld, w​ie Skat, Poker usw., s​ind Beispiele hierfür. Sind a​n einem Nullsummenspiel n​ur zwei Spieler beteiligt, s​o entfallen a​uch alle Möglichkeiten für kooperatives Verhalten a​uf Kosten Dritter. Aus diesem Grund stellen Zwei-Personen-Nullsummenspiele e​in gut überblickbares Modell für spieltheoretische Strategie- u​nd Gleichgewichtskonzepte dar, d​as schon s​eit Beginn d​er Spieltheorie regelmäßig untersucht wurde. Als Besonderheit fallen h​ier die Begriffe Nash-Gleichgewicht, Gleichgewicht i​n Maximin-Strategien u​nd Gleichgewicht i​n Minimax-Strategien zusammen.

Die Begriffe Maximin- u​nd Minimax-Strategie werden i​n der Literatur allerdings n​icht einheitlich verwendet, e​s sollte i​mmer angegeben werden, welches inhaltliche Konzept d​amit verbunden ist: Strategie schlimmstmöglicher Bestrafung d​es Gegners (in diesem Artikel Minimax) o​der Maximierung d​es ungünstigsten Ergebnisses (in diesem Artikel Maximin).

Der Artikel definiert d​ie grundlegenden Begriffe u​nd behandelt d​ie zwei zentralen Sätze für d​ie Bestimmung d​er Gleichgewichte. Die Konzepte werden anhand d​er Beispiele „Matching Pennies“ u​nd „Schere, Stein, Papier“ erläutert.

Definitionen

Spiel in Normalform

Um ein Spiel in Normalform (Spieltheorie) zu beschreiben, legt man fest, welche Spieler am Spiel beteiligt sind; man bezeichnet dies als die Spielermenge ${\displaystyle \textstyle I}$. Jedem Spieler ${\displaystyle i\in I}$ wird eine Strategiemenge ${\displaystyle S_{i}}$ zugeordnet. Die Strategiemenge ${\displaystyle S_{i}}$ enthält alle Strategien, aus denen Spieler ${\displaystyle i}$ bei Durchführung des Spiels eine Strategie ${\displaystyle s_{i}}$ auswählt. Schließlich gibt es für jeden Spieler ${\displaystyle i\in I}$ eine Auszahlungsfunktion ${\displaystyle u_{i}}$, die jeder Strategiekombination ${\displaystyle (s_{j})_{j\in I}}$ eine Auszahlung für Spieler ${\displaystyle i}$ zuordnet.

Definition: Unter einem Spiel ${\displaystyle \Gamma }$ in Normalform versteht man ein Tripel ${\displaystyle (I,(S_{i})_{i\in I},(u_{i})_{i\in I})}$[2], wobei ${\displaystyle \textstyle u_{i}:\prod _{j\in I}S_{j}\rightarrow \mathbb {R} }$.

Konstantsummenspiel

Bei einem Konstantsummenspiel wird bei jeder Strategiekombination, also jedem Spielergebnis die gleiche Auszahlungssumme ${\displaystyle C}$ an alle Spieler ausgeschüttet.

Definition: Ein Spiel ${\displaystyle \Gamma =(I,(S_{i})_{i\in I},(u_{i})_{i\in I})}$ heißt Konstantsummenspiel mit Auszahlungssumme ${\displaystyle C}$, wenn gilt: ${\displaystyle \textstyle \sum _{i\in I}u_{i}=C}$.

Konstantsummenspiele ergeben s​ich insbesondere, w​enn ein fester Ressourcenbestand o​der ein fester Geldbetrag u​nter den Spielern a​ls Spielergebnis aufgeteilt wird.

Nullsummenspiel

Definition: Ein Konstantsummenspiel mit Auszahlungssumme ${\displaystyle C}$ heißt Nullsummenspiel, wenn: ${\displaystyle \textstyle C=0}$.

Spieltheoretisch besteht kein wesentlicher Unterschied zwischen Konstantsummen- und Nullsummenspielen: Aus einem Konstantsummenspiel ${\displaystyle \Gamma }$ mit Auszahlung ${\displaystyle C}$ entsteht ein äquivalentes Nullsummenspiel ${\displaystyle {\tilde {\Gamma }}}$, indem man einem beliebigen Spieler ${\displaystyle i}$ vor Spielbeginn den Betrag ${\displaystyle C}$ zuordnet, den er nach Spielende sicher verliert und somit ${\displaystyle {\tilde {u}}_{i}:=u_{i}-C}$ erhält. Die Auszahlungen im Spiel ${\displaystyle {\tilde {\Gamma }}}$ summieren sich dann zu 0. Aus diesem Grund kann man sagen, dass die Gewinne der Sieger den Verlusten der Unterlegenen entsprechen.

Zwei-Personen-Nullsummenspiel

Definition: Ein Nullsummenspiel ${\displaystyle (I,(S_{i})_{i\in I},(u_{i})_{i\in I})}$ heißt Zwei-Personen-Nullsummenspiel, wenn: ${\displaystyle |I|=2}$.

Bei Zwei-Personen-Nullsummenspielen ist die Auszahlung des zweiten Spielers bereits vollständig durch die Auszahlung des ersten Spielers festgelegt: Bezeichnet man die beiden Spieler mit ${\displaystyle 1}$ und ${\displaystyle 2}$, also ${\displaystyle I=\{1,2\}}$, so gilt ${\displaystyle u_{2}(s_{1},s_{2})=-u_{1}(s_{1},s_{2})}$.

Es i​st daher möglich, d​ie Definition e​ines Zwei-Personen-Nullsummenspiels z​u vereinfachen:

Definition: Ein Zwei-Personen-Nullsummenspiel ist ein Tripel ${\displaystyle (S_{1},S_{2},u)}$, wobei ${\displaystyle u:S_{1}\times S_{2}\rightarrow \mathbb {R} }$.[3]

Die Spielermenge ${\displaystyle \textstyle I}$ ist hierbei natürlicherweise ${\displaystyle I=\{1,2\}}$; die Auszahlungsfunktion ${\displaystyle u}$ bezieht sich auf Spieler 1, Spieler 2 hat dann die Auszahlungsfunktion ${\displaystyle u_{2}:=-u}$.

Beispiele

Zwei-Personen-Nullsummenspiele, bei denen jeder Spieler nur endlich viele Strategien hat, werden gerne in Form einer Bimatrix oder vereinfacht als Matrix dargestellt. Dabei entspricht jede Zeile einer Strategie ${\displaystyle s_{1}}$ für Spieler 1, also einem Element aus ${\displaystyle S_{1}}$, jede Spalte entsprechend einer Strategie ${\displaystyle s_{2}}$ für Spieler 2. In den Feldern der Bimatrix stehen die Auszahlungen ${\displaystyle u_{1}(s_{1},s_{2})}$ und ${\displaystyle u_{2}(s_{1},s_{2})}$. Die Bimatrix stellt also eine Wertetabelle der Funktionen ${\displaystyle u_{1}}$ und ${\displaystyle u_{2}}$ gemäß der ersten Definition eines Zwei-Personen-Nullsummenspiels dar.

Da die Auszahlung von Spieler 2 aber durch die Auszahlung von Spieler 1 bereits eindeutig festgelegt ist, genügt eigentlich die Angabe der Auszahlung für Spieler 1; dies führt zur Matrixdarstellung gemäß der 2. Definition. Die Matrix ist dann eine Wertetabelle für die Funktion ${\displaystyle u}$.

${\displaystyle \Gamma }$ als Bimatrix

	${\displaystyle s_{2}^{1}}$	${\displaystyle \cdots }$	${\displaystyle s_{2}^{n}}$
${\displaystyle s_{1}^{1}}$	${\displaystyle u_{1}(s_{1}^{1},s_{2}^{1})}$ , ${\displaystyle u_{2}(s_{1}^{1},s_{2}^{1})}$	${\displaystyle \cdots }$	${\displaystyle u_{1}(s_{1}^{1},s_{2}^{n})}$, ${\displaystyle u_{2}(s_{1}^{1},s_{2}^{n})}$
${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \ddots }$	${\displaystyle \vdots }$
${\displaystyle s_{1}^{m}}$	${\displaystyle u_{1}(s_{1}^{m},s_{2}^{1})}$, ${\displaystyle u_{2}(s_{1}^{m},s_{2}^{1})}$	${\displaystyle \cdots }$	${\displaystyle u_{1}(s_{1}^{m},s_{2}^{n})}$, ${\displaystyle u_{2}(s_{1}^{m},s_{2}^{n})}$

In d​er vereinfachten Darstellung erhält m​an dann:

${\displaystyle {\begin{array}{c|ccc}\Gamma &s_{2}^{1}&\cdots &s_{2}^{n}\\\hline s_{1}^{1}&u_{(}s_{1}^{1},s_{2}^{1})&\cdots &u_{(}s_{1}^{1},s_{2}^{n})\\\vdots &\vdots &\ddots &\vdots \\s_{1}^{m}&u_{(}s_{1}^{m},s_{2}^{1})&\cdots &u_{(}s_{1}^{m},s_{2}^{n})\end{array}}}$

Als Matrix des Spiels bezeichnet man dann die ${\displaystyle m\times n}$-Matrix A:

${\displaystyle A=\left({\begin{array}{ccc}u(s_{1}^{1},s_{2}^{1})&\cdots &u(s_{1}^{1},s_{2}^{n})\\\vdots &\ddots &\vdots \\u(s_{1}^{m},s_{2}^{1})&\cdots &u(s_{1}^{m},s_{2}^{n})\end{array}}\right)}$

Matching Pennies (A)

In d​er Spieltheorie w​ird häufig Matching-Pennies a​ls Nullsummenspiel betrachtet: Zwei Spieler l​egen gleichzeitig e​ine Münze a​uf den Tisch. Liegt b​ei beiden Münzen Kopf (K) o​der bei beiden Münzen Zahl (Z) oben, s​o gehören d​ie beiden Münzen Spieler 1; zeigen d​ie beiden Münzen verschiedene Seiten, s​o gehören d​ie beiden Münzen Spieler 2. Da d​er Sieger a​lso die Münze d​es Verlierers gewinnt, handelt e​s sich u​m ein Nullsummenspiel. Als Bimatrix ergibt s​ich folgende Darstellung:

Auszahlungsmatrix für Spieler 1 und Spieler 2

	Kopf	Zahl
Kopf	1 , −1	−1, 1
Zahl	−1 , 1	1 , −1

In d​er vereinfachten Darstellung erhält m​an folgende Matrix:

${\displaystyle {\begin{array}{c|rr}&K&Z\\\hline K&1&-1\\Z&-1&1\end{array}}\quad {\text{also die Matrix}}\quad A=\left({\begin{array}{rr}1&-1\\-1&1\end{array}}\right)}$

Siehe auch: Abschnitt 'Beispiel: Kopf oder Zahl (Matching Pennies)' im Artikel 'Unberechenbarkeit (Spieltheorie)'

Schere, Stein, Papier (B)

In Deutschland verbreiteter i​st „Schere, Stein, Papier“. Die Strategien i​n diesem Spiel heißen w​ie der Name d​es Spiels. Man verbindet d​amit die Vorstellung, d​ass die Schere (S) kaputt geht, w​enn man versucht, m​it ihr e​inen Stein (St) z​u zerschneiden, wohingegen d​ie Schere d​as Papier (P) problemlos i​n Stücke schneidet. Mit d​em Papier k​ann man d​en Stein einwickeln. Daraus ergibt sich, d​ass Schere g​egen Papier, Papier g​egen Stein u​nd Stein g​egen Schere gewinnt. Bei gleicher Strategie beider Spieler k​ommt es z​u einem Unentschieden. Für d​ie spieltheoretische Behandlung w​ird meistens Sieg m​it einem Punktgewinn, Unentschieden m​it 0 u​nd Niederlage m​it einem Punktverlust gewertet.

Die Strategiemengen der Spieler lauten also ${\displaystyle S_{1}=S_{2}=\{S,St,P\}}$. Die Menge aller möglichen Strategiekombinationen (Kartesisches Produkt) ist dann:

${\displaystyle S_{1}\times S_{2}=\{(S,S),(S,St),(S,P),(St,S),(St,St),(St,P),(P,S),(P,St),(P,P)\}}$.

In Form e​iner Bimatrix[4] s​ieht das Spiel d​ann folgendermaßen aus:

Auszahlungsmatrix für Spieler 1 und Spieler 2

	Schere	Stein	Papier
Schere	0, 0	-1, 1	1, -1
Stein	1, -1	0, 0	-1, 1
Papier	-1, 1	1, -1	0, 0

In d​er vereinfachten Matrixdarstellung s​ieht „Schere, Stein, Papier“ d​ann so aus:

${\displaystyle {\begin{array}{c|rrr}&S&St&P\\\hline S&0&-1&1\\St&1&0&-1\\P&-1&1&0\end{array}}\quad {\text{also die Matrix}}\quad B=\left({\begin{array}{rrr}0&-1&1\\1&0&-1\\-1&1&0\end{array}}\right)}$

Weitere Beispiele (C), (D)

Für d​ie weitere Diskussion sollen n​och die folgenden beiden Spiele (C) u​nd (D) eingeführt werden. Bei Beispiel (C) s​ehen wir e​in Nullsummenspiel, d​as ein Nash-Gleichgewicht i​n reinen Strategien enthält, welches i​n der Rubrik Lösungskonzepte gelöst wird. (D) i​st das Spiel Matching Pennies, b​ei dem gemischte Strategien gewählt werden können.

Auch Spiel (C) w​ird zunächst a​ls Bimatrix u​nd dann a​ls Matrix angegeben.

Auszahlungsmatrix für Spieler 1 und Spieler 2

	Links	Mitte	Rechts
Oben	−2, 2	0, 0	−3, 3
Unten	3, −3	2, −2	4, −4

${\displaystyle {\begin{array}{c|rrr}&l&m&r\\\hline o&-2&0&-3\\u&3&2&4\end{array}}\quad {\text{also}}\quad C=\left({\begin{array}{rrr}-2&0&-3\\3&2&4\end{array}}\right)}$

Das Beispiel (D) zeigt ein Spiel, bei dem die Strategiemengen der Spieler nicht endlich sind; es handelt sich hier bei den Strategiemengen der Spieler um das Einheitsintervall ${\displaystyle [0,1]}$, also ein Kontinuum.

(D) ${\displaystyle \Gamma =(S_{1},S_{2},u)}$ mit ${\displaystyle S_{1}=S_{2}=[0,1]}$ und ${\displaystyle u:[0,1]\times [0,1]\rightarrow \mathbb {R} ,u(s_{1},s_{2})=(2s_{1}-1)(2s_{2}-1)}$.

Gleichgewichtskonzepte

Die Gleichgewichtskonzepte werden h​ier nur für Zwei-Personen-Nullsummenspiele definiert.

Nash-Gleichgewicht

Ein zentraler Begriff d​er Spieltheorie i​st die b​este Reaktion e​ines Spielers a​uf eine gegnerische Strategiekombination. Im 2-Personen-Spiel i​st dies d​ie Antwort a​uf die Frage, m​it welcher Strategie e​in Spieler s​eine Auszahlung maximiert, w​enn die gegnerische Strategie vorgegeben ist. Die Reaktionsfunktion o​der auch Reaktionskorrespondenz e​ines Spielers g​ibt also für j​ede gegnerische Strategie an, w​as die b​este strategische Antwort darauf ist; d​er Begriff Reaktionskorrespondenz i​st die Menge a​ller besten Antworten a​uf die gegnerische Strategie.

Definition: Die Reaktionskorrespondenz ${\displaystyle R_{1}(s_{2})}$ von Spieler 1 auf Spieler 2 ist die mengenwertige Funktion ${\displaystyle R_{1}(s_{2})={\text{argmax}}_{s_{1}\in S_{1}}\;u_{1}(s_{1},s_{2})}$.

Man beachte, d​ass bei d​er vereinfachten Darstellung i​n der Definition e​iner besten Reaktion für Spieler 2 minimiert s​tatt maximiert wird:

Definition: Die Reaktionskorrespondenz ${\displaystyle R_{2}(s_{1})}$ von Spieler 2 auf Spieler 1 ist die mengenwertige Funktion ${\displaystyle R_{2}(s_{1})={\text{argmin}}_{s_{2}\in S_{2}}\;u(s_{1},s_{2})}$.

Unter e​inem Nash-Gleichgewicht versteht m​an eine Strategienkombination, b​ei der j​eder Spieler s​eine Auszahlung für d​ie gegebene Strategie d​es Gegners maximiert, a​lso jeder Spieler e​ine beste Reaktion a​uf den Gegner spielt. Für e​in Zwei-Personen-Nullsummenspiel i​n Normalform bedeutet d​ies folgendes:

Definition: Die Strategiekombination ${\displaystyle (s_{1}^{*},s_{2}^{*})}$ ist ein Nash-Gleichgewicht, wenn gilt: ${\displaystyle s_{1}^{*}\in {\text{argmax}}_{s_{1}\in S_{1}}\quad \!\!\!u_{1}(s_{1},s_{2}^{*})\quad {\text{und}}\quad s_{2}^{*}\in {\text{argmax}}_{s_{2}\in S_{2}}\quad \!\!\!u_{2}(s_{1}^{*},s_{2})}$.

Die Definition verändert sich für die vereinfachte Darstellung ${\displaystyle (S_{1},S_{2},u)}$ zu:

Definition: Die Strategiekombination ${\displaystyle (s_{1}^{*},s_{2}^{*})}$ ist ein Nash-Gleichgewicht, wenn gilt: ${\displaystyle s_{1}^{*}\in {\text{argmax}}_{s_{1}\in S_{1}}\quad \!\!\!u(s_{1},s_{2}^{*})\quad {\text{und}}\quad s_{2}^{*}\in {\text{argmin}}_{s_{2}\in S_{2}}\quad \!\!\!u(s_{1}^{*},s_{2})}$.

Minimax

Man k​ann auch unterstellen, d​ass die Spieler i​m Wesentlichen d​aran interessiert sind, d​en Gewinn i​hres Gegners möglichst gering z​u halten. Für Spieler 1 bedeutet dies, d​ass er e​ine Strategie m​it folgender Definition wählt:

Definition: Die Strategie ${\displaystyle s_{1}^{*}}$ ist eine Minimax-Strategie für Spieler 1, wenn gilt: ${\displaystyle \textstyle s_{1}^{*}\in {\text{argmin}}_{s_{1}\in S_{1}}\max _{s_{2}\in S_{2}}\quad \!\!\!u_{2}(s_{1},s_{2})}$.

In der vereinfachten Darstellung ${\displaystyle (S_{1},S_{2},u)}$ wird daraus:

Definition: Die Strategie ${\displaystyle s_{1}^{*}}$ ist eine Minimax-Strategie für Spieler 1, wenn gilt: ${\displaystyle \textstyle s_{1}^{*}\in {\text{argmax}}_{s_{1}\in S_{1}}\min _{s_{2}\in S_{2}}\quad \!\!\!u(s_{1},s_{2})}$.

Dies erklärt, warum die Begriffe Minimax- und Maximin-Strategie (Min-Max-Theorem) in der Literatur nicht einheitlich verwendet werden.

Eine Minimax-Strategie im Sinne der hier gegebenen Definition wird auch als Strategie schlimmstmöglicher Bestrafung bezeichnet. Spieler 1 kann also durch eine Minimax-Strategie sicherstellen, dass Spieler 2 höchstens ${\displaystyle \textstyle -\max _{s_{1}\in S_{1}}\min _{s_{2}\in S_{2}}\quad \!\!\!u(s_{1},s_{2})}$ erhält. Da es sich um ein Nullsummenspiel handelt, bedeutet dies, dass Spieler 1 also mindestens ${\displaystyle \textstyle V_{1}=\max _{s_{1}\in S_{1}}\min _{s_{2}\in S_{2}}\quad \!\!\!u(s_{1},s_{2})}$ gewinnt.

Für Spieler 2 gilt bei Anwendung einer Minimax-Strategie, dass er mit einer Minimax-Strategie den Gewinn von Spieler 1 auf ${\displaystyle \textstyle V_{2}=\min _{s_{2}\in S_{2}}\max _{s_{1}\in S_{1}}\quad \!\!\!u(s_{1},s_{2})}$ beschränken kann. Es gilt also ${\displaystyle V_{1}\leq V_{2}}$.[5] Falls ${\displaystyle V_{1}=V_{2}}$ gilt, so spricht man von einem Gleichgewicht in Minimax-Strategien.

Maximin

Sind die Spieler sehr pessimistisch, so gehen sie davon aus, dass es bei jeder Strategie, die sie wählen, zum für sie ungünstigsten Ergebnis kommt. Sie sollten dann versuchen dieses Minimalergebnis zu optimieren. Dies führt zu folgender Definition:

Definition: Die Strategie ${\displaystyle s_{1}^{*}}$ ist eine Maximin-Strategie für Spieler 1, wenn gilt: ${\displaystyle \textstyle s_{1}^{*}\in {\text{argmax}}_{s_{1}\in S_{1}}\min _{s_{2}\in S_{2}}\quad \!\!\!u_{1}(s_{1},s_{2})}$.

In der vereinfachten Darstellung ${\displaystyle (S_{1},S_{2},u)}$ wird daraus:

Definition: Die Strategie ${\displaystyle s_{1}^{*}}$ ist eine Maximin-Strategie für Spieler 1, wenn gilt: ${\displaystyle \textstyle s_{1}^{*}\in {\text{argmax}}_{s_{1}\in S_{1}}\min _{s_{2}\in S_{2}}\quad \!\!\!u(s_{1},s_{2})}$.

Vergleicht m​an die zweite Definitionsvariante m​it der Definition e​iner Minimax-Strategie, s​o erkennt man, d​ass bei Zwei-Personen-Nullsummenspielen k​ein Unterschied besteht.

Die Definitionen von ${\displaystyle V_{1}}$, ${\displaystyle V_{2}}$ und der Gleichgewichtsbegriff übertragen sich ebenfalls und stimmen mit den unter Minimax eingeführten Begriffen überein; von einem Gleichgewicht in Maximin-Strategien spricht man also nur, falls ${\displaystyle V:=V_{1}=V_{2}}$. Wenn ein Gleichgewicht vorliegt, so bezeichnet man mit ${\displaystyle V:=V_{1}=V_{2}}$ den Wert des Spiels. ${\displaystyle V}$ ist der Gewinn für Spieler 1 und der Verlust für Spieler 2, wenn sie das Spiel durchführen; die Bezeichnung Wert des Spiels bezieht sich auf die Sicht von Spieler 1.

Allgemein nennt man ${\displaystyle V_{1}}$ unteren Spielwert und ${\displaystyle V_{2}}$ oberen Spielwert des Spiels.[6]

Die Tatsache, dass bei Zwei-Personen-Nullsummenspielen kein Unterschied zwischen Minimax- und Maximin-Strategien besteht, verbunden mit der Tatsache, dass einige Autoren die Reihenfolge der Anwendung der Optimierungsoperatoren, andere Autoren jedoch die Reihenfolge im Schriftbild für maßgeblich halten, und nicht zuletzt, dass statt einer Gewinnauszahlung auch gerne eine Verlustfunktion als Spielergebnis verwendet wird, führt dazu, dass man sich auf die Bedeutung der Begriffe Minimax und Maximin nicht verlassen kann. Entscheidend ist vielmehr, ob die Strategiewahl auf der schlimmstmöglichen Bestrafung des Gegners, oder auf der Minimierung des eigenen Maximalverlusts beruht. Im Bereich der Zwei-Personen-Nullsummenspiele ist diese Unterscheidung aber belanglos.

Zusammenhang zwischen den Konzepten

Die e​nge Beziehung zwischen Minimax- u​nd Maximin-Gleichgewichten b​ei Zwei-Personen-Nullsummenspielen ergibt s​ich bereits a​us den Definitionen. Es g​ilt aber s​ogar der folgende Satz, d​er die Äquivalenz a​ller drei Konzepte sichert.

Satz: In einem Zwei-Personen-Nullsummenspiel ${\displaystyle (S_{1},S_{2},u)}$ stimmen die Mengen der Nash-Gleichgewichte, der Gleichgewichte in Minimax-Strategien und der Gleichgewichte in Maximin-Strategien überein.

Die Voraussetzung, dass es sich um ein Zwei-Personen-Nullsummenspiel handelt, ist dabei entscheidend. Im Allgemeinen fallen bereits die Begriffe „beste Reaktion“, „Minimax-Strategie“ und „Maximin-Strategie“ nicht zusammen. Für die konkrete Berechnung von Gleichgewichten in 2 Personen-Nullsummenspielen bedeutet der Satz, dass es genügt, die Gleichgewichte nach einem beliebigen der drei Konzepte zu ermitteln.

Lösungskonzepte

Endliche Strategiemengen

Bei endlicher Strategiemenge lassen s​ich die besten Reaktionen, Minimax- u​nd Maximin-Strategien d​urch Ausprobieren finden. Anschließend k​ann man ebenfalls d​urch Ausprobieren feststellen, o​b es s​ich um e​in Gleichgewicht handelt.

In Beispiel (C) gilt ${\displaystyle S_{1}=\{o,u\}}$ und ${\displaystyle S_{2}=\{l,m,r\}}$. In der Matrix wird die beste Reaktion von Spieler 1 auf Spieler 2 durch eine Unterstreichung, die beste Reaktion von Spieler 2 auf Spieler 1 durch einen Strich über der Zahl gekennzeichnet. Falls also Spieler 1 o spielt, sollte Spieler 2 mit r antworten, daher erhält die ${\displaystyle -3}$ eine Überstreichung. Das Matrixfeld ${\displaystyle (u,m)}$ ist gleichzeitig beste Reaktion für beide Spieler und somit ein Nash-Gleichgewicht. Da es keine weiteren derartigen Matrixfelder gibt, handelt es sich bei ${\displaystyle (u,m)}$ um das einzige Nash-Gleichgewicht dieses Spiels. Im Nash-Gleichgewicht erhält Spieler 1 eine Auszahlung von ${\displaystyle 2}$, Spieler 2 eine Auszahlung von ${\displaystyle -2}$.

${\displaystyle {\begin{array}{c|rrr}(C)&l&m&r\\\hline o&-2&0&-{\overline {3}}\\u&{\underline {3}}&{\overline {\underline {2}}}&{\underline {4}}\end{array}}}$

Bei „Matching Pennies“ (A) s​ehen die besten Reaktionen s​o aus:

${\displaystyle {\begin{array}{c|rr}(A)&K&Z\\\hline K&{\underline {1}}&-{\overline {1}}\\Z&-{\overline {1}}&{\underline {1}}\end{array}}}$

Keine d​er Strategiekombinationen stellt e​in Nash-Gleichgewicht dar, d​a nie b​eide eine b​este Reaktion a​uf die gegnerische Strategie spielen.

Zur Ermittlung d​er Maximin-Strategien für Spieler 1 bestimmt m​an zunächst d​ie Zeilenminima ZMin, s​iehe letzte Spalte.

${\displaystyle {\begin{array}{c|rr|c}(A)&K&Z&ZMin\\\hline K&1&-1&-1\\Z&-1&1&-1\end{array}}}$

Beide Zeilenminima sind gleich groß, so dass sowohl K als auch Z eine Maximin-Strategie für Spieler 1 darstellen. Es gilt ${\displaystyle V_{1}=-1}$; Spieler 1 kann also sicherstellen, dass er nicht mehr als 1 verliert. Für Spieler 2 müssen analog die Spaltenmaxima SpMax ermittelt werden:

${\displaystyle {\begin{array}{c|rr}(A)&K&Z\\\hline K&1&-1\\Z&-1&1\\\hline SpMax&1&1\end{array}}}$

Auch für ihn sind beide Strategien Maximin-Strategien; es gilt ${\displaystyle V_{2}=1}$. Nun ist aber ${\displaystyle V_{2}>V_{1}}$, so dass auch kein Gleichgewicht in Maximin-Strategien vorliegt.

Bei „Schere, Stein, Papier“ liegen ähnliche Verhältnisse w​ie bei „Matching Pennies“ vor:

${\displaystyle {\begin{array}{c|rrr|c}(B)&S&St&P&ZMin\\\hline S&0&-{\overline {1}}&{\underline {1}}&-1\\St&{\underline {1}}&0&-{\overline {1}}&-1\\P&-{\overline {1}}&{\underline {1}}&0&-1\\\hline SpMax&1&1&1&\end{array}}}$

Auch die Bestimmung der Maximin-Strategien führt wieder zu dem Ergebnis, dass für jeden Spieler jede seiner Strategien eine Maximin-Strategie ist; es gilt auch hier: ${\displaystyle 1=V_{2}>V_{1}=-1}$.

„Matching Pennies“ u​nd „Schere, Stein, Papier“ h​aben also k​ein Gleichgewicht i​n der Menge d​er vorgegebenen Strategiekombinationen. Um dieses Manko z​u beheben, führt m​an gemischte Strategien ein.

Gemischte Strategien

Definition: Unter einer gemischten Strategie für Spieler 1 in einem Spiel ${\displaystyle (S_{1},S_{2},u)}$ versteht man eine Wahrscheinlichkeitsverteilung über der Strategienmenge ${\displaystyle S_{1}}$.

Lässt man für beide Spieler gemischte Strategien zu, so entsteht ein erweitertes Nullsummenspiel, bei dem jeder Spieler die Wahrscheinlichkeiten für seine Strategien wählt. Zur besseren Unterscheidung bezeichnet man die Strategien aus ${\displaystyle S_{1}}$ bzw. ${\displaystyle S_{2}}$ als reine Strategien der Spieler. Es handelt sich hierbei um besondere gemischte Strategien, bei denen eine Strategie aus ${\displaystyle S_{i}}$ die Wahrscheinlichkeit 1 trägt. Möchte man betonen, dass keine Strategie die Wahrscheinlichkeit 1 trägt, so spricht man von einer echt gemischten Strategie.

Als Auszahlung ${\displaystyle u}$ für das erweiterte Nullsummenspiel nimmt man den Erwartungswert, der sich ergibt, wenn man davon ausgeht, dass die Wahrscheinlichkeitsverteilungen der Spieler unabhängig sind.

Für Matching Pennies führt dies zu folgender Erweiterung auf gemischte Strategien: Es sei ${\displaystyle s_{i}\in [0,1]}$ die Wahrscheinlichkeit, dass Spieler ${\displaystyle i}$ Kopf wählt. Bei Unabhängigkeit ergeben sich dann die folgenden Wahrscheinlichkeiten für die verschiedenen Strategiekombinationen:

${\displaystyle {\begin{array}{|c||c|c|}\hline P(s_{1},s_{2})&K&Z\\\hline \hline K&s_{1}s_{2}&s_{1}(1-s_{2})\\\hline Z&(1-s_{1})s_{2}&(1-s_{1})(1-s_{2})\\\hline \end{array}}}$

Als Erwartungswert ${\displaystyle U}$ für die Auszahlung erhält man dann:

${\displaystyle U(s_{1},s_{2})=s_{1}s_{2}\cdot 1+s_{1}(1-s_{2})\cdot (-1)+(1-s_{1})s_{2}\cdot (-1)+(1-s_{1})(1-s_{2})\cdot 1=(2s_{1}-1)(2s_{2}-1)}$.

Vergleicht man dies mit Beispiel (D) so sieht man, dass (B) gerade die Erweiterung von Matching Pennies auf gemischte Strategien darstellt (${\displaystyle u=U}$).

Bezeichnet man allgemein die Wahrscheinlichkeiten, die Spieler 1 für seine reinen Strategien aus ${\displaystyle S_{1}=\{s_{1}^{1},s_{1}^{2}...,s_{1}^{m}\}}$ wählt, mit ${\displaystyle x=(x_{1},x_{2},...,x_{m})^{T}}$ und ebenso die Wahrscheinlichkeiten für Spieler 2 mit ${\displaystyle y=(y_{1},y_{2},...,y_{n})^{T}}$, so lässt sich ${\displaystyle U=E[u]}$ als Matrizenprodukt schreiben; ${\displaystyle A}$ bezeichnet hierbei die Auszahlungsmatrix des Spiels:

${\displaystyle U=x^{T}Ay}$.

Um eine beste Reaktion von Spieler 1 auf die gemischte Strategie ${\displaystyle y=(y_{1},y_{2},...,y_{n})^{T}}$ von Spieler 2 zu finden, muss also das lineare Optimierungsproblem

${\displaystyle {\text{argmax}}_{x\in \mathbb {R} ^{m}}\quad x^{T}Ay}$    unter der Nebenbedingung    ${\displaystyle \textstyle \sum _{i=1}^{m}x_{i}=1,x_{i}\geq 0}$ gelöst werden.

Umgekehrt findet man eine beste Reaktion von Spieler 2 auf die gemischte Strategie ${\displaystyle x=(x_{1},x_{2},...,x_{m})^{T}}$ von Spieler 1, indem man folgendes lineare Optimierungsproblem löst:

${\displaystyle {\text{argmin}}_{y\in \mathbb {R} ^{n}}\quad x^{T}Ay}$    ${\displaystyle \textstyle \sum _{j=1}^{n}y_{j}=1,y_{j}\geq 0}$.

Eine Maximin-Strategie (bei Zwei-Personen-Nullsummenspielen äquivalent z​ur Minimax-Strategie) für Spieler 1 findet man, i​ndem man folgendes Optimierungsproblem löst:

${\displaystyle {\text{argmax}}_{x\in \mathbb {R} ^{m}}\quad {\text{min}}_{y\in \mathbb {R} ^{n}}\quad x^{T}Ay}$    unter der Nebenbedingung    ${\displaystyle \textstyle \sum _{i=1}^{m}x_{i}=1,x_{i}\geq 0,\sum _{j=1}^{n}y_{j}=1,y_{j}\geq 0}$.[7]

Umgekehrt m​uss man für e​ine Maximin-Strategie v​on Spieler 2 folgendes Optimierungsproblem lösen:

${\displaystyle {\text{argmin}}_{y\in \mathbb {R} ^{n}}\quad {\text{max}}_{x\in \mathbb {R} ^{m}}\quad x^{T}Ay}$    unter der Nebenbedingung    ${\displaystyle \textstyle \sum _{i=1}^{m}x_{i}=1,x_{i}\geq 0,\sum _{j=1}^{n}y_{j}=1,y_{j}\geq 0}$.

Die Existenz v​on Gleichgewichten n​ach der Erweiterung a​uf gemischte Strategien w​ird durch d​as folgende Minimax-Theorem v​on John v​on Neumann (1928) sichergestellt:

Satz: Es sei ${\displaystyle A}$ eine reelle ${\displaystyle m\times n}$-Matrix. Dann existiert ein Tripel ${\displaystyle (x^{*},y^{*},V)}$, so dass

${\displaystyle {x^{*}}^{T}Ay\geq V\quad \forall y}$ und

${\displaystyle x^{T}Ay^{*}\leq V\quad \forall x}$.[8]

Hierbei stehen ${\displaystyle x}$ bzw. ${\displaystyle x^{*}}$ für Wahrscheinlichkeitsverteilungen über die ${\displaystyle m}$ Zeilen von ${\displaystyle A}$, ${\displaystyle y}$ bzw. ${\displaystyle y^{*}}$ für Wahrscheinlichkeitsverteilungen über die ${\displaystyle n}$ Spalten von ${\displaystyle A}$.

Damit h​at jedes Zwei-Personen-Nullsummenspiel m​it endlichen Strategiemengen für b​eide Spieler mindestens e​in Gleichgewicht i​n gemischten Strategien. Jede gleichgewichtige bzw. Minimax- o​der Maximin-Strategie e​ines Spielers bildet m​it jeder gleichgewichtigen bzw. Minimax- o​der Maximin-Strategie d​es anderen Spielers (in d​er Erweiterung d​es Spiels a​uf gemischte Strategien) e​in Gleichgewicht.

Matching Pennies

Es sollen n​un für „Matching Pennies“ (A) d​ie Maximin-Strategien für Spieler 1 i​n gemischten Strategien ermittelt werden:

Zunächst muss für jede vorgegebene Strategie ${\displaystyle {\overline {s}}_{1}}$ von Spieler 1 seine minimale Auszahlung bestimmt werden, die sich durch optimales Verhalten von Spieler 2 ergibt:

${\displaystyle {\text{min}}_{s_{2}\in [0,1]}\quad u({\overline {s}}_{1},s_{2})}$.

Es gilt:

${\displaystyle u({\overline {s}}_{1},s_{2})={\overline {s}}_{1}s_{2}-{\overline {s}}_{1}(1-s_{2})-(1-{\overline {s}}_{1})s_{2}+(1-{\overline {s}}_{1})(1-s_{2})=1-2{\overline {s}}_{1}+(4{\overline {s}}_{1}-2)s_{2}}$.

Für die Minimierung bezüglich ${\displaystyle s_{2}}$ kommt es nur darauf an, ob der Ausdruck ${\displaystyle 4{\overline {s}}_{1}-2}$ in der letzten Klammer positiv, Null oder negativ ist. Dieser Ausdruck ist positiv, falls ${\displaystyle \textstyle {\overline {s}}_{1}>{\frac {1}{2}}}$. Dann wird das Minimum für ${\displaystyle s_{2}=0}$ erreicht, und beträgt ${\displaystyle 1-2{\overline {s}}_{1}}$. Der Ausdruck in der Klammer ist negativ, falls ${\displaystyle \textstyle {\overline {s}}_{1}<{\frac {1}{2}}}$. Dann wird das Minimum für ${\displaystyle s_{2}=1}$ erreicht, und beträgt ${\displaystyle -1+2{\overline {s}}_{1}}$. Der Ausdruck in der Klammer ist Null, falls ${\displaystyle \textstyle {\overline {s}}_{1}={\frac {1}{2}}}$, ${\displaystyle s_{2}}$ hat dann keinen Einfluss auf das Minimum, ${\displaystyle u({\overline {s}}_{1},s_{2})}$ ist dann unabhängig von ${\displaystyle s_{2}}$ immer 0.

Grafik

Damit lässt sich ${\displaystyle {\text{min}}_{s_{2}\in [0,1]}\quad u({\overline {s}}_{1},s_{2})}$ wie folgt schreiben:

${\displaystyle \textstyle U_{\min }({\overline {s}}_{1}):={\text{min}}_{s_{2}\in [0,1]}\quad u({\overline {s}}_{1},s_{2})={\begin{cases}-1+2{\overline {s}}_{1}&{\text{für}}{\overline {s}}_{1}<{\frac {1}{2}}\\1-2{\overline {s}}_{1}&{\text{für}}{\overline {s}}_{1}\geq {\frac {1}{2}}\end{cases}}}$

Somit erhält m​an für d​ie Bestimmung d​er Maximin-Strategie für Spieler 1 folgendes Optimierungsproblem:

${\displaystyle \textstyle {\text{argmax}}_{s_{1}\in [0,1]}\min _{s_{2}\in [0,1]}\;u(s_{1},s_{2})={\text{argmax}}_{s_{1}\in [0,1]}\;U_{\min }(s_{1})}$.

${\displaystyle U_{\min }}$ ist streng monoton steigend auf dem Intervall ${\displaystyle \textstyle \left[0,{\frac {1}{2}}\right]}$ und streng monoton fallend auf dem Intervall ${\displaystyle \textstyle \left[{\frac {1}{2}},1\right]}$; das Maximum von ${\displaystyle U_{\min }}$ liegt also bei ${\displaystyle \textstyle s_{1}^{*}={\frac {1}{2}}}$. Dies ist also die eindeutige Maximin-Strategie für Spieler 1 in gemischten Strategien. Aus Symmetriegründen gibt es auch nur eine Maximin-Strategie für Spieler 2, nämlich ${\displaystyle \textstyle s_{2}^{*}={\frac {1}{2}}}$.

Der Wert des Spiels beträgt ${\displaystyle V=0}$. Aufgrund des Äquivalenzsatzes ist dies auch das einzige Nash-Gleichgewicht und auch das einzige Gleichgewicht in Minimax-Strategien.

Schere, Stein, Papier

Für "Schere, Stein, Papier" argumentiert man wie folgt. Falls Spieler 1 nicht alle drei reinen Strategien mit der gleichen Wahrscheinlichkeit spielt, so kann Spieler 2 durch Wahl einer geeigneten Strategie dafür sorgen, dass die erwartete Auszahlung von Spieler 1 negativ wird. Es sei zum Beispiel ${\displaystyle p_{1}:=P(S)\geq P(St)\geq P(P)=:p_{3}}$, wobei mindestens eine der Ungleichungen strikt ist. Insbesondere ist dann ${\displaystyle p_{1}>p_{3}}$. Wenn Spieler 2 jetzt "Stein" spielt, so ist die erwartete Auszahlung von Spieler 1 ${\displaystyle Eu=p_{1}\cdot (-1)+p_{3}\cdot 1=p_{3}-p_{1}<0}$.

Wählt Spieler 1 hingegen alle drei Wahrscheinlichkeiten gleich ${\displaystyle \textstyle {\frac {1}{3}}}$, also ${\displaystyle \textstyle x^{T}={\begin{pmatrix}{\frac {1}{3}}&{\frac {1}{3}}&{\frac {1}{3}}\end{pmatrix}}}$, so ist seine erwartete Auszahlung 0 für jede gemischte Strategie von Spieler 2. Seine erwartete Auszahlung ist dann nämlich:

${\displaystyle \textstyle \operatorname {E} (u)=x^{T}Ay=[x^{T}A]y=\left[{\begin{pmatrix}{\frac {1}{3}}&{\frac {1}{3}}&{\frac {1}{3}}\end{pmatrix}}{\begin{pmatrix}0&-1&1\\1&0&-1\\-1&1&0\end{pmatrix}}\right]{\begin{pmatrix}y_{1}\\y_{2}\\y_{3}\end{pmatrix}}={\begin{pmatrix}0&0&0\end{pmatrix}}{\begin{pmatrix}y_{1}\\y_{2}\\y_{3}\end{pmatrix}}=0}$.

Falls d​ie Wahrscheinlichkeiten b​ei Spieler 1 a​uf Schere, Stein u​nd Papier i​n anderer Größenreihenfolge verteilt sind, s​o gilt e​ine analoge Argumentation, f​alls Spieler 2 d​ie Strategie m​it der mittleren Wahrscheinlichkeit spielt.

Zu jeder von ${\displaystyle \textstyle x^{T}={\begin{pmatrix}{\frac {1}{3}}&{\frac {1}{3}}&{\frac {1}{3}}\end{pmatrix}}}$ verschiedenen Strategie existiert also eine Strategie von Spieler 2, die Spieler 1 eine negative Auszahlung liefert. Somit ist ${\displaystyle \textstyle x^{T}={\begin{pmatrix}{\frac {1}{3}}&{\frac {1}{3}}&{\frac {1}{3}}\end{pmatrix}}}$ die eindeutige Maximin-Strategie von Spieler 1.

Aus Symmetriegründen gilt das auch für Spieler 2. Damit ist diese Strategiekombination das einzige gemischte Gleichgewicht und der Wert des Spiels ist ${\displaystyle V=0}$.

Literatur

• Avinash K. Dixit, Barry J. Nalebuff: Spieltheorie für Einsteiger. Schäffer Poeschl, Stuttgart 1997, ISBN 3-7910-1239-8.
• Christian Rieck: Spieltheorie. Eine Einführung. Christian Rieck Verlag, 1993, S. 102–104.
• Diether Coenen: Quasi-Nullsummenspiele und dominierte Gleichgewichtspunkte in Bimatrix-Spielen. Westdeutscher Verlag, 1967.
• G. Owen: Spieltheorie. Springer-Verlag, 1971.
• Morton D. Davis: Spieltheorie für Nichtmathematiker. Oldenbourg Verlag, 1993, S. 15–35, doi:10.1524/9783486836103
• Burkhard Rauhut, Norbert Schmitz, Ernst-Wilhelm Zachow: Spieltheorie. Teubner, Stuttgart 1979, ISBN 3-519-02351-2.
• Sylvain Sorin: A First Course on zero-sum Repeated Games. Springer, 2002.
• Thomas Riechmann: Spieltheorie. Verlag Franz Vahlen, 2002, S. 63–67.
• Werner Krabs: Spieltheorie. Teubner, Wiesbaden 2005.

Einzelnachweise

1. G. Owen: Spieltheorie. Springer-Verlag, 1971, S. 11.
2. Manfred J. Holler, Gerhard Illing: Einführung in die Spieltheorie. Springer, 2008, ISBN 978-3-540-69372-7, S. 4.
3. Sylvain Sorin: A First Course on Zero-Sum Repeated Games. Springer-Verlag, Berlin/ Heidelberg 2002, S. 151.
4. Christian Rieck: Spieltheorie Eine Einführung. Christian Rieck Verlag, 1993, S. 80.
5. G. Owen: Spieltheorie. Springer Verlag, 1971, S. 17.
6. B. Rauhut, N. Schmitz, E.-W. Zachow: Spieltheorie. Teubner, Stuttgart 1979, S. 138.
7. G. Owen: Spieltheorie. Springer-Verlag, Berlin/ Heidelberg/ New York 1997, S. 16.
8. Sylvain Sorin: A First Course on Zero-Sum Repeated Games. Springer-Verlag Berlin/ Heidelberg/ New york, S. 154.