Zwei-Personen-Nullsummenspiel

Ein Zwei-Personen-Nullsummenspiel ist in der Spieltheorie ein Nullsummenspiel mit zwei Spielern. Nullsummenspiele sind dadurch gekennzeichnet, dass die Verluste der Verlierer genau den Gewinnen der Sieger entsprechen. Die meisten gängigen Spiele um Geld, wie Skat, Poker usw., sind Beispiele hierfür. Sind an einem Nullsummenspiel nur zwei Spieler beteiligt, so entfallen auch alle Möglichkeiten für kooperatives Verhalten auf Kosten Dritter. Aus diesem Grund stellen Zwei-Personen-Nullsummenspiele ein gut überblickbares Modell für spieltheoretische Strategie- und Gleichgewichtskonzepte dar, das schon seit Beginn der Spieltheorie regelmäßig untersucht wurde. Als Besonderheit fallen hier die Begriffe Nash-Gleichgewicht, Gleichgewicht in Maximin-Strategien und Gleichgewicht in Minimax-Strategien zusammen.

Die Begriffe Maximin- und Minimax-Strategie werden in der Literatur allerdings nicht einheitlich verwendet, es sollte immer angegeben werden, welches inhaltliche Konzept damit verbunden ist: Strategie schlimmstmöglicher Bestrafung des Gegners (in diesem Artikel Minimax) oder Maximierung des ungünstigsten Ergebnisses (in diesem Artikel Maximin).

Der Artikel definiert die grundlegenden Begriffe und behandelt die zwei zentralen Sätze für die Bestimmung der Gleichgewichte. Die Konzepte werden anhand der Beispiele „Matching Pennies“ und „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 $\textstyle I$. Jedem Spieler $i\in I$ wird eine Strategiemenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_i } zugeordnet. Die Strategiemenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_i } enthält alle Strategien, aus denen Spieler Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i } bei Durchführung des Spiels eine Strategie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_i } auswählt. Schließlich gibt es für jeden Spieler Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \in I } eine Auszahlungsfunktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_i } , die jeder Strategiekombination Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (s_j)_{j \in I} } eine Auszahlung für Spieler $i$ zuordnet.

Definition: Unter einem Spiel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Gamma } in Normalform versteht man ein Tripel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (I,(S_i)_{i \in I},(u_i)_{i \in I}) } , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C } an alle Spieler ausgeschüttet.

Definition: Ein Spiel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Gamma= (I,(S_i)_{i \in I},(u_i)_{i \in I})} heißt Konstantsummenspiel mit Auszahlungssumme Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C } , wenn gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 $C$ heißt Nullsummenspiel, wenn: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textstyle C=0 } .

Spieltheoretisch besteht kein wesentlicher Unterschied zwischen Konstantsummen- und Nullsummenspielen: Aus einem Konstantsummenspiel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Gamma } mit Auszahlung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C } entsteht ein äquivalentes Nullsummenspiel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde{\Gamma} } , indem man einem beliebigen Spieler Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i } vor Spielbeginn den Betrag Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C } zuordnet, den er nach Spielende sicher verliert und somit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde{u}_i:=u_i-C } erhält. Die Auszahlungen im Spiel ${\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (I,(S_i)_{i \in I},(u_i)_{i \in I}) } heißt Zwei-Personen-Nullsummenspiel, wenn: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2 } , also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I=\{1,2\} } , so gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (S_1,S_2,u) } , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u:S_1 \times S_2 \rightarrow \mathbb{R} } .

Die Spielermenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textstyle I } ist hierbei natürlicherweise Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I=\{1,2\} } ; die Auszahlungsfunktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u } bezieht sich auf Spieler 1, Spieler 2 hat dann die Auszahlungsfunktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_1 } für Spieler 1, also einem Element aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1 } , jede Spalte entsprechend einer Strategie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_2 } für Spieler 2. In den Feldern der Bimatrix stehen die Auszahlungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_1(s_1,s_2) } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_2(s_1,s_2) } . Die Bimatrix stellt also eine Wertetabelle der Funktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_1 } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u } .

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Gamma } als Bimatrix

	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_2^1 }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \cdots }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_2^n }
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_1^1 }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_1(s_1^1,s_2^1) } , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_2(s_1^1,s_2^1) }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \cdots }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_1(s_1^1,s_2^n) } , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_2(s_1^1,s_2^n) }
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \vdots }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \vdots }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ddots }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \vdots }
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_1^m }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_1(s_1^m,s_2^1) } , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_2(s_1^m,s_2^1) }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \cdots }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_1(s_1^m,s_2^n) } , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_2(s_1^m,s_2^n) }

In der vereinfachten Darstellung erhält man dann:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m \times n } -Matrix A:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 der Spieltheorie wird häufig Matching-Pennies als Nullsummenspiel betrachtet: Zwei Spieler legen gleichzeitig eine Münze auf den Tisch. Liegt bei beiden Münzen Kopf (K) oder bei beiden Münzen Zahl (Z) oben, so gehören die beiden Münzen Spieler 1; zeigen die beiden Münzen verschiedene Seiten, so gehören die beiden Münzen Spieler 2. Da der Sieger also die Münze des Verlierers gewinnt, handelt es sich um ein Nullsummenspiel. Als Bimatrix ergibt sich folgende Darstellung:

Auszahlungsmatrix für Spieler 1 und Spieler 2

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

In der vereinfachten Darstellung erhält man folgende Matrix:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 ist „Schere, Stein, Papier“. Die Strategien in diesem Spiel heißen wie der Name des Spiels. Man verbindet damit die Vorstellung, dass die Schere (S) kaputt geht, wenn man versucht, mit ihr einen Stein (St) zu zerschneiden, wohingegen die Schere das Papier (P) problemlos in Stücke schneidet. Mit dem Papier kann man den Stein einwickeln. Daraus ergibt sich, dass Schere gegen Papier, Papier gegen Stein und Stein gegen Schere gewinnt. Bei gleicher Strategie beider Spieler kommt es zu einem Unentschieden. Für die spieltheoretische Behandlung wird meistens Sieg mit einem Punktgewinn, Unentschieden mit 0 und Niederlage mit einem Punktverlust gewertet.

Die Strategiemengen der Spieler lauten also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1=S_2=\{S,St,P\} } . Die Menge aller möglichen Strategiekombinationen (Kartesisches Produkt) ist dann:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 einer Bimatrix sieht das Spiel dann 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 der vereinfachten Matrixdarstellung sieht „Schere, Stein, Papier“ dann so aus:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 die weitere Diskussion sollen noch die folgenden beiden Spiele (C) und (D) eingeführt werden. Bei Beispiel (C) sehen wir ein Nullsummenspiel, das ein Nash-Gleichgewicht in reinen Strategien enthält, welches in der Rubrik Lösungskonzepte gelöst wird. (D) ist das Spiel Matching Pennies, bei dem gemischte Strategien gewählt werden können.

Auch Spiel (C) wird zunächst als Bimatrix und dann als 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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [0,1] } , also ein Kontinuum.

(D) Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Gamma=(S_1,S_2,u) } mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1=S_2=[0,1] } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 hier nur für Zwei-Personen-Nullsummenspiele definiert.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R_1(s_2) } von Spieler 1 auf Spieler 2 ist die mengenwertige Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R_2(s_1) } von Spieler 2 auf Spieler 1 ist die mengenwertige Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (s_1^*,s_2^*) } ist ein Nash-Gleichgewicht, wenn gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (S_1,S_2,u) } zu:

Definition: Die Strategiekombination Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (s_1^*,s_2^*) } ist ein Nash-Gleichgewicht, wenn gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_1^* } ist eine Minimax-Strategie für Spieler 1, wenn gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (S_1,S_2,u) } wird daraus:

Definition: Die Strategie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_1^* } ist eine Minimax-Strategie für Spieler 1, wenn gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V_1 \leq V_2} . Falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_1^* } ist eine Maximin-Strategie für Spieler 1, wenn gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (S_1,S_2,u) } wird daraus:

Definition: Die Strategie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_1^* } ist eine Maximin-Strategie für Spieler 1, wenn gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V_1 } , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V:=V_1=V_2 } . Wenn ein Gleichgewicht vorliegt, so bezeichnet man mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V:=V_1=V_2 } den Wert des Spiels. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V_1 } unteren Spielwert und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1=\{o,u\} } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -3 } eine Überstreichung. Das Matrixfeld Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (u,m) } um das einzige Nash-Gleichgewicht dieses Spiels. Im Nash-Gleichgewicht erhält Spieler 1 eine Auszahlung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2 } , Spieler 2 eine Auszahlung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -2 } .

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V_2=1 } . Nun ist aber Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (S_1,S_2,u) } versteht man eine Wahrscheinlichkeitsverteilung über der Strategienmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1 } bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_2 } als reine Strategien der Spieler. Es handelt sich hierbei um besondere gemischte Strategien, bei denen eine Strategie aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_i \in [0,1] } die Wahrscheinlichkeit, dass Spieler Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i } Kopf wählt. Bei Unabhängigkeit ergeben sich dann die folgenden Wahrscheinlichkeiten für die verschiedenen Strategiekombinationen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{array}{|c||c|c|} \hline P(s_1,s_2) & K & Z \\ \hline \hline K & s_1s_2 & s_1(1-s_2) \\ \hline Z & (1-s_1)s_2 & (1-s_1)(1-s_2) \\ \hline \end{array} }

Als Erwartungswert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U } für die Auszahlung erhält man dann:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U(s_1,s_2)= s_1s_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 (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u=U } ).

Bezeichnet man allgemein die Wahrscheinlichkeiten, die Spieler 1 für seine reinen Strategien aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1=\{s_1^1,s_1^2...,s_1^m\} } wählt, mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x=(x_1,x_2,...,x_m)^T } und ebenso die Wahrscheinlichkeiten für Spieler 2 mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y=(y_1,y_2,...,y_n)^T } , so lässt sich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U=E[u]} als Matrizenprodukt schreiben; Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A } bezeichnet hierbei die Auszahlungsmatrix des Spiels:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U=x^TAy } .

Um eine beste Reaktion von Spieler 1 auf die gemischte Strategie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y=(y_1,y_2,...,y_n)^T } von Spieler 2 zu finden, muss also das lineare Optimierungsproblem

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{argmax}_{x \in \mathbb{R}^m} \quad x^TAy}     unter der Nebenbedingung    Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x=(x_1,x_2,...,x_m)^T } von Spieler 1, indem man folgendes lineare Optimierungsproblem löst:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{argmin}_{y \in \mathbb{R}^n} \quad x^TAy}     Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{argmax}_{x \in \mathbb{R}^m} \quad \text{min}_{y \in \mathbb{R}^n} \quad x^TAy}     unter der Nebenbedingung    Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{argmin}_{y \in \mathbb{R}^n} \quad \text{max}_{x \in \mathbb{R}^m} \quad x^TAy}     unter der Nebenbedingung    Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A } eine reelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m \times n} -Matrix. Dann existiert ein Tripel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x^*,y^*,V) } , so dass

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {x^*}^TAy \geq V \quad \forall y } und

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^TAy^* \leq V \quad \forall x } .

Hierbei stehen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x } bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^* } für Wahrscheinlichkeitsverteilungen über die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m } Zeilen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A } , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y } bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y^* } für Wahrscheinlichkeitsverteilungen über die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n } Spalten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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)

Matching Pennies

Es sollen nun für „Matching Pennies“ (A) die Maximin-Strategien für Spieler 1 in gemischten Strategien ermittelt werden:

Zunächst muss für jede vorgegebene Strategie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \overline{s}_1 } von Spieler 1 seine minimale Auszahlung bestimmt werden, die sich durch optimales Verhalten von Spieler 2 ergibt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{min}_{s_2 \in [0,1]}\quad u(\overline{s}_1,s_2) } .

Es gilt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u(\overline{s}_1,s_2)=\overline{s}_1s_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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_2 } kommt es nur darauf an, ob der Ausdruck Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 4\overline{s}_1-2 } in der letzten Klammer positiv, Null oder negativ ist. Dieser Ausdruck ist positiv, falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textstyle \overline{s}_1 > \frac{1}{2} } . Dann wird das Minimum für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_2=0 } erreicht, und beträgt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1-2\overline{s}_1 } . Der Ausdruck in der Klammer ist negativ, falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textstyle \overline{s}_1 < \frac{1}{2} } . Dann wird das Minimum für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_2=1 } erreicht, und beträgt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -1+2\overline{s}_1 } . Der Ausdruck in der Klammer ist Null, falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textstyle \overline{s}_1 = \frac{1}{2}} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_2 } hat dann keinen Einfluss auf das Minimum, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u(\overline{s}_1,s_2) } ist dann unabhängig von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_2 } immer 0.

Datei:Max123.png

Grafik

Damit lässt sich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{min}_{s_2 \in [0,1]}\quad u(\overline{s}_1,s_2) } wie folgt schreiben:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 man für die Bestimmung der Maximin-Strategie für Spieler 1 folgendes Optimierungsproblem:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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) } .

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U_{\min} } ist streng monoton steigend auf dem Intervall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textstyle \left[0,\frac{1}{2} \right] } und streng monoton fallend auf dem Intervall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textstyle \left[\frac{1}{2},1 \right] } ; das Maximum von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U_{\min} } liegt also bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textstyle s_2^*=\frac{1}{2} } .

Der Wert des Spiels beträgt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_1:= P(S) \geq P(St) \geq P(P)=:p_3 } , wobei mindestens eine der Ungleichungen strikt ist. Insbesondere ist dann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_1>p_3} . Wenn Spieler 2 jetzt "Stein" spielt, so ist die erwartete Auszahlung von Spieler 1 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Eu=p_1 \cdot (-1) + p_3 \cdot 1=p_3-p_1<0 } .

Wählt Spieler 1 hingegen alle drei Wahrscheinlichkeiten gleich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textstyle \frac{1}{3} } , also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textstyle \operatorname E(u)=x^TAy=[x^TA]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 die Wahrscheinlichkeiten bei Spieler 1 auf Schere, Stein und Papier in anderer Größenreihenfolge verteilt sind, so gilt eine analoge Argumentation, falls Spieler 2 die Strategie mit der mittleren Wahrscheinlichkeit spielt.

Zu jeder von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.