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.G. Owen: Spieltheorie. Springer-Verlag, 1971, S. 11. 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 . Jedem Spieler wird eine Strategiemenge zugeordnet. Die Strategiemenge enthält alle Strategien, aus denen Spieler bei Durchführung des Spiels eine Strategie auswählt. Schließlich gibt es für jeden Spieler eine Auszahlungsfunktion , die jeder Strategiekombination eine Auszahlung für Spieler zuordnet.
Definition: Unter einem Spiel in Normalform versteht man ein Tripel Manfred J. Holler, Gerhard Illing: Einführung in die Spieltheorie. Springer, 2008, ISBN 978-3-540-69372-7, S. 4., wobei .
Konstantsummenspiel
Bei einem Konstantsummenspiel wird bei jeder Strategiekombination, also jedem Spielergebnis die gleiche Auszahlungssumme an alle Spieler ausgeschüttet.
Definition: Ein Spiel heißt Konstantsummenspiel mit Auszahlungssumme , wenn gilt: .
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 heißt Nullsummenspiel, wenn: .
Spieltheoretisch besteht kein wesentlicher Unterschied zwischen Konstantsummen- und Nullsummenspielen: Aus einem Konstantsummenspiel mit Auszahlung entsteht ein äquivalentes Nullsummenspiel , indem man einem beliebigen Spieler vor Spielbeginn den Betrag zuordnet, den er nach Spielende sicher verliert und somit erhält. Die Auszahlungen im Spiel 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 heißt Zwei-Personen-Nullsummenspiel, wenn: .
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 und , also , so gilt .
Es ist daher möglich, die Definition eines Zwei-Personen-Nullsummenspiels zu vereinfachen:
Definition: Ein Zwei-Personen-Nullsummenspiel ist ein Tripel , wobei .Sylvain Sorin: A First Course on Zero-Sum Repeated Games. Springer-Verlag, Berlin / Heidelberg 2002, S. 151.
Die Spielermenge ist hierbei natürlicherweise ; die Auszahlungsfunktion bezieht sich auf Spieler 1, Spieler 2 hat dann die Auszahlungsfunktion .
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 für Spieler 1, also einem Element aus , jede Spalte entsprechend einer Strategie für Spieler 2. In den Feldern der Bimatrix stehen die Auszahlungen und . Die Bimatrix stellt also eine Wertetabelle der Funktionen und 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 .
als Bimatrix , , , ,
In der vereinfachten Darstellung erhält man dann:
Als Matrix des Spiels bezeichnet man dann die -Matrix A:
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 2KopfZahlKopf1 , −1 −1, 1 Zahl−1 , 1 1 , −1
In der vereinfachten Darstellung erhält man folgende Matrix:
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 . Die Menge aller möglichen Strategiekombinationen (Kartesisches Produkt) ist dann:
.
In Form einer BimatrixChristian Rieck: Spieltheorie Eine Einführung. Christian Rieck Verlag, 1993, S. 80. sieht das Spiel dann folgendermaßen aus:
Auszahlungsmatrix für Spieler 1 und Spieler 2SchereSteinPapierSchere0, 0-1, 11, -1Stein1, -10, 0-1, 1Papier-1, 11, -10, 0
In der vereinfachten Matrixdarstellung sieht „Schere, Stein, Papier“ dann so aus:
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 2LinksMitteRechtsOben−2, 20, 0−3, 3Unten3, −32, −24, −4
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 , also ein Kontinuum.
(D) mit und .
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 von Spieler 1 auf Spieler 2 ist die mengenwertige Funktion .
Man beachte, dass bei der vereinfachten Darstellung in der Definition einer besten Reaktion für Spieler 2 minimiert statt maximiert wird:
Definition: Die Reaktionskorrespondenz von Spieler 2 auf Spieler 1 ist die mengenwertige Funktion .
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 ist ein Nash-Gleichgewicht, wenn gilt: .
Die Definition verändert sich für die vereinfachte Darstellung zu:
Definition: Die Strategiekombination ist ein Nash-Gleichgewicht, wenn gilt: .
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 ist eine Minimax-Strategie für Spieler 1, wenn gilt: .
In der vereinfachten Darstellung wird daraus:
Definition: Die Strategie ist eine Minimax-Strategie für Spieler 1, wenn gilt: .
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 erhält. Da es sich um ein Nullsummenspiel handelt, bedeutet dies, dass Spieler 1 also mindestens gewinnt.
Für Spieler 2 gilt bei Anwendung einer Minimax-Strategie, dass er mit einer Minimax-Strategie den Gewinn von Spieler 1 auf beschränken kann. Es gilt also .G. Owen: Spieltheorie. Springer Verlag, 1971, S. 17. Falls 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 ist eine Maximin-Strategie für Spieler 1, wenn gilt: .
In der vereinfachten Darstellung wird daraus:
Definition: Die Strategie ist eine Maximin-Strategie für Spieler 1, wenn gilt: .
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 , 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 . Wenn ein Gleichgewicht vorliegt, so bezeichnet man mit den Wert des Spiels. 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 unteren Spielwert und oberen Spielwert des Spiels.B. Rauhut, N. Schmitz, E.-W. Zachow: Spieltheorie. Teubner, Stuttgart 1979, S. 138.
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.