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})}$, 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 sich insbesondere, wenn ein fester Ressourcenbestand oder ein fester Geldbetrag unter den Spielern als 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 ist daher möglich, die Definition eines Zwei-Personen-Nullsummenspiels zu 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} }$.

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 der vereinfachten Darstellung erhält man 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)}$

Nash-Gleichgewicht

Ein zentraler Begriff der Spieltheorie ist die beste Reaktion eines Spielers auf eine gegnerische Strategiekombination. Im 2-Personen-Spiel ist dies die Antwort auf die Frage, mit welcher Strategie ein Spieler seine Auszahlung maximiert, wenn die gegnerische Strategie vorgegeben ist. Die Reaktionsfunktion oder auch Reaktionskorrespondenz eines Spielers gibt also für jede gegnerische Strategie an, was die beste strategische Antwort darauf ist; der Begriff Reaktionskorrespondenz ist die Menge aller besten Antworten auf 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, dass bei der vereinfachten Darstellung in der Definition einer besten Reaktion für Spieler 2 minimiert statt 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 einem Nash-Gleichgewicht versteht man eine Strategienkombination, bei der jeder Spieler seine Auszahlung für die gegebene Strategie des Gegners maximiert, also jeder Spieler eine beste Reaktion auf den Gegner spielt. Für ein Zwei-Personen-Nullsummenspiel in Normalform bedeutet dies 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 kann auch unterstellen, dass die Spieler im Wesentlichen daran interessiert sind, den Gewinn ihres Gegners möglichst gering zu halten. Für Spieler 1 bedeutet dies, dass er eine Strategie mit 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}}$. 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 man die zweite Definitionsvariante mit der Definition einer Minimax-Strategie, so erkennt man, dass bei Zwei-Personen-Nullsummenspielen kein 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.

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 enge Beziehung zwischen Minimax- und Maximin-Gleichgewichten bei Zwei-Personen-Nullsummenspielen ergibt sich bereits aus den Definitionen. Es gilt aber sogar der folgende Satz, der die Äquivalenz aller 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.

Endliche Strategiemengen

Bei endlicher Strategiemenge lassen sich die besten Reaktionen, Minimax- und Maximin-Strategien durch Ausprobieren finden. Anschließend kann man ebenfalls durch Ausprobieren feststellen, ob es sich um ein 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) sehen die besten Reaktionen so aus:

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

Keine der Strategiekombinationen stellt ein Nash-Gleichgewicht dar, da nie beide eine beste Reaktion auf die gegnerische Strategie spielen.

Zur Ermittlung der Maximin-Strategien für Spieler 1 bestimmt man zunächst die Zeilenminima ZMin, siehe 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 wie 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“ und „Schere, Stein, Papier“ haben also kein Gleichgewicht in der Menge der vorgegebenen Strategiekombinationen. Um dieses Manko zu beheben, führt man 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 zur Minimax-Strategie) für Spieler 1 findet man, indem 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}$.

Umgekehrt muss man für eine Maximin-Strategie von 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 von Gleichgewichten nach der Erweiterung auf gemischte Strategien wird durch das folgende Minimax-Theorem von John von 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}$.

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 hat jedes Zwei-Personen-Nullsummenspiel mit endlichen Strategiemengen für beide Spieler mindestens ein Gleichgewicht in gemischten Strategien. Jede gleichgewichtige bzw. Minimax- oder Maximin-Strategie eines Spielers bildet mit jeder gleichgewichtigen bzw. Minimax- oder Maximin-Strategie des anderen Spielers (in der Erweiterung des Spiels auf gemischte Strategien) ein Gleichgewicht.

Beispiele (Fortsetzung)