Nullsummenspiel

Für endliche Nullsummenspiele mit zwei Spielern ergeben die verschiedenen spieltheoretischen Lösungskonzepte des Nash-Gleichgewichts, des Minimax und des Maximin alle die gleiche Lösung. Wenn es den Spielern erlaubt ist, eine gemischte Strategie zu spielen, hat das Spiel immer ein Gleichgewicht.

BeispielBearbeiten

Ein Null-sum game

Blau Rot	A	B	C
1	-30 30	10 -10	-20 20
2	10 -10	-20 20	20 -20

Die Auszahlungsmatrix eines Spiels ist eine praktische Darstellung. Betrachten wir zum Beispiel das Nullsummenspiel für zwei Spieler, das rechts oder oben abgebildet ist.

Die Spielreihenfolge ist wie folgt: Der erste Spieler (rot) wählt heimlich eine der beiden Aktionen 1 oder 2; der zweite Spieler (blau), der die Wahl des ersten Spielers nicht kennt, wählt heimlich eine der drei Aktionen A, B oder C. Dann werden die Entscheidungen aufgedeckt und die Punktzahl jedes Spielers wird entsprechend der Auszahlung für diese Entscheidungen beeinflusst.

Beispiel: Rot wählt Aktion 2 und Blau wählt Aktion B. Bei der Verteilung des Gewinns gewinnt Rot 20 Punkte und Blau verliert 20 Punkte.

In diesem Beispielspiel kennen beide Spieler die Gewinnmatrix und versuchen, die Anzahl ihrer Punkte zu maximieren. Rot könnte wie folgt argumentieren: „Mit Aktion 2 kann ich bis zu 20 Punkte verlieren und nur 20 gewinnen, und mit Aktion 1 kann ich nur 10 verlieren, aber bis zu 30 gewinnen, also sieht Aktion 1 viel besser aus.“ Mit ähnlichen Überlegungen würde Blau Aktion C wählen. Wenn beide Spieler diese Aktionen ausführen, gewinnt Rot 20 Punkte. Wenn Blau die Überlegungen von Rot vorhersieht und sich für Aktion 1 entscheidet, kann Blau Aktion B wählen, um 10 Punkte zu gewinnen. Wenn Rot seinerseits diesen Trick vorhersieht und sich für Aktion 2 entscheidet, gewinnt Rot 20 Punkte.

Émile Borel und John von Neumann hatten die grundlegende Einsicht, dass die Wahrscheinlichkeit einen Ausweg aus diesem Rätsel bietet. Anstatt sich für eine bestimmte Aktion zu entscheiden, ordnen die beiden Spieler ihren jeweiligen Aktionen Wahrscheinlichkeiten zu und verwenden dann ein Zufallsgerät, das entsprechend dieser Wahrscheinlichkeiten eine Aktion für sie auswählt. Jeder Spieler berechnet die Wahrscheinlichkeiten so, dass der maximale erwartete Punktverlust unabhängig von der Strategie des Gegners minimiert wird. Dies führt zu einem linearen Programmierproblem mit den optimalen Strategien für jeden Spieler. Diese Minimax-Methode kann wahrscheinlich optimale Strategien für alle Zwei-Spieler-Nullsummenspiele berechnen.

Für das obige Beispiel stellt sich heraus, dass Rot die Aktion 1 mit der Wahrscheinlichkeit 4/7 und die Aktion 2 mit der Wahrscheinlichkeit 3/7 wählen sollte, und Blau sollte den drei Aktionen A, B und C die Wahrscheinlichkeiten 0, 4/7 und 3/7 zuweisen. Rot wird dann im Durchschnitt 20/7 Punkte pro Spiel gewinnen.

LösenBearbeiten

Das Nash-Gleichgewicht für ein Nullsummenspiel mit zwei Spielern kann durch Lösen eines linearen Programmierproblems gefunden werden. Angenommen, ein Nullsummenspiel hat eine Auszahlungsmatrix M, in der das Element Mi,j die Auszahlung ist, die man erhält, wenn der minimierende Spieler die reine Strategie i und der maximierende Spieler die reine Strategie j wählt (d.h. der Spieler, der die Auszahlung zu minimieren versucht, wählt die Zeile und der Spieler, der die Auszahlung zu maximieren versucht, wählt die Spalte). Angenommen, jedes Element von M ist positiv. Das Spiel wird mindestens ein Nash-Gleichgewicht haben. Das Nash-Gleichgewicht kann gefunden werden (Raghavan 1994, S. 740), indem das folgende lineare Programm gelöst wird, um einen Vektor u zu finden:

Minimize: ∑ i u i {\displaystyle \sum _{i}u_{i}} Unter Berücksichtigung der Nebenbedingungen: u ≥ 0 M u ≥ 1.

Die erste Bedingung besagt, dass jedes Element des u-Vektors nicht negativ sein muss, und die zweite Bedingung, dass jedes Element des M u-Vektors mindestens 1 sein muss. Für den resultierenden u-Vektor ist der Kehrwert der Summe seiner Elemente der Wert des Spiels. Multipliziert man u mit diesem Wert, erhält man einen Wahrscheinlichkeitsvektor, der die Wahrscheinlichkeit angibt, dass der maximierende Spieler jede der möglichen reinen Strategien wählt.

Wenn die Spielmatrix nicht alle positiven Elemente hat, addiert man einfach eine Konstante zu jedem Element, die groß genug ist, um sie alle positiv zu machen. Das erhöht den Wert des Spiels um diese Konstante und hat keine Auswirkung auf die gemischten Strategien des Gleichgewichts.

Die gemischte Strategie des Gleichgewichts für den minimierenden Spieler kann durch Lösen des Duals des gegebenen linearen Programms gefunden werden. Oder man kann sie finden, indem man das obige Verfahren anwendet, um eine modifizierte Auszahlungsmatrix zu lösen, die die Transponierte und Negierte von M ist (indem man eine Konstante hinzufügt, so dass sie positiv ist), und dann das resultierende Spiel löst.

Wenn alle Lösungen des linearen Programms gefunden werden, stellen sie alle Nash-Gleichgewichte für das Spiel dar. Umgekehrt kann jedes lineare Programm in ein Nullsummenspiel mit zwei Spielern umgewandelt werden, indem man die Variablen so ändert, dass es die Form der obigen Gleichungen annimmt. Solche Spiele sind also im Allgemeinen äquivalent zu linearen Programmen.

Universelle LösungBearbeiten

Wenn das Vermeiden eines Nullsummenspiels eine Aktionswahl mit einer gewissen Wahrscheinlichkeit für die Spieler ist, ist das Vermeiden immer eine Gleichgewichtsstrategie für mindestens einen Spieler bei einem Nullsummenspiel. Für jedes Nullsummenspiel mit zwei Spielern, bei dem ein Nullsummenspiel unmöglich oder nicht glaubwürdig ist, nachdem das Spiel begonnen hat, wie z. B. Poker, gibt es keine andere Nash-Gleichgewichtsstrategie als das Vermeiden des Spiels. Selbst wenn es ein glaubwürdiges Null-Null-Unentschieden gibt, nachdem ein Nullsummenspiel begonnen wurde, ist es nicht besser als die Vermeidungsstrategie. In diesem Sinne ist es interessant zu sehen, dass die Belohnungsstrategie bei der Berechnung der optimalen Wahl bei allen Nullsummenspielen mit zwei Spielern überwiegt, unabhängig davon, ob das Spiel begonnen wird oder nicht.

Das gebräuchlichste oder einfachste Beispiel aus dem Teilgebiet der Sozialpsychologie ist das Konzept der „sozialen Fallen“. In einigen Fällen kann die Verfolgung individueller persönlicher Interessen das kollektive Wohlergehen der Gruppe verbessern, aber in anderen Situationen führt die Verfolgung persönlicher Interessen durch alle Parteien zu einem gegenseitig destruktiven Verhalten.

KomplexitätBearbeiten

Es wurde von Robert Wright in seinem Buch Nonzero: The Logic of Human Destiny (Die Logik des menschlichen Schicksals) die These aufgestellt, dass die Gesellschaft mit zunehmender Komplexität, Spezialisierung und gegenseitiger Abhängigkeit immer weniger Nullsummen aufweist.