Einführung in die Spieltheorie

Inhaltsverzeichnis

1 Einleitung

2 Definitionen
2.1 Das Spiel und seine Bestandteile
2.2 Extensivform
2.3 Informationsmengen
2.4 Allgemeinwissen
2.5 Informationskategorien

3 Matrixspiele
3.1 Normalform
3.2 Nash-Gleichgewicht
3.3 Reine und gemischte Strategien
3.4 Der Wert und optimale Strategien
3.5 Dominierte Strategien
3.6 Lösen aller-Matrizen

4 Zwei Personen Nicht-Kooperative Spiele
4.1 Darstellung als Bimatrix
4.2 Safety-Level
4.3 Nash-Gleichgewicht
4.4 Dominierte Strategien
4.5 Konstantsummenspiele
4.6 Gefangenendilemma
4.7 Braess-Paradoxon

5 Kombinatorische Spieltheorie
5.1 P- und N-Positionen
5.2 Nim

6 Quellenverzeichnis

7 Register

8 Selbstständigkeitserklärung

"Statistically, it would seem improbable that any mathematician or scientist, at the age of 66, would be able through continued research efforts, to add much to his or her previous achievements. However I am still making the effort and it is conceivable that with the gap period of about 25 years of partially deluded thinking providing a sort of vacation my situation may be atypical. Thus I have hopes of being able to achieve something of value through my current studies or with any new ideas that come in the future."

John Forbes Nash

1 Einleitung

Die Spieltheorie beschäftigt sich mit dem Modellieren und Analysieren von Spielen. Um ein Spiel handelt es sich immer, wenn zwei^[1] oder mehrere Personen, die Spieler, Entscheidungen fällen, die nicht nur ihr eigenes Ergebnis, sondern auch jenes der anderen Spieler beeinflussen. Hierbei kann es sich um Spiele handeln, die man aus dem Alltag kennt (z. B. Schach, Go, Poker, usw.), aber auch Vorgänge in der Wirtschaft können damit modelliert werden. Wenn beispielsweise zwei große Firmen, die um Kunden konkurrieren, den Preis ihrer Produkte festlegen, dann befinden sie sich in einem Spiel. Jeder versucht den Preis möglichst hoch zu halten, damit der Gewinn steigt, aber auch möglichst unter dem Preis des Konkurrenten, um eine größere Menge an Kunden zu gewinnen.

Die Spieltheorie soll nun helfen diese Spiele zu analysieren: Kann ich gewinnen, wenn ich als Erster beginne? Wenn ja, wie? Ist das Spiel gerecht oder favorisiert es einen Spieler? Wie maximiere ich meinen Gewinn? Ist mir ein minimaler Gewinn garantiert? Was passiert, wenn ich wiederholt spiele? Stellt sich ein Gleichgewicht ein?

Zur Ernüchterung sei jedoch gesagt, dass Grenzen existieren. Eine komplette Analyse von sehr großen Spielen wie Schach ist praktisch unmöglich. Auch lassen sich durch die Hilfe der Mathematik nie die Entscheidungen der Mitspieler oder Zufallselemente vorhersagen, es wird lediglich angenommen, dass alle Spieler möglichst vernünftig handeln und versuchen ihren eigenen Gewinn zu maximieren. Die Spieltheorie ist nicht wie andere Bereiche der Mathematik axiomatisch aufgebaut und strikt definiert, vielmehr bietet sie Hilfsmittel zur Modellierung und Analyse von Spielen, deren Definitionen einer allgemeinen Übereinkunft folgen, damit wissenschaftliche Arbeiten untereinander vergleichbar bleiben.

Der Leser wird dabei in vier Kapiteln in die Spieltheorie eingeführt, wobei der Schwerpunkt auf den sogenannten Matrixspielen liegt. Danach soll er die benötigten Hilfsmittel und Gedankenstrukturen so verinnerlicht haben, dass er einfache Spiele selbstständig lösen kann.

Im ersten Kapitel beschäftigen wir uns mit der Definition eines Spiels, schauen uns also dessen Elemente und deren Beziehungen näher an. Wir werden lernen, wie man Spiele modelliert und graphisch darstellt, wobei nicht nur die Vorgänge in einem Spiel, sondern auch die Informationen, welche die Spieler besitzen, relevant sind.

Im darauffolgenden Kapitel werden wir eine besondere Art von Spielen, die Matrixspiele, bei denen der Gewinn des einen Spielers sogleich der Verlust des anderen ist, kennen lernen. Diese können mit Hilfe einer Matrix vollständig beschrieben werden, was es uns ermöglicht grundlegende Werkzeuge der Linearen Algebra darauf anzuwenden. Es wird dabei beschrieben, wie man auf die oben formulierten Eingangsfragen Antworten erhält und inwieweit diese sich auf die Realität übertragen lassen.

Danach werden wir im dritten Kapitel unsere anfängliche Annahme, dass der Verlust des einen Spielers immer zugleich der Gewinn des anderen ist, verwerfen und damit Bimatrixspiele erhalten. Die bereits bekannten Begriffe werden auf diese Art von Spielen erweitert und noch offene Beweise schließlich geführt. Dabei stellt das Braess-Paradoxon eine schöne Abrundung mit Bezug zur Realität dar.

Im letzten Kapitel beschäftigen wir uns noch kurz mit kombinatorischen Spielen, zu denen z. B. auch Schach gehört, das wir jedoch aus verständlichen Gründen nicht analysieren können. Interessante Streichholzspiele wie Nim bieten uns dazu jedoch genug Möglichkeiten.

Schaubilder zur Illustration, viele Beispiele und geschichtliche Hintergründe sollen hierbei nicht vernachlässigt werden.

Diese Einführung ist dabei an Erstsemesterstudenten und Hobbymathematiker gerichtet, die mit den gebräuchlichen Notationen und der Vektorrechnung vertraut sind. Ein gewisses Interesse an Spielen ist natürlich auch nicht fehl am Platz.

Als weiterführende Lektüre empfiehlt sich ein Vorlesungsskript von Dr. Andrea Schalk, das vor allem auf die praktische Analyse z. B. von Schach detailliert eingeht. Ebenfalls leicht verständlich ist ein Skript von Professor Thomas Ferguson der University of California, das nicht nur durch seine ausgezeichnete Darstellung hervorsticht.

2 Definitionen

2.1 Das Spiel und seine Bestandteile

Wir folgen im Weiteren der Definition nach Rasmusen 2007, S. 12f.

Ein Spiel besteht aus mehreren Spielern, Aktionen, Auszahlungen und Informationen, die alle zusammen als die Regeln des Spiels aufgefasst werden. Diese sind den Spielern in vollem Umfang immer bekannt.

Ein Spieler kann Entscheidungen, Aktionen, in verschiedenen Abschnitten treffen. Jeder Spieler handelt dabei rational, versucht also am Ende des Spiels eine möglichst große Auszahlung zu erhalten. Als Egoist ist er dabei nur auf seinen eigenen Vorteil aus, auch wenn dies für seine Mitspieler einen großen Nachteil bedeutet. Hierbei bezieht er Informationen über seine aktuelle Position im Spielgeschehen oder jede andere Art der Information über seine Gegenspieler mit ein. Die Spieler kann man hierbei auf verschiedene Arten benennen (z. B. Spieler A, Spieler B, ... ), jedoch werden dazu oft natürliche Zahlen verwendet.

Definition 2.1.1: Ein Spielerist ein Akteur in einem Spiel, der Aktionen ausführt, um eine möglichst große Auszahlung zu erhalten. ist dabei die Menge der Spieler.

Aktionen können hierbei jegliche Art von Entscheidungen sein, die den Verlauf des Spiels beeinflussen: Der weiße Spieler zieht den Bauer von C2 nach C4 oder Firma A erhöht den Preis ihres Produktes um einen Euro. Je nachdem wie weit das Spiel fortgeschritten ist, stehen jedem Spieler verschiedene Aktionen zur Verfügung, aus denen er wählen kann.

Definition 2.1.2: Eine Aktion oder Zug eines Spielers ist eine Entscheidung, die er an einem bestimmten Punkt des Spiels treffen kann.

Auszahlungen werden immer am Ende des Spiels getätigt. Sie können Geld, eine Form der Bestrafung, die man möglichst gering zu halten versucht oder jede andere Form von Vor- oder Nachteil für den betreffenden Spieler sein. Um dies zu vereinfachen, vergibt man häufig Zahlen, die den Wert einer Auszahlung festlegen sollen. Diese (reellen) Zahlen nennt man Nutzen. Je höher der Wert, desto wertvoller ist diese Auszahlung für den jeweiligen Spieler. Ein Kandidat bei "Wer wird Millionär" hat beispielsweise die zwei Aktionen "Aufhören" und "Zocken". Wählt er die erste, so erhält er sofort eine Auszahlung von 10.000 €. Wählt er dagegen die zweite, so erhält er mit einprozentiger Wahrscheinlichkeit 1.000.000 €. Die durchschnittlichen Auszahlungen sind gleich, jedoch werden sich die meisten Spieler für die erste Aktion entscheiden, da ihnen dort der Geldgewinn sicher ist. Deswegen ist es häufig besser Auszahlungen, die ja letztendlich darstellen sollen, wie sehr ein Spieler diesen Ausgang des Spiels erreichen möchte, durch Nutzen darzustellen. Ein risikoscheuer Spieler würde der Auszahlung, die er durch die Wahl der Aktion "Aufhören" erhält, einen größeren Nutzen (z. B. die 10) zuordnen, als der Auszahlung, die er durchschnittlich beim Zocken erhält (z. B. 3). Steht er nun vor der Entscheidung, ob er aufhören möchte, vergleicht er nicht die durchschnittlichen Gewinne, die für beide Aktionen 10.000 € betragen, sondern den Nutzen beider Aktionen und stellt fest, dass er durch "Aufhören" einen größeren Nutzen erreicht. Beim Vergleich des durchschnittlichen Gewinns, wäre er dagegen zu dem Ergebnis gekommen, dass beide Aktionen ihm den gleichen Gewinn bringen, was jedoch nicht stimmt.

An diesem Beispiel erkennt man auch, dass im Allgemeinen beim Wort "Auszahlung" kein Unterschied zwischen tatsächlicher Auszahlung, dem Gewinn, den man nach den Regeln erhält (z. B. Punkte, Geld), durchschnittlicher bzw. zu erwartender Auszahlung (wenn Wahrscheinlichkeiten berücksichtigt werden) und dem Nutzen einer Auszahlung gemacht wird. Wie man am besten jeder Auszahlung einen Nutzen zuordnet, beschreibt die Nutzentheorie.

Definition 2.1.3: Eine Auszahlung ist der Nutzen oder Gewinn, den ein Spieler am Ende des Spiels erhält.

Befinden sich Zufallselemente wie das Werfen einer Münze im Spiel, so werden sie von einem Pseudo-Spieler namens Natur ausgeführt. Wie der Name schon sagt, ist sie kein richtiger Spieler, sondern dient nur dem Bestimmen des Zufallsereignisses (z. B. ob Kopf oder Zahl fällt). Ist die Natur am Zug, so wird gemäß den vorgegebenen Wahrscheinlichkeiten berechnet, welchen Zug sie macht. Eine Berechnung kann auch schon im vorhinein erfolgen, jedoch darf deswegen das Ergebnis den Spielern nicht früher bekannt werden, da sich sonst die Informationen der Spieler und damit die Regeln des Spiels ändern. Wetten beispielsweise zwei Spieler, auf welcher Seite eine geworfene Münze liegen bleibt, so darf sie von einer dritten Person schon vor dem Wetten geworfenen werden, ohne dass die zwei Spieler etwas davon erfahren. Das Spiel bleibt das gleiche. Anders verhält es sich jedoch, wenn die dritte Person den Spielern das Ergebnis vor dem Wetten verrät. So wissen diese schon früher als durch die Regeln festgelegt den Ausgang des Zufallsereignisses. Bei Gesellschaftsspielen wird der Zug von einem Spielleiter übernommen. Modelliert man dagegen eine reale Situation, möchte z. B. eine Firma ihren Umsatz im nächsten Jahr abhängig von den Entscheidungen ihrer Konkurrenten abschätzen und benötigt dazu die Inflationsrate des kommenden Jahres, so können zwar Experten Vorraussagen anstellen, mit denen sich der Umsatz dann abschätzen lässt, wie hoch sie tatsächlich ist, wird erst später öffentlich und kann durch die Modellierung nicht erfasst werden.

Definition 2.1.4: Die Natur ist ein Pseudo-Spieler, der während des Spiels nach gewissen Wahrscheinlichkeiten handelt.

Oft kann ein Spieler an verschiedenen Stellen des Spiels mehrmals Aktionen ausführen, also Entscheidungen treffen. Um die Analyse zu erleichtern, fasst man nun alle möglichen Kombinationen von Aktionen zu der Menge der Strategien zusammen. Eine Strategie bestehend aus einer Familie von Aktionen gibt also immer an, in welcher Stufe des Spiels der Spieler sich für welche Aktion entscheidet. Sie hält also für jede erdenkliche Situation, in der sich der Spieler im Lauf des Spiels befinden kann, eine Aktion parat. Der Begriff ist von dem sonst gebräuchlichen Begriff der Strategie zu unterscheiden. Entscheidet sich ein Spieler vor dem Spiel für eine Strategie, so bedarf es keinerlei Entscheidung mehr von ihm, vielmehr ist schon ganz genau festgelegt, was für Züge er wann macht, er muss sie also nur noch gemäß seinem Plan, der Strategie, ausführen. Es kann für ein Spiel sehr viele Strategien geben, da sie jeder Situation eine Aktion zuordnet. Es muss also sowohl die Position im Spiel als auch die vorhandene Information des Spielers berücksichtigt werden. Eine mögliche Strategie könnte also so aussehen: "Falls Spielerin B vor zwei Zügen sich für Aktion X entschieden hat und die Natur Aktion Y gespielt hat, so wähle Aktion Z, wenn du das nächste Mal ziehen darfst. Falls Spielerin B".

Man sieht, dass durch die vielen Bedingungen, an die eine Strategie geknüpft ist, eine konkrete Ausformulierung bei komplexeren Spielen damit unmöglich wird. Der Schachcomputer Deep Blue z. B. spielt genau eine Strategie. Für jede erdenkliche Situation hat er eine Aktion parat. Wenn das Programm keine Zufallselemente verwendet und der Gegner bei zwei Partien genau die gleichen Züge ausführt, so wird dies auch Deep Blue machen. Ein Statement von IBM zur berühmten Partie Deep Blue gegen Garri Kasparow:

"Any changes in the way Deep Blue plays chess must be performed by the members of the development team between games. Garry Kasparov can alter the way he plays at any time before, during, and/or after each game." (IBM 1997)

Definition 2.1.5: Eine Strategie eines Spielers ist eine Vorschrift, welche Aktionen er in den jeweiligen Situationen je nach verfügbaren Informationen ausführen soll. Die Menge der Strategiendes Spielersenthält alle ihm zur Verfügung stehenden Strategien.

Um nun das Ergebnis, also die Auszahlungen jedes Spielers, zu berechnen, betrachtet man ein Strategieprofil. Dieses Profil enthält zu jedem Spieler seine Strategie, für die er sich entschieden hat. Damit kann man nun das Spiel simulieren, indem man abhängig von der Strategie die Aktionen jedes Spielers und der Natur ausführt und damit die jeweiligen Auszahlungen erhält. Durch das Berechnen des Ergebnisses für jedes mögliche Strategieprofil hat man alle Möglichkeiten, die das Spiel bietet, berücksichtigt. Dies ist oft jedoch praktisch unmöglich.

Definition 2.1.6: Ein Strategieprofil ist eine Familie von Strategien, die jedem Spielereine Strategiezuordnet.sei die Menge aller Strategieprofile.

Um das Berechnen des Ergebnisses zu ermöglichen, muss für jedes Spiel eine Auszahlungsfunktion existieren. Durch sie erhält man für den jeweiligen Spieler die Auszahlung in Abhängigkeit eines Strategieprofils, also abhängig davon, was für Entscheidungen er und die anderen Mitspieler im Verlauf des Spiels treffen werden.

Definition 2.1.7: Eine Funktion, die jedem Strategieprofildie Auszahlung des Spielerszuordnet, nennt man Auszahlungsfunktio n. Die Familieist das Ergebnis des Spiels für das Strategieprofil.

2.2 Extensivform

Um ein Spiel komplett darzustellen, also die oft durch Worte (Gesellschaftsspiele) oder durch Beobachtung komplexer Vorgänge (reale Situationen) gegebenen Spielregeln mathematisch zu modellieren, bieten sich verschiedene Möglichkeiten an. Eine davon ist die sogenannte Extensivform. Hierbei greift man auf die Hilfe der Graphentheorie zurück. Das Spiel wird als Menge von Knoten und Kanten dargestellt. Jeder Knotenpunkt stellt dabei eine einzigartige Position im Spiel dar. Von ihm gehen mehrere Kanten zu anderen Knoten, die sogenannten Nachfolger dieses Knotens. Eine Kante stellt dabei eine Aktion dar, die der Spieler, der an der Reihe ist, an dieser Stelle ausführen kann.

Ein Spiel beginnt bei der Wurzel bzw. dem Anfangsknoten. Der Spieler (hierzu kann auch die Natur zählen), der dort an der Reihe ist, wählt aus den verfügbaren Kanten, die mit diesem Knoten verbunden sind, eine aus. Diese Kante ist nun mit einem anderen Knoten verbunden. Das Spiel wird nun an diesem Nachfolger fortgesetzt und der Spieler, der dort an der Reihe ist, muss nun wiederum aus den verfügbaren Kanten, seinen Aktionen an dieser Position im Spiel, eine auswählen. Das Spiel wird dann bei dem entsprechenden Nachfolger des aktuellen Knotens fortgesetzt. Die Natur führt ihre Züge nach den Wahrscheinlichkeiten, die bei den jeweiligen Kanten notiert sind, aus. Das Spiel endet, wenn ein Endknoten erreicht wurde, also ein Knoten, der keine Nachfolger hat. Dort werden nun die Auszahlungen für alle Spieler gemäß dem dort notierten Ergebnis vorgenommen.

Bei der Extensivform handelt es sich um einen gewurzelten Baum. In ihm existiert von der Wurzel zu jedem anderen Knoten ein einzigartiger Pfad. Dabei ist ein Pfad von einem Knotenzu einem anderen eine geordnete Menge von paarweise verschiedenen Knoten, wobei zwischen benachbarten Knoten eine Kante existieren muss, die diese geeignet miteinander verbindet. Eine Kante muss also vonzuführen, eine andere vonzu, usw. Aus der Einzigartigkeit folgt auch, dass keine Kreise existieren. Es kann in einem Spiel vorkommen, dass man durch verschiedene Aktionen der Spieler an Stellen im Spiel ankommt, die sich durch nichts außer dem Weg, wie man zu ihnen gelangt ist, unterscheiden. Im Schach kann z. B. man eine gewisse Aufstellung, also die Positionen aller Spielfiguren, durch viele verschiedene Züge erreichen. In der Extensivform werden die Positionen im Spiel durch verschiedene Knoten dargestellt, wodurch so ein Baum schnell mit der Komplexität des Spiels wächst.

Abbildung 1 zeigt das sogenannte Basic Endgame Poker, eine stark vereinfachte Form des Pokers, in Extensivform.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Basic Engame Poker in Extensivform

Es spielen zwei Spieler, Spieler A und B um Chips im Pot. Anfangs legt jeder einen sogenannten Ante von einem Stück in den Pot. Dann wird dem ersten Spieler eine für den zweiten Spieler verdeckte Karte ausgeteilt, die mit einer Wahrscheinlichkeit voneine Gewinnkarte und inaller Fälle eine Verliererkarte ist. Im Baum wird dies durch einen Initialzug der Natur, also dem ersten Zug im Spiel, dargestellt. In beiden Fällen (s.h. Nachfolger der Wurzel) hat Spieler A nun die Auswahl einen Betrag von zwei Stücken in den Pot zu setzen (bet) oder nichts zu unternehmen (c heck). Im letzteren Fall gewinnt er den Pot, also seinen Einsatz und den Ante des Gegners, wenn er eine Gewinnerkarte (linke Seite des Baums) hat und verliert seinen Ante, wenn er eine Verliererkarte auf der Hand hält (rechte Seite des Baums). An den Endknoten der beiden check -Kanten ist die jeweilige Auszahlung (1 bzw. -1) angegeben. Es steht dort immer nur die Auszahlung von Spieler A, da der Gewinn des einen Spielers immer auch der Verlust des anderen Spielers ist. Auch beträgt der Gewinn von Spieler A nicht zwei Stücke, wie man anfangs annehmen könnte (jeweils der Ante von Spieler A und B befinden sich im Pot), da es sinnvoll ist den Einsatz eines Spielers nicht zu seinem Gewinn dazuzurechnen.

Entscheidet sich Spieler A dagegen zu setzen (bet), so legt er zwei Stücke in den Pot und Spielerin B ist an der Reihe, da dieser Knoten sich in dem gestrichelten Bereich von Spielerin B befindet. Diese hat nun die Wahl, ebenfalls zwei Stücke zu setzen (call) oder auszusteigen (fold). Im letzteren Fall verliert sie automatisch ihren Ante an Spieler A, im ersten Fall, legt sie zwei Stücke in den Pot, wobei sich nun von beiden Spieler jeweils drei Stücke im Pot befinden. Die Möglichkeit der Spieler Aktionen auszuführen, ist nun ausgeschöpft, da alle zwei call -Kanten zu Endknoten führen. Dort gewinnt Spieler A den Pot (6 Stücke gesamt, davon 3 Gewinn), wenn er eine Gewinnerhand hat (Endknoten der linken call -Kante) und verliert dementsprechend viele bei einer Verliererhand, was einer Auszahlung von -3 entspricht.

2.3 Informationsmengen

Unser vorheriges Beispiel ist durch Abbildung 1 noch nicht ganz modelliert. Wir erinnern uns, dass jeder Spieler die Regeln des Spiels und damit auch den Baum der Extensivform kennt (siehe Abschnitt 2.1). Aus unserem Baum ist jedoch nicht abzulesen, dass Spielerin B bis zum Erreichen der call -Endknoten nicht weiß, welche Karte Spieler A auf der Hand hält. Die Spielregeln schreiben jedoch vor, dass nur Spieler A seine Karte kennt. Dies führt uns zur Definition der Informationsmengen. Alle Knoten, an denen Spieler entscheiden müssen (keine Anfangs-, End-, Naturknoten), werden in disjunkte Informationsmengen zerlegt. Befindet sich ein Spieler an einem Knoten, so weiß er zwar, dass er an der Reihe ist, kann aber nicht unterscheiden, ob er sich an diesem Knoten oder einem anderen in derselben Informationsmenge befindet. Um dies zu garantieren, müssen verschiedene Bedingungen erfüllt sein:

•Alle Knoten in der Informationsmenge gehören einem Spieler, damit er weiß, dass er an der Reihe ist.

•Von jedem Knoten aus der Informationsmenge müssen gleichviel Kanten mit der gleichen Beschriftung ausgehen, sonst wäre für den Spieler eine Unterscheidung der Knoten anhand der Züge, die zur Auswahl stehen, möglich.

Definition 2.3.1: Eine Informationsmengeeines Spielersenthält Knoten, an denen er einen Zug ausführen kann, jedoch nicht weiß, an welchem Knoten in der Informationsmenge er sich befindet.

Istdie Menge aller Knoten K ohne die Wurzel, Endknoten und Knoten, an denen die Natur zieht, unddie j-te Informationsmenge des Spielers i, von denen erStück hat, so ist die disjunkte Vereinigung aller Informationsmengen aller Spieler.

Betrachten wir nun Basic Endgame Poker in Abbildung 2 mit eingezeichneten Informationsmengen:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Basic Engame Poker mit eingezeichneten Informationsmengen

Knoten in derselben Informationsmenge befinden sich hier auch in demselben gestrichelten Kringel. Wie zu erwarten sind um die Wurzel und die sechs Endknoten keine Kringel, also gibt es hierfür auch keine Informationsmengen. Interessant ist nun die zweite Ebene im Baum: Hier ist Spieler A an der Reihe, nachdem er seine Gewinner- oder Verliererkarte ausgeteilt bekam. Jeder seiner zwei Endknoten befindet sich dabei in einer eigenen Informationsmenge, d.h. er weiß, ob er sich im rechten oder linken Teil des Graphen befindet, also ob er eine Gewinner- oder Verliererkarte hat. Anders verhält es sich bei dem darauffolgenden Zug von Spielerin B. Ihre beiden Knoten befinden sich in derselben Informationsmenge. Sie kann also nicht unterscheiden, was für eine Karte Spieler A auf der Hand hält. Dies ist dadurch möglich, dass ihr bei beiden Knoten die zwei Aktionen call und fold zur Auswahl stehen. In der nächsten Ebene befinden sich nur Endknoten, woraus Spielerin B die Karte von A anhand seiner Auszahlung schließen kann - jedoch zu spät.

In einer Baumstruktur zieht ein Spieler nach dem anderen, jedoch gibt es auch Spiele mit gleichzeitigen Zügen, d.h. zwei oder mehrere Spieler wählen ihre Aktionen unabhängig voneinander. Dies lässt sich jedoch leicht mit Hilfe von Informationsmengen darstellen. Das gleichzeitige Ziehen entspricht dabei dem sequenziellen Ziehen, wobei jedoch der zweite Spieler nicht weiß, welche Aktion der erste gewählt hat. Ist das Spiel also an einer Position angelangt, an der beide Spieler gleichzeitig ziehen müssen, so zieht erst Spieler I, d.h. er wählt von seinem Knoten eine Kante aus. An allen Nachfolgerknoten ist nun Spieler II an der Reihe. Zu diesem Zeitpunkt hat er keine Information über den Zug seines Mitspielers, wenn man alle diese Nachfolgerknoten in eine Informationsmenge aufnimmt. Dies ermöglicht es nun Spieler II zu ziehen, womit der gleichzeitige Zug in zwei aufgelöst wurde. Wie man simultane Züge nicht nur formal sondern mit Hilfe der Spielregeln auflöst, sieht man am Beispiel des Blinden-Stein-Schere-Papiers (siehe Abschnitt 2.5).

Es gibt Möglichkeiten die Qualität von Information mathematisch zu erfassen, auf die wir hier aber nicht weiter eingehen werden. Es ist sogar möglich, dass jemand mit mehr Informationen einen Nachteil hat. Stellen Sie sich zwei Geschäftsleute, Arnold und Bettina, vor, die die Entscheidung eines Kunden über einen großen Auftrag erwarten. Der Kunde wird sich entweder für Arnold oder Bettina entscheiden, die zudem beide risikoscheu sind. Da auch noch deren beiden Existenzen bedroht sind - sie sind pleite - beschließen sie, dass derjenige, der den Auftrag erhält, sich den Gewinn mit seinem Kollegen teilt. Bietet nun ein Insider des Kunden an, schon vor der Entscheidung dessen zu verkünden, wer den Auftrag erhält, so würde dies verhindern, dass eine Übereinkunft zwischen Arnold und Bettina zustande kommt, da für denjenigen, der den Auftrag voraussichtlich bekommt, das Teilen des Gewinns nicht mehr wirtschaftlich erscheint. Im Durchschnitt erhält jeder einen gleich großen Gewinn, nämlich die Hälfte des eigentlichen Gewinns durch den Großauftrag, wenn wir davon ausgehen, dass beide eine gleichgroße Chance haben, diesen zu erhalten. Da ein so großer Auftrag aber nur einmal zu erwarten ist, macht dies einen Unterschied aus. Einer von beiden wird leer ausgehen, womit seine Zukunft ruiniert ist, was durch eine Übereinkunft zu verhindern gewesen wäre. Hier hat also die zusätzliche Information des Insiders eine schlechtere Situation hervorgerufen. Dieses Beispiel zeigt auch, warum es sinnvoller ist, Nutzen und nicht Geld als Auszahlung zu betrachten, da der individuelle Nutzen eben von Spieler zu Spieler variiert. Beide haben einen größeren Nutzen davon, wenn sie sicher die Hälfte des Gewinns anstatt mit fünfzigprozentiger Wahrscheinlichkeit den vollen Gewinn erhalten. Der durchschnittliche Gewinn ist dabei aber in beiden Fällen gleich.

2.4 Allgemeinwissen

Eine besondere Art der Information stellt das Allgemeinwissen ^[2] dar. Ist eine Information Allgemeinwissen, so ist sie nicht nur allen Spieler bekannt, sondern jeder Spieler weiß auch, dass alle Spieler sie wissen und dass alle Spieler wissen, dass alle Spieler die Information wissen, etc. Diese Rekursion lässt sich unendlich fortführen, wird uns aber noch bei Dominanz nützlich sein. Die Regeln des Spiels sind immer Allgemeinwissen, also auch die Informationsmengen. Sonst würde Spieler A in Basic Endgame Poker nicht wissen, dass Spielerin B seine Karte nicht kennt.

2.5 Informationskategorien

Es ist nicht immer nötig, die Informationsstruktur eines Spiels in Informationsmengen zu zerlegen. Stattdessen ist es auch schon hilfreich die Art der Information, die sogenannten Informationskategorien, zu definieren:

Abbildung in dieser Leseprobe nicht enthalten^[3]

Tabelle 1: Informationskategorien (vgl. Rasmusen 2007, S. 49 - 52)

Aus den Definitionen lassen sich einige Folgerungen ziehen:

Asymmetrische oder unvollständige Information ist zugleich auch imperfekt. Dies gilt nicht für unsichere Information, da ein Zug der Natur von jedem Spieler beobachtet werden kann, auch wenn es sich wie bei unsicherer Information nicht um einen Initialzug handelt.

Ein schöne Verdeutlichung stellt ein Spiel dar, dass ich Blinden-Stein-Schere-Papier taufen möchte. Der erste Spieler wählt zuerst aus, ob er Stein, Schere oder Papier nehmen möchte (wie bei dem Original), während die andere Spielerin die Augen geschlossen hat. Danach macht die zweite Spielerin ihre Wahl, ohne die Augen zu öffnen und damit die Hand des ersten Spielers zu sehen. Ein Schiedsrichter entscheidet nun nach den gewohnten Regeln, wer gewonnen hat. Dieses Spiel gleicht dem Original, jedoch wurde hier der gleichzeitige Zug in zwei sequenzielle aufgelöst. Der Schiedsrichter ist nur für die Praxis nötig, damit der erste Spieler nicht betrügt. Nun ist die Information im Original symmetrisch, da keiner weiß, was der andere wählen wird und die Bekanntgabe gleichzeitig ist. Damit muss aber auch die Information im Blinden-Stein-Schere-Papier symmetrisch sein. Verfolgen wir das Spielgeschehen schrittweise:

Der erste Spieler (Arnold) hat keinerlei Information zu Beginn, da er den Initialzug tätigt. Danach erlangt er jedoch Information, denn er kennt nun seinen eigenen Zug, den er gerade getätigt hat. Er weiß genau, wo er sich im Spielbaum befindet, dies gibt ihm aber keine relevante Information, da er nicht an der Reihe ist und damit sie nicht verwerten kann. Dies stellt also keinen Widerspruch zur Symmetrie dar. Nun ist die zweite Spielerin (Bettina) an der Reihe. Sie hat zu diesem Zeitpunkt weniger Informationen also Arnold, da sie seinen Zug nicht beobachten konnte, jedoch hat sie genauso viele Informationen wie Arnold bei seinem Initialzug hatte und damit keinerlei Nachteil beim Auswählen ihrer Aktion. Auch an den Endknoten haben beide die gleichen Informationen, da sie dort den Zug des anderen erfahren. Damit sind die Erfordernisse für symmetrische Information gegeben.

Asymmetrisch wird das Spiel, wenn nach dem Zug von Bettina Arnold zwei Möglichkeiten hätte. Entweder er beendet das Spiel (es werden die Aktionen verglichen und entschieden, wer gewonnen hat) oder stellt Bettina vor die Wahl "Doppelt oder Nichts" (vgl. Basic Endgame Poker in Abschnitt 2.2). Da er zu dieser Zeit die Wahl von Bettina kennt, diese aber seine in der Situation "Doppelt oder Nichts" immer noch nicht weiß (ihre Augen sind bis zum Spielende verschlossen), wird die Information des Spiels asymmetrisch.

3 Matrixspiele

Nach den vielen Definitionen von Spielen im Allgemeinen möchten wir nun konkreter werden und beschränken uns nur auf einen besonderen Typ von Spiel:

Definition 3.0.1: Ein endliches Nullsummenspiel mit zwei Spielern in Normalform wird als Matrixspiel bezeichnet.

Klären wir zuerst einmal die Begrifflichkeiten. Endlich heißt, dass das Spiel ein Ende hat und somit irgendwann terminiert. Wir beschäftigen uns im Weiteren nur mit solchen Spielen.

Definition 3.0.2: Ein Spiel ist ein Nullsummenspiel, wenn die Summe der Auszahlungen über alle Spieler für jedes beliebige Strategieprofil Null ergibt, also für jedes Strategieprofil gilt.

Der Volksmund würde ein Nullsummenspiel mit dem Satz "Des einen Freud ist des andren Leid." charakterisieren.

Der Name Matrixspiel lässt schon vermuten, dass ein solches Spiel in Normalform als Matrix dargestellt werden kann. Definieren wir nun also diese Art der Darstellung.

3.1 Normalform

Entgegen der allgemein verwendbaren Extensivform, kommt die Normalform nur bei Matrixspielen (also Nullsummenspielen mit zwei Spielern) zum Einsatz, da man schon bei drei Spielern das Spiel nicht mehr als Matrix darstellen kann. Im Weiteren seien unsere Spieler immer Arnold (Spieler A) und Bettina ^[4] (Spielerin B).

Definition 3.1.1: Ein Zwei-Personen-Nullsummenspiel in Normalform ist ein geordneter Tripel mit •die nicht-leere, endliche Menge von Arnolds Strategien mit der Mächtigkeit, •die nicht-leere, endliche Menge von Bettinas Strategien mit der Mächtigkeit und •eine Funktion, die jedem StrategieprofilArnolds Auszahlungzuordnet.

Bemerkung: Die Funktionlegt hier bereits das Ergebnis fest, obwohl sie nur Arnolds Auszahlung liefert. Diese Vereinfachung wurde vorgenommen, da aufgrund der Nullsummeneigenschaft Bettinas Auszahlungist. Das Ergebnis eines Strategieprofilsist damit .

Um nun das Spiel vernünftig als Matrix darstellen zu können, nummerieren wir alle Strategien der beiden Spieler. Dies entspricht formal einer Zerlegung der Strategiemengen in einelementige, disjunkte Mengen:

Abbildung in dieser Leseprobe nicht enthalten

Nun können wir die Funktionals Matrix^[5] darstellen:

Abbildung in dieser Leseprobe nicht enthalten

Mit dem Strategieprofilsei im Weiterengemeint.

Arnolds Auszahlung, wenn er seine i-te Strategie und Bettina ihre j-te Strategie wählt, kann man in der i-ten Zeile und j-ten Spalte der Matrix ablesen. Damit geben wir aber die Wohldefiniertheit unserer obigen Definition auf, da das gleiche Spiel - je nachdem wie man die Strategien nummeriert -­ durch verschiedene Matrizen darstellbar ist. Dies kann jedoch durch geeignete Spalten- und Zeilenvertauschungen behoben werden. Auch empfiehlt sich zwar zum Rechnen eine Nummerierung der Strategien, bei der Darstellung als Matrix werden die Strategien jedoch häufig mit Namen versehen.

Der Spielablauf gestaltet sich nun dergestalt, dass jeder Spieler unabhängig von seinem Mitspieler eine Strategie wählt und dann das Ergebnis gemäß der Matrix bestimmt wird. Aufgrund dessen nennt man Spieler A auch Zeilenspieler und Spielerin B Spaltenspieler, da jeder durch die Wahl seiner Strategie die Zeile bzw. Spalte festlegt, in der sich das Ergebnis befindet.

3.2 Nash-Gleichgewicht

Verdeutlichen wir dies nun an dem Beispiel "Erkundung von Aalen".

Arnold und Bettina möchten ihren Nachmittag in der ihnen unbekannten Stadt Aalen verbringen. Da sie sich nicht einigen können, was für Sehenswürdigkeiten sie bestaunen möchten, schlägt Bettina vor: "Wir haben vier Orte in Aalen zur Auswahl und können von dort aus in alle vier Himmelsrichtungen loslaufen. Warum wählst du nicht den Startort aus und ich entscheide, ohne den Ort zu wissen, in welche Richtung wir gehen?"

Arnold stimmt zu, jedoch haben beide verschiedene Interessen. Er möchte lieber seinen Spaß haben und Bettina würde gerne etwas Kultur aus Aalen mitnehmen. Jeder der Wege, die jeweils aus Ort und Richtung bestehen, bietet nun von einem mehr und vom anderen weniger an. Als Nutzen führen wir den "Spaßfaktor" ein. Je höher er ist, desto mehr Spaß und desto weniger Kultur^[6] birgt der ausgewählte Weg. Als Orte stehenund als Himmelsrichtungen zur Auswahl. Da beide unabhängig voneinander Entscheidungen treffen und jeder auch nur eine fällt, sind die Aktionen der Spieler sogleich alle Strategien, die ihnen zur Auswahl stehen. Wir erhalten also eine-Matrix, deren Einträge den jeweiligen Spaßfaktor des Weges angeben:

Dieses Spiel macht nur Sinn, wenn wir davon ausgehen, dass die Spieler rational handeln (davon gehen wir immer aus) und in diesem Fall auch Nebenübereinkünfte außerhalb der Spielregeln à la "Ich spendiere dir ein Eis, wenn du das alte Rathaus als Startpunkt wählst." verboten sind. Diese sogenannten kooperativen Spiele bieten noch Spielraum zur Analyse, sind hier jedoch nur hinderlich.

Arnold möchte einen möglichst hohen Spaßfaktor erreichen, wohingegen Bettina versuchen wird, diesen Wert möglichst gering zu halten, da dies für sie weniger Kultur bedeutet. Immerhin variiert der Spaßfaktor von 1 bis 7, jedoch möchte keiner von beiden das jeweils für ihn schlechte Extrem erreichen. Man kann sich nun überlegen, dass sich beide Spieler die Frage stellen werden, ob es nicht möglich ist, durch ihre Entscheidung für sich ein gewisses Maß an Spaß bzw. Kultur zu garantieren, unabhängig davon, was der andere wählt. Wählt Arnold beispielsweise den Startort B aus, so weiß er, dass der Spaßfaktor, den er ja maximieren möchte, bestenfalls 5 (Bettina wählt Westen) und schlechtestenfalls 2 (Bettina wählt Osten) beträgt. 2 ist also bei der Aktion "Ort B" sein garantierter Spaßfaktor, egal für welche Richtung sich Bettina entscheidet. Diese Überlegung kann er nun für jede seiner Strategien fortführen und erhält damit folgende Tabelle:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2: Minimaler Spaßfaktor von Arnold

Für Arnold ist nun die Entscheidung klar. Er wählt den Startpunkt C, da ihm ein Spaßfaktor von mindestens 3 dort garantiert ist, egal in welche Richtung Bettina gehen möchte. Dies ist sein größter garantierter Spaßfaktor, wie man leicht aus der Tabelle entnehmen kann. Man beachte, dass es sich bei diesem Vorgehen nur um eine von vielen Möglichkeit handelt, für sich eine geeignete Strategie zu finden. Am Ort C hat er zum Beispiel keine Chance den maximalen Spaßfaktor von 7 zu erreichen, den er nur an Ort A erreichen kann. Jedoch sieht man mit einem Blick auf die erste Zeile, dass dort auch die "Gefahr" größer ist, dass Bettina eine Richtung wählt, die zu dem sehr kleinen Spaßfaktor 1 führt. Die Wahl des Ortes C, also des größten garantierten Spaßfaktors, ist damit eine risikofreie Entscheidung.

Die gleichen Überlegungen macht nun auch Bettina. Wir erinnern uns, dass sie möglichst viel Kultur erleben möchte, also versucht den Spaßfaktor zu minimieren. Beim Betrachten der Matrix sucht sie nun für jede ihrer Strategien, also in jeder Spalte, den größten Wert heraus, also den für sie schlechtesten Fall:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3: Maximaler Spaßfaktor von Bettina

Analog zu Arnold, überlegt sie sich nun, dass sie diejenige Strategie wählt, bei der der maximale Spaßfaktor, also der schlimmste Fall, der eintreten kann, am geringsten ist. Damit ist sie auf einer recht sicheren Seite. Sie wählt also die Himmelsrichtung Osten.

Es überrascht vielleicht nun den unerfahrenen Leser, dass das von beiden gewählte Strategieprofil (Ort C und Richtung Osten) genau zu dem Spaßfaktor führt, der beiden garantiert war, nämlich 3. Sie haben sich also ohne Absprache auf eine Art Kompromiss geeinigt.

Dieses Strategieprofil bezeichnen wir als Sattelpunkt oder Nash-Gleichgewicht.

Definition 3.2.1: In Matrixspielen wird ein Strategieprofil Nash-Gleichgewicht oder Sattelpunkt genannt, wenn der Eintragdas Minimum in der Reiheund das Maximum in der Spalteist.

Bemerkung: Gelegentlich wird auch der Eintragals Sattelpunkt bezeichnet.

Ein Sattelpunkt ist also ein Strategieprofil, bei dem keiner der beiden Spieler einen Vorteil davon hat, als einziger seine Strategie zu wechseln. Ist dies sogar nachteilig für den wechselnden Spieler, so nennt man den Sattelpunkt stabil.

Um nun nachzuvollziehen, ob mit dieser Definition dasselbe Gleichgewicht wie das von Arnold und Bettina gemeint ist, schauen wir uns erst einmal an, wie die beiden vorgegangen sind:

Arnold bestimmt erst für alle Zeilen jeweils das Minimum aller Einträge und über diese Minima dann das Maximum

Abbildung in dieser Leseprobe nicht enthalten

Bettina geht aus ihrer Sichtweise analog vor. Sie schaut erst bei allen Spalten nach den jeweiligen Maxima aller dort befindlichen Einträge und wählt aus diesen Maxima dann das kleinste aus, nämlich

Abbildung in dieser Leseprobe nicht enthalten

Weiter oben haben wir nun behauptet, dass es sich bei den von Arnold und Bettina berechneten Einträgen um einen Sattelpunkt handelt, sobald diese gleich sind. In unserem Beispiel können wir dies schnell an der Matrix überprüfen, jedoch bedarf diese Behauptung für den allgemeinen Fall eines Beweises. Wir können uns aber schon einmal klarmachen, dass die garantierten Werte beider Spieler nicht immer gleich sein müssen:

Abbildung in dieser Leseprobe nicht enthalten

Satz 3.2.2: Ein Sattelpunktin einer Matrixexistiert genau dann, wenn

Abbildung in dieser Leseprobe nicht enthalten

Zum Beweis des Satzes benötigen wir ein Lemma:

Abbildung in dieser Leseprobe nicht enthalten

Beweis des Lemmas:

Wir haben die Matrixeinträge

und

gegeben, wobei die Indizeskeinesfalls eindeutig sein müssen. Es reicht, irgendwelche Indizes zu betrachten, die auf den entsprechenden Eintrag verweisen.

Dadurch, dassper Definition das Minimum in der Zeileist, gilt

(I).

Bezeichnen wir nun mit

das jeweilige Maximum in der j-ten Spalte. Für dieses gilt dann per Definition

(II).

Nun machen wir uns nun alle Tatsachen zu nutze, um das Lemma zu beweisen:

Beweis des Satzes (vgl. Schalk 2007, S. 32f.):

Beweisen wir zuerst die Rückrichtung:

Es gibt also Indizesund, so dass

Daraus folgt aber auch im Speziellen

und

Damit istnach Definition 3.2.1 ein Sattelpunkt, da er der kleinste Eintrag in seiner Zeile und der größte Eintrag in seiner Spalte ist.

Nun der Hinweg:

Aus der Definition eines Sattelpunktserhalten wir:

Da der Eintragminimal in seiner Zeile ist, so ist er höchstens so groß wie das Maximum über alle Minima in jeder Zeile, also

und mit gleicher Begründung

Als eine Ungleichung geschrieben, erhält man

Durch das Lemma 3.2.3 wissen wir aber, dass nur die Gleichheit gelten kann:

Korollar 3.2.4: Existieren mehrere Sattelpunkte, so sind deren Einträge gleich.

Dies folgt direkt aus Satz 3.2.2.

3.3 Reine und gemischte Strategien

Um im Weiteren eine detaillierte Analyse zu ermöglichen, führen wir den Begriff einer gemischten Strategie ein. Reine Strategien sind dabei die uns bereits bekannten Strategien, also eine Reihe von Aktionen, die ein Spieler zu einem gegebenen Zeitpunkt unter gewissen Umständen (in Abhängigkeit der Position im Spiel und Information) ausführt. Hat sich ein Spieler für eine reine Strategie entschieden, so spielt er diese immer auf die gleiche Weise - wie nach einem vorgefertigten Plan. Eine gemischte Strategie dagegen besteht aus mehreren Strategien, die mit gewissen Wahrscheinlichkeiten gespielt werden. So besteht eine gemischte Strategie p von Arnold in "Erkundung von Aalen" darin, dass er z. B. mit einer Wahrscheinlichkeit von 20% Ort A, 10% Ort B, 30% Ort C und 40% Ort D wählt. Man schreibt dies nun kürzer als Tupel, wobei jeder reinen Strategie eine Wahrscheinlichkeit zwischen 0 und 1 zugeordnet wird. Die Wahrscheinlichkeiten über alle reinen Strategien müssen sich dabei natürlich zu 1 summieren.

Definition 3.3.1: Für eine geordnete, endliche Mengereiner Strategien mitist der m-Tupelmiteine gemischte Strategie. Hierbei wird die reine Strategiemit der Wahrscheinlichkeitgespielt.

Definition 3.3.2: sei die Menge aller gemischten Strategien bei k reinen Strategien.

Bemerkung: Da es unendlich viele reelle Zahlen im Intervallgibt, existieren fürimmer auch unendlich viele gemischte Strategien.

Eine reine Strategiekann dabei immer als gemischte Strategie mit

aufgefasst werden. Deshalb reicht es zur Analyse aus, im Weiteren immer nur gemischte Strategien zu betrachten.

Wie berechnet man nun die Auszahlung, wenn mindestens ein Spieler eine gemischte Strategie spielt?

Benutzt Spieler A die gemischte Strategieund B die reine Strategie, d.h. sie spielt die j-te Spalte, so ist die durchschnittliche Auszahlung von Spieler A

Ähnliches gilt, wenn Spieler A die reine Strategieund Spielerin B die gemischte Strategie spielt. Die (durchschnittliche) Auszahlung beträgt dann

Spielen nun beide die gemischten Strategienbzw., so erhält man zusammen mit der Martizenmultiplikation^[7] die (durchschnittliche) Auszahlung von Spieler A:

^[8]

3.4 Der Wert und optimale Strategien

Wir möchten nun herausfinden, ob und wie ein Spiel unfair ist, also in welcher Weise es einem Spieler möglich ist, für sich immer einen gewissen Gewinn zu garantieren.

Definition 3.4.1: wird Wert eines Matrixspiels genannt, wenn

a) Spieler A für sich eine (durchschnittliche) Auszahlung vongarantieren kann, unabhängig davon, welche (gemischte)^[9] Strategie B spielt, und wenn

b) Spielerin B für sich eine (durchschnittliche) Auszahlung vongarantieren kann, unabhängig davon, welche (gemischte) Strategie A spielt.

Für, so sagt man, dass das Spiel fair ist. Istpositiv, so bevorzugt das Spiel Spieler A, istdagegen negativ, so bevorzugt es Spielerin B. Man bezeichnet den Wert eines Matrixspiels A auch mit.

Bemerkung: Garantieren heißt hier, dass bei geeigneter Wahl einer (gemischten) Strategie die (durchschnittliche) Auszahlung für den Spieler immer mindestensbzw.beträgt.

Dem aufmerksamen Leser wird diese Definition an Nash-Gleichgewichte erinnern. In der Tat:

Korollar 3.4.2: Existiert ein Sattelpunkt, so istder Wert des Matrixspiels A.

Dies wurde bereits mit Satz 3.2.2 bewiesen, da durch Definition 3.2.1der minimale Gewinn von Spieler A ist, wenn er die reine Strategiespielt undder minimale Gewinn von Spielerin B ist, wenn sie ihre reine Strategiewählt.

Jedoch haben wir gesehen, dass für reine Strategien nicht immer Sattelpunkte existieren müssen (vgl. Matrixin Abschnitt 3.2). Schauen wir uns also eine allgemeinere Definition an, die die bekannte Definition 3.2.1 impliziert.

Definition 3.4.3: Ein Strategieprofilbestehend aus den gemischten Strategienvon Spieler A undvon Spielerin B ist ein Nash-Gleichgewicht des Matrixspiels, wenn

a) für alle gemischten Strategienvon Spieler A

und

b) für alle gemischten Strategienvon Spielerin B

gilt.

bzw.nennt man dann jeweils eine optimale Strategie von Spieler A bzw. B.

Jeder Spieler kann also durch die Wahl einer anderen gemischten Strategie seine Auszahlung nicht verbessern, wenn der andere Spieler gleichzeitig bei seiner optimalen Strategie bleibt.

Satz 3.4.4: Istein Nash-Gleichgewicht aus gemischten Strategienund, so ist der Wert des Matrixspiels.

Durch Definition 3.4.3 b) erhalten wir

, was gleichbedeutend damit ist, dass die durchschnittliche Auszahlungvon Spieler A bei der Wahl der gemischten Strategiemindestensbeträgt, egal was für eine gemischte StrategieSpielerin B wählt. Dies entspricht der Bedingung a) aus Definition 3.4.1 des Wertes.

Aus Definition 3.4.3 a) erhält man

Die durchschnittliche Auszahlungvon Spielerin B ist für jede beliebige gemischte Strategiemindestens. Damit ist auch Definition 3.4.1 b) erfüllt. □

Satz 3.4.5: Sindundzwei Nash-Gleichgewichte aus gemischten Strategien, so sind die jeweiligen Auszahlungengleich.

Wir verwenden hier die Tatsache, dass sich die Auszahlung eines Spielers nicht verbessern kann, wenn er von seiner optimalen Strategie abweicht, während der andere Spieler bei seiner optimalen Strategie bleibt (Definition 3.4.3).

Im ersten Schritt wechselt A seine Strategie vom ersten Nash-Gleichgewicht weg. Dadurch wird seine Auszahlung nie besser. Daraufhin wechselt B zur zweiten optimalen Strategie. Dadurch wird Bs Auszahlung nicht schlechter, also As nicht besser. Durch analoges Wechseln der optimalen Strategien gelangt man wieder zum ersten Gleichgewicht (vgl. Schalk 2007, S. 46f.).

Da auf beiden Seiten der Ungleichung dasselbe steht, muss überall die Gleichheit gelten. □

Bemerkung: Erst dieser Satz lässt uns von dem Wert eines Spiels sprechen.

Wir möchten nun noch ein paar Sätze beweisen, die für die Praxis sehr hilfreich sind.

Satz 3.4.6: ist genau dann ein Nash-Gleichgewicht aus gemischten Strategien eines Matrixspiels A, wenn

und

,

wobeider i-te kanonische Basisvektor desbzw.ist.

Die Hinrichtung ist nur ein Spezialfall der Definition 3.4.3.

Wir beweisen nun die Rückrichtung in bezug auf Spieler A. Für Spielerin B geht man analog vor.

Sei nuneine beliebige gemischte Strategie, so ist

Dabeliebig war, entspricht die obere Ungleichung der Definition 3.4.3 eines Nash-Gleichgewichts. □

Damit lässt sich nun ganz einfach überprüfen, ob eine gemischte Strategie ein Nash-Gleichgewicht ist.

Satz 3.4.7: SindundNash-Gleichgewichte, so ist für beliebigesauchein Nash-Gleichgewicht.

Seieine beliebige gemischte Strategie von Spieler A, so gilt

Hierbei ergibt sich die Ungleichung aus dem mehrfachen Anwenden der Definition 3.4.3 a) auf die Nash-Gleichgewichteund.

Sei nuneine beliebige gemischte Strategie von Spielerin B, so gilt

Hierbei ergibt sich die Ungleichung aus dem mehrfachen Anwenden der Definition 3.4.3 b) auf die Nash-Gleichgewichteund.

Beide Ungleichungen definierenals Nash-Gleichgewicht. □

Existieren also mehrere optimale Strategien für einen Spieler, so können diese in beliebiger Weise kombiniert werden.

3.5 Dominierte Strategien

Unser großes Ziel ist es, für jedes Matrixspiel den Wert zu bestimmen und zusätzlich für jeden Spieler eine optimale Strategie zu finden. Hat das Spiel einen Sattelpunkt, den wir auch bei großen Matrizen leicht mit dem Algorithmus aus "Erkundung von Aalen" finden können, so ist das Spiel lösbar, d.h. wir können die optimalen Strategien und den Wert berechnen. Jedoch muss ein Sattelpunkt nicht immer existieren, wie wir schon gesehen haben (vgl. Matrixin Abschnitt 3.2). Auch für Matrizen der Formundexistieren einfache Verfahren zur Berechnung (Satz 3.6.2 beschreibt, wie man-Matrizen löst, sonst vgl. Ferguson 2007, S. II-9). Liegen diese Typen nicht vor, so kann uns zwar die Lineare Optimierung unter die Arme greifen, jedoch ist es oft auch möglich, die Matrix auf eine der "lösbaren" Formen zu bringen. Schauen wir uns dazu folgendes Beispiel an:

In der Matrix existieren keine Sattelpunkte. Wählen beide Spieler nur reine Strategien, so würde Spielerin B (Spaltenspieler) jedoch nie ihre dritte Strategie spielen, denn sie erreicht durch Wahl der ersten Strategie immer ein besseres Ergebnis. Dies ist daran zu erkennen, dass die Einträge in jeder Zeile aus der 1. Spalte echt kleiner sind, als die der 3. Spalte:

, und Man sagt, die 1. Strategie dominiert streng die 3. Strategie. Da es unvernünftig ist, sie zu spielen, und wir gehen immer von vernünftigen Spielern aus, kann man sich überlegen, diese Strategie zu streichen. Man erhält damit eine vereinfachte Matrix

Spielerin B bietet uns keine weiteren Strategien an, die sich dominieren. Wählt Spieler A jedoch seine zweite Strategie, so erhält er mindestens dieselbe Auszahlung wie durch Wahl der dritten Strategie. Da seine Auszahlung beim Spielen der dominierenden Strategie nicht immer besser ist, sondern diese auch gleich sein kann (B wählt ihre erste Strategie), spricht man hier nicht mehr von strenger Dominanz, sondern nur noch von Dominanz. Auch hier streichen wir die dominierte Strategie und übrig bleibt

.

Diese-Matrix lässt sich einfach lösen (Satz 3.6.2). Der gute Menschenverstand kommt hier zu demselben Ergebnis: Für jeden Spieler stellteine optimale Strategie dar. Auf unsere ursprüngliche Matrixbezogen, ist damiteine optimale Strategie für jeweils beide Spieler. Folglich ist der Wert der MatrixNull, weshalb das Spiel fair ist.

Definition 3.5.1: Eine reine Strategievon Spieler A dominiert seine Strategie, wenn

.

Eine Strategievon Spielerin B dominiert ihre reine Strategie, wenn .

In beiden Fällen spricht man von strenger Dominanz, wenn die Gleichheit nicht gilt.

Die Rechtfertigung für das Streichen der dominierten Strategien liefern die Sätze 4.4.2 und 4.4.3.

Bei dem nächsten Beispiel (vgl. Schalk 2007, S. 49)

existieren für beide Spieler keine Dominanzen. Jedoch gilt

und

Die gemischte Strategievon Spieler A dominiert seine reine Strategie. Es macht für ihn also immer Sinn die gemischte Strategie anstatt der reinen zu wählen. Dies motiviert die folgende Definition:

Definition 3.5.2: Die gemischte Strategievon Spieler A dominiert seine reine Strategie, wenn

Die gemischte Strategievon Spielerin B dominiert ihre reine Strategie, wenn

In beiden Fällen spricht man von strenger (gemischter) Dominanz, wenn die Gleichheit nicht gilt.

Es ergibt selbstverständlich nur Sinn, eine solche dominierte reine Strategie zu entfernen, wenn sie keinen Anteil an der gemischten dominierenden Strategie hat. Bei Spieler A z. B. muss alsosein, um die Strategiezu entfernen.

Wie erkenne ich nun aber, ob eine reine Strategie von einer gemischten dominiert wird? Nehmen wir uns wieder die Beispielmatrixvor. Spielerin B hat zu wenig Strategien, damit eine gemischte Dominanz möglich wäre. Für Spieler A überlegen wir uns (ungeachtet des bereits bekannten Ergebnisses), ob die erste Strategie von den beiden anderen dominiert wird. Wir müssten also ein mit

finden. Da aber für beliebigeimmerzwischen a und b liegt, gibt es für beide Gleichungen keine Lösung. Auf dasselbe Problem stoßen wir, wenn wir annehmen, dass die zweite Strategie dominiert wird. Als letztes müssen wir also eine Lösung für

finden. Diese Gleichungen sind für alleerfüllt, d.h. jede gemischte Strategievon Spieler A mit dem gerade bestimmtendominiert seine reine Strategie.

3.6 Lösen aller 2x2-Matrizen

Lösen bedeutet hier das Berechnen des Wertes und das Finden von mindestens einer optimalen Strategie für jeden Spieler. ^[10] Sei die Matrix

gegeben, so können wir sie leicht mit unseren bisherigen Kenntnissen auf einen Sattelpunkt prüfen. Existiert dieser, so sind wir bereits in der Lage die Matrix zu lösen. Wir nehmen also an, dass es keinen Sattelpunkt gibt und versuchen herauszufinden, ob ein Wert und optimale Strategien existieren:

Ist, so muss, da sonstein Sattelpunkt wäre. Dann muss jedoch auch, da sonst ebenfallszum Sattelpunkt wird. Verfahren wir mit dieser Technik weiter, so erhalten wir zusätzlich(sonstSattelpunkt) und(sonstSattelpunkt). Schauen wir uns den zweiten Fallan, so erhalten wir mit gleicher Begründung,und.

Lemma 3.6.1: Existiert für die Matrix A kein Sattelpunkt, so gilt entweder

1. ,,und ODER

2. ,,und.

Da kein Sattelpunkt existiert, muss ein Nash-Gleichgewicht aus gemischten Strategien bestehen (Satz 4.3.2). Wählt Spieler A die erste Zeile mit Wahrscheinlichkeitund Spielerin B die erste Spalte mit Wahrscheinlichkeit, so ist die

Wählt Spielerin B die zweite Spalte (), so ist der durchschnittliche Gewinn von A

Erinnern wir uns an die Definition des Werteseines Spiels, so kann Spieler A immer die Auszahlung V garantieren, egal was Spielerin B für eine Strategie benutzt. Es macht also Sinn, die beiden Auszahlungen oben gleichzusetzen, denn dann erhält Spieler A immer die gleiche Auszahlung unabhängig davon, was für eine Spalte B wählt.

Lösen wir nach p auf, so erhalten wir:

Aus Lemma 3.6.1 wissen wir, dass entwederundbeide positiv oder beide negativ sind. Damit ist, wie gefordert. Schauen wir uns noch einmal die durchschnittliche Auszahlung von Spieler A an:

Stellen wir nun die gleichen Überlegungen für Spielerin B an. Ihr durchschnittlicher Gewinn, wenn Spieler A die erste Zeile ()wählt, ist

,

bei der zweiten Zeile () ist er

Gleichsetzen

und das Auflösen nachergibt

Berechnen wir auch hier wieder den durchschnittlichen Gewinn von Spielerin B

,

so bemerken wir, dassder Wert des Spiels ist. Damit sind die gemischten Strategien von Spieler A undvon Spielerin B jeweils optimale Strategien.

Satz 3.6.2: Existiert im Matrixspielkein Sattelpunkt, so ist

1. der Wert des Spiels,

2. miteine optimale Strategie von Spieler A und

3. miteine optimale Strategie von Spielerin B.

Verdeutlichen wir das an einem Beispiel:

;;;

4 Zwei Personen Nicht-Kooperative Spiele

Da wir uns nun ausreichend mit Matrixspielen beschäftigt haben, möchten wir alle Begriffe ein wenig verallgemeinern. Dazu nehmen wir nicht mehr an, dass sich die Gewinne der beiden Spieler zu Null addieren (Nullsummenspiel), sondern ordnen jedem Spieler seine eigene Auszahlung zu. Zwar kann man alle folgenden Überlegungen auch für mehr als zwei Spieler machen, jedoch bleiben wir bei den übersichtlicheren Spielen.

Definition 4.0.1: Ein zwei Personen Nicht-Kooperatives Spiel ist ein geordneter Tupel mit

1. die nicht-leere, endliche Menge von Spieler As Strategien der Mächtigkeit,

2. die nicht-leere, endliche Menge von Spielerin Bs Strategien der Mächtigkeit,

3. eine Funktion, die jedem StrategieprofilArnolds Auszahlung zuordnet und

4. eine Funktion, die jedem StrategieprofilBettinas Auszahlung zuordnet.

Die Spieler dürfen dabei keine Auszahlungen untereinander austauschen.

Bemerkung: Ist, so handelt es sich um ein Matrixspiel.

Schauen wir uns zuerst den Begriff "nicht-kooperativ" an. Da der Gewinn des einen Spielers nicht sofort gleich dem Verlust des anderen Spielers ist, gibt es Strategien, bei denen beide Spieler einen Vorteil erlangen können, wenn sie ein anderes Strategieprofil spielen. Nun ist es z. B. möglich, dass sich beide Spieler treffen und vereinbaren, welche Strategien sie spielen werden, damit beide davon einen möglichst großen Gewinn haben. Jedoch stellt sich auch die Frage, wie die Spieler die Gesamtauszahlung untereinander aufteilen sollen. Hat durch einen Wechsel des Strategieprofils z. B. nur ein Spieler einen Vorteil und der andere weder Vor- noch Nachteil, so kann dieser von dem ersten Spieler eine Bezahlung dafür verlangen, dass er ihm durch den Wechsel seiner Strategie eine größere Auszahlung ermöglicht. Falls die Spieler doch zu einem Kompromiss kommen, also z. B. ein Spieler von dem anderen einen Ausgleich in Form von Nutzen für das Wechseln erhält, so muss auch bedacht werden, dass Spieler Übereinkünfte brechen könnnen. Ist der Austausch von Nutzen erlaubt und auch möglich, so spricht man von einem Kooperativen Spiel. Wir werden uns mit der Analyse dieses Typs nicht beschäftigen. Andernfalls spricht man von Nicht-Kooperativen Spielen. Dort kann zwar die Kommunikation vor Wahl der Strategien erlaubt sein, jedoch wird dies ohne Austausch von Nutzen und Verpflichtungen gegenüber dem anderen Spieler keinen Unterschied ausmachen.

4.1 Darstellung als Bimatrix

Das erste Problem, dem wir gegenüberstehen, ist die Darstellung des Spiels. Hierbei gibt es mehrere Möglichkeiten:

In der Extensivform müssen im Gegensatz zu einem Nullsummenspiel die Auszahlungen an den Endknoten durch einen n-Tupel (mit n die Anzahl der Spieler) dargestellt werden. Dabei stellt jedes Element den Gewinn des jeweiligen Spielers dar. Dieses Vorgehen ist dabei nicht nur auf zwei Personen nicht-kooperative Spiele beschränkt.

Möchten wir das Spiel in Normalform darstellen, so ersetzen wir die Matrixeinträge durch Tupel, die wie oben den Gewinn eines jeden Spielers darstellen. Das erste Element steht dabei für den Gewinn des Spielers A und das zweite Element für den Gewinn von Spielerin B. Nummerieren wir nun die Strategien X vonbisund die Strategien Y vonbis, so können wir die Einträge der Matrix

durch

darstellen. Dabei sindundjeweils die i-te und j-te Strategie von Spieler A bzw. B.

Beispiel:

Um jedoch die Auszahlung eines Spielers bei einem bestimmten Strategieprofil zu erhalten, bedarf es zu viel Schreibaufwands, deswegen ist es auch möglich, die Auszahlungen mit Hilfe von zwei Matrizen darzustellen. Matrix A für Spieler A und Matrix B entsprechend für Spielerin B:

Unser vorheriges Beispiel in zwei Matrizen übersetzt:

Da nun der Gewinn des einen Spielers nicht zugleich der Verlust des anderen Spielers ist, ist jeder Spieler verpflichtet, nicht nur auf seine eigenen Strategien zu schauen. Vielmehr muss er auch in Betracht ziehen, was für eine Strategie der andere Spieler wählen wird und danach die Wahl seiner Strategie ausrichten. Dies macht die Analyse solcher Spiele komplexer.

Aufgrund der Darstellung durch zwei Matrizen nennt man zwei Personen nicht-kooperative Spiele auch Bimatrixspiele.

4.2 Safety-Level

Analog zur Definition des Werts bei Matrixspielen ist es interessant zu wissen, welchen Gewinn sich jeder Spieler auf jeden Fall garantieren kann, unabhängig von der Wahl der Strategie des anderen Spielers.

Sei das Spiel durch die zwei Matrizenundgegeben, so möchten wir erst einmal nur reine Strategien betrachten. Da Spieler A Zeilenspieler ist, kann man sich wieder überlegen, was für einen Gewinn er sich auch im schlechtesten Fall garantieren kann. Wählt er eine Zeile aus, so ist sein geringster Gewinn das Minimum in dieser Zeile, da Spielerin B die Spalte wählt. Spieler A wird nun jedoch die Zeile wählen, in der sein geringster Gewinn (das Minimum in dieser Zeile) am größten ist. Spieler A gewinnt bei diesem Vorgehen also mindestens

Für Spielerin B kann man analog vorgehen. Im Gegensatz zu Nullsummenspielen sind dabei die Einträge der Matrixnicht die Verluste sondern die Gewinne von Spielerin B. Sie erhält dabei eine Auszahlung von mindestens

Die Wahl reiner Strategien ist jedoch häufig nicht sinnvoll. Der garantierte Gewinn lässt sich nämlich oft durch die Wahl von gemischten Strategien steigern.

Isteine gemischte Strategie von Spieler A, so ist sein durchschnittlicher Gewinn, wenn Spielerin B die reine Strategiewählt,

Das Minimum über die reinen Strategien von Spielerin B ist dabei der geringste Gewinn, den Spieler A erhalten kann, nämlich

Spieler A versucht nun durch die Wahl einer gemischten Strategieden geringsten Gewinn möglichst groß zu halten:

Dies entspricht genau der Definition 3.4.1 des Wertes der Matrix A als Nullsummenspiel.

Für Spielerin B geht man analog vor. Ihr garantierter Gewinn bei geeigneter Wahl einer gemischten Strategiebeträgt

.

Man beachte, dass hier der Wert der zur Matrix B Transponierten verwendet wurde, da im Nullsummenspiel die Matrixeinträge als Verluste für Spielerin B gewertet werden. So jedoch wird sie in der transponierten Matrix zum Zeilenspieler und damit die Einträge zu Gewinnen.

Satz 4.2.1: In einem durch zwei Matrizenundgegebenen Bimatrixspiel ist

a) der Gewinn, den Spieler A bei geeigneter Wahl einer gemischten Strategie mindestens erhält und

b) der Gewinn, den Spielerin B bei geeigneter Wahl einer gemischten Strategie mindestens erhält.

Diese garantierten Gewinne nennt man Safety Levels^[11].

Beispiel:

Der Wert der Matrix A ist, die optimale Strategie, mit der Spieler A diese Auszahlung erreichen kann, ist. Bei der Matrix B dominiert die erste Spalte die zweite (wir erinnern uns, dass B Spaltenspieler ist und die Einträge der Matrixihre Gewinne sind). Deswegen ist der Wert 2 und ihre optimale Strategie.

Man sieht an diesem Beispiel schön, dass bei der Berechnung eines Safety-Levels der Gegenspieler nicht miteinbezogen wird. Da die erste Spalte in Matrix B die zweite streng dominiert, wird Spielerin B immer diese Spalte spielen. Verwendet Spieler A seine optimale Strategie, so erhält er eine durchschnittliche Auszahlung von, sein Safety-Level. Ist ihm dagegen bewusst, dass seine Gegenspielerin die erste Spalte spielt, so wird er immer die zweite Zeile wählen, da er dann eine Auszahlung von 4 erhält. Dies ist das 1,6-fache des Safety-Levels, jedoch besteht auch die Gefahr, dass Spielerin B, aus welchen Gründen auch immer, die zweite Spalte spielt, was für Spieler A einen Gewinn von nur 1 zur Folge hätte, welcher unter seinem Safety-Level liegt. Ein Safety-Level ist also, wie der Name schon sagt, eine risikofreie Art ein Bimatrixspiel zu spielen

4.3 Nash-Gleichgewicht

Analog zu Nash-Gleichgewichten in Matrixspielen definieren wir ein Nash-Gleichgewicht als (gemischtes) Strategieprofil, bei dem jeder Spieler keinen Vorteil erlangt, wenn nur er von seiner Strategie abweicht.

Sei das zwei Personen nicht-kooperative Spielgegeben.

Wir bezeichnen die durchschnittliche Auszahlung von Spieler A mit

und von Spielerin B mit

Definition 4.3.1: Gilt für ein gemischtes Strategieprofil

und

so nennt man es Nash-Gleichgewicht. Die Strategienundsind jeweils die besten Antworten des Spielers A bzw. B auf die Strategie des anderen Spielers.

Wählt jeder Spieler also eine seiner besten Antworten auf die Strategie des Gegners, so liegt ein Nash-Gleichgewicht vor. Verändert nur ein Spieler seine Strategie, so hat er davon keinen Vorteil.

Sowohl das Berechnen von Safety-Levels als auch von besten Antworten ist in der Praxis schwer, wenn man gemischte Strategien zugrunde legt. Nicht die beste, jedoch ein "gute" Antwort auf die Strategie des Gegenspielers erhält man, wenn man schätzt, mit welchen Wahrscheinlichkeiten er seine reinen Strategien wählt und danach dann die beste Antwort berechnet. Man vergleiche das Vorgehen mit dem Satz von Bayes.

Verwenden wir jedoch nur reine Strategien, so kann man mit Hilfe von Sattelpunkten alle Nash-Gleichgewichte aus reinen Strategien finden. Dabei muss wieder beachtet werden, dass die Einträge in der Matrix von Spielerin B Gewinne sind.

In der obigen Matrix sind jeweils die Maxima des ersten Elements im Tupel (Gewinne von Spieler A) in jeder Spalte und die Maxima des zweiten Elements im Tupel (Gewinne von Spielerin B) in jeder Zeile markiert. Sind in einem Eintrag der Matrix beide Elemente des Auszahlungstupels markiert, so liegt dort ein Nash-Gleichgewicht vor. In diesem Beispiel ist dies bei den reinen Strategieprofilen^[12] mit Auszahlungundmit Auszahlungder Fall. Da der Gewinn von Spieler A im Nash-Gleichgewicht das Maximum der Spalte ist, also das Maximum seiner verfügbaren reinen Strategien, kann er sich nicht verbessern, wenn er eine andere Strategie wählt. Ähnliches gilt für Spielerin B. Dass die Summe der Auszahlungen beider Spieler an den beiden Nash-Gleichgewichten jeweils 7 beträgt, ist reiner Zufall.

Die Definition eines Nash-Gleichgewichts haben wir hierbei seinem Namensgeber John Forbes Nash Jr. (1928 geboren) zu verdanken. In seiner 1950 eingereichten Dissertation verallgemeinerte er den bekannten Minimax-Satz^[13] (1928) von John von Neumann, der als Begründer der Spieltheorie gilt . Dieser besagt, dass jedes endliche Zwei-Personen-Nullsummenspiel mindestens ein Nash-Gleichgewicht aus gemischten Strategien besitzt. Zusammen mit zwei anderen Mathematikern (Selten und Harsanyi) wurde Nash 1994 für seine Leistungen in der Spieltheorie mit dem Nobelpreis für Wirtschaftswissenschaften ausgezeichnet. Sogar ein Hollywoodfilm, A Beautiful Mind (2001), handelt von ihm und seinem Umgang mit der Krankheit Schizophrenie, unter der er seit seinem vierten Lebensjahrzehnt leidet.

Satz 4.3.2 (Satz von Nash): Jedes nicht-kooperative Spiel besitzt mindestens ein Nash-Gleichgewicht aus gemischten Strategien.

Zum Beweis des Satzes benötigen wir mehr Hilfsmittel. Der interessierte Leser sei jedoch auf Nashs Dissertation (vgl. Nash 1950, S. 5f.) und einen Beweis mit Hilfe des Brouwerschen Fixpunktsatzes (vgl. Ferguson 2007, S. A-8f.) verwiesen.

4.4 Dominierte Strategien

Definition 4.4.1:

a) Eine gemischte Strategievon Spieler A dominiert seine reine Strategie, wenn

b) Eine gemischte Strategievon Spielerin B dominiert ihre reine Strategie, wenn

Gilt die Gleichheit nicht, so liegt strenge Dominanz vor.

Diese Definition entspricht genau dem, was wir bereits kennen. Auch stellen wir fest, dass beim Entfernen von streng dominierten Strategien uns kein Nash-Gleichgewicht "verloren geht":

Satz 4.4.2: Wird die reine Strategievondurchgemischte Strategie

streng dominiert und istein Nash-Gleichgewicht mitund, so ist.

Wir beweisen diesen Satz nur für Spieler A, da er für Spielerin B analog geführt wird:

Aus der strengen Dominanz erhalten wir

. (1)

Angenommen, dann kann man eine neue gemischte Strategie^[14] konstruieren:

Hierbei istder k-te kanonische Basisvektor im.

ist hierbei das Kronecker-Symbol.

Damit kann aberkein Nash-Gleichgewicht sein. □

Es bleibt noch zu beweisen, dass das Entfernen einer dominierten Strategie den Wert der Matrixbzw.und damit auch die Safety-Level der Spieler nicht ändert. Dazu schauen wir uns folgenden Satz für Matrixspiele an:

Satz 4.4.3: Wird in einem Matrixspieldie reine Strategievondurchgemischte Strategiedominiert, istein Nash-Gleichgewicht mit,und entsteht die Matrixdurch Entfernen deraus, so ist.

Betrachten wir zuerst die Dominanz der Strategien von Spieler A:

Für die strenge Dominanz folgt der Satz als Spezialfall von Satz 4.4.2, daund. Wir müssen also nur noch die Gleichheit bei der Dominanz beachten:

(1)

Wir konstruieren eine gemischte Strategiemit

Dann gilt:

ist also auch ein Nash-Gleichgewicht und damit.

Istder Vektor, der durch Streichen der k-ten Komponente ausentsteht, so istwegenein Nash-Gleichgewicht der Matrixund es gilt sogar

.

Der Beweis für die Dominanz Bs Strategien geht analog. Wir konstruieren ein

, erhalten durch

das Nash-Gleichgewichtder Matrixund letztendlich mit

. □

Korollar 4.4.4: In einem Bimatrixspiel bleiben die Safety-Level der Spieler erhalten, wenn man dominierte Strategien streicht.

Mit der Satz 4.2.1 folgt dies direkt aus Satz 4.4.3. □

4.5 Konstantsummenspiele

Ein Spezialfall des Bimatrixspiels ist das Konstantsummenspiel. Hierbei ist die Summe der Auszahlungen beider Spieler bei jedem erdenklichen Strategieprofil gleich einer Konstante c. Mit ist uns diese Form bereits als Matrixspiel, das ja die Nullsummeneigenschaft besitzt, bekannt.

Definition 4.5.1: Ein Bimatrixspielmit der Eigenschaft nennt man Z wei-Personen-Konstantsummenspiel.

Das Interessante ist nun, dass wir aus jedem Konstantsummenspiel ein Nullsummenspiel erstellen können, das vergleichbare Eigenschaften besitzt:

ist damit ein Matrixspiel. Schauen wir uns noch einmal das Kapitel 3 über Matrixspiele an, so fällt auf, dass bei allen Beweisen nicht die Höhe der Auszahlungen eine Rolle spielt, sondern immer nur die Vergleichsrelationenverwendet wurden. Damit kann man Eigenschaften wie Dominanz, Sattelpunkte und Nash-Gleichgewichte von einem Matrixspiel auf das korrespondierende Konstantsummenspiel übertragen. Zu den Auszahlungen muss natürlich wiederaddiert werden. Dieses bedeutet aber auch, dass ein Konstantsummenspiel keinen Wert, sondern nur Safety-Levels, besitzt. Ist nämlichder Wert des korrespondierenden Matrixspiels, so ist die garantierte Auszahlung in diesem Spiel von Spieler A und von Spielerin B . Übertragen wir diese Mindestauszahlungen wieder auf das Konstantsummenspiel, so müssen wir jeweils addieren. Die garantierte Auszahlung von Spieler A in unserem ursprünglichen Spiel beträgt damit

und von Spielerin B

Beispiel:

B ist die Matrix zum korrespondierenden Matrixspiel, welches man aus dem Konstantsummenspiel A erhält. In B dominiert die dritte Spalte streng die erste (ebenso in A). Deshalb kann man diese streichen. Übrig bleibt eine-Matrix, die man lösen kann. Sie besitzt keinen Sattelpunkt (ebenso wie A), man kann aber trotzdem optimale Strategien finden. Gemäß dem Satz 3.6.2 erhält man mit den dortigen Notationen

,und.

Damit betragen die Safety-Levels nach der obigen Notation

und.

4.6 Gefangenendilemma

Diese Bimatrix gehört zu dem wohl bekanntesten Spiel der Spieltheorie - dem Gefangenendilemma. Folgende Geschichte wird dazu erzählt:

Zwei mutmaßliche Verbrecher werden von der Polizei verhaftet und in zwei separaten Zellen zu ihrer gemeinsam begangenen Tat verhört. Sie können dort nicht miteinander sprechen. Beiden wird nun folgendes Angebot gemacht: Verrät ein Verdächtiger den anderen, so wird dieser zur Höchststrafe (10 Jahre) verurteilt. Der Informant wird von der Polizei dagegen freigelassen, jedoch nur, wenn der andere nicht auch auspackt. Verraten sie sich also gegenseitig, bekommen beide die Mindeststrafe (8 Jahre) für ihre Verbrechen, da sie gestanden haben. Entscheiden sich beide zum Schweigen (kooperieren mit dem anderen), so kann man sie nur wegen Kleinigkeiten aus ihrer Vergangenheit belangen. Dies führt für beide zu einer nur geringen Strafe von 2 Jahren.

Spieltheoretisch ist dieses Spiel sehr interessant. Es handelt sich um kein Konstantsummenspiel, d.h. beide Spieler wären gut daran zu kommunizieren und das Strategieprofil mit der größten Gesamtauszahlung zu wählen, um diese dann untereinander aufzuteilen. Durch die Regeln des Spiels ist ihnen aber das Kommunizieren verboten und ein Austauschen von Haftstrafen ist auch nicht möglich. Man sieht sofort, dass ein stabiler Sattelpunkt existiert, nämlich (Verraten, Verraten) mit der Auszahlung. Dieser bietet jedoch im Vergleich zum Strategieprofil (Kooperieren, Kooperieren) mit der AuszahlungNachteile: Die Auszahlung ist für beide Spieler jeweils schlechter und auch die Gesamtauszahlung, die bei kooperativen Spielen eine Rolle spielt, ist die geringste gegenüber allen anderen Strategieprofilen. Man würde also eher erwarten, dass beide Verdächtige kooperieren, jedoch verleitet die Aussicht, auf freien Fuß gesetzt zu werden und die Gefahr, vom anderen verraten zu werden, ebenfalls zum Verrat. Dies sieht man auch daran, dass die zweite Zeile bzw. Spalte die erste Zeile bzw. Spalte streng dominiert. Deswegen auch die Bezeichnung "Dilemma". Dieses Spiel soll zeigen, dass Dominanz und Sattelpunkte nicht immer zu einem vernünftigen Ergebnis führen.

Noch interessanter ist das mehrmalige Spielen. Die Gefangenen können dann abhängig vom letzten Ergebnis den Gegenspieler einschätzen und dahingehend handeln. Robert Axelrod, ein Politikwissenschaftler, führte 1979 einen Wettbewerb durch. Er forderte alle Interessierten auf, ein Computerprogramm einzuschicken, dass einen Spieler in Gefangenendilemma simulieren sollte. Jedes Programm trat gegen jeweils jedes andere und einen seiner Klone an, wobei in einem Spiel gegen den gleichen Gegner 200 Runden (vgl. Schalk 2007, S. 65) Gefangenendilemma gespielt wurde. Jedem Computerprogramm war es erlaubt alle Züge im Spiel gegen denselben Gegner zu speichern, wodurch es ihm möglich wurde auf die vergangenen Aktionen seines Kontrahenten zu reagieren. Informationen aus den Spielen über andere Gegner durften jedoch nicht verwendet werden. Wer am Ende des Turniers die meisten Punkte^[15] gesammelt hatte, hat gewonnen.

Nachdem Axelrod das Turnier fünfmal wiederholte, präsentierte er sein überraschendes Ergebnis: Bei den vielen eingesendeten Quellcodes konnte man vermuten, dass ein komplexes Programm eines Mathematikers gewinnen würde. Stattdessen gewann das kürzeste Programm (4 Codezeilen in Basic, vgl. ebd., S. 65) des Philosophen und Psychologen Anatol Rapoport. Der Name TitForTat (engl.: "Wie du mir, so ich dir."; kurz: TFT) verrät bereits seine einfache Vorgehensweise. In der ersten Runde kooperiert TitForTat, danach kopiert es immer den vorherigen Zug seines Gegners. Nach weiteren Untersuchungen und Turnieren formulierte Axelrod zwei wichtige Eigenschaften, die ein Programm aufweisen sollte:

1. Nettigkeit: Das Programm kooperiert immer in der ersten Runde.

2. Vergebung: Das Programm vergibt dem anderen nach irgendeinem Zeitpunkt, d.h. es weicht vom Sattelpunkt (Verraten, Verraten) ab.

Beim ersten Turnier waren alle acht höchstplatzierten Teilnehmer nett. In den nachfolgenden Turnieren vergaben sogar fast alle Programme ihrem Gegner einen Verrat, d.h. diese Eigenschaft wurde von vielen Teilnehmern als notwendig erachtet.

Der Erfolg jedes einzelnen Programms hängt hierbei nicht nur von seinen Eigenschaften, sondern von der Umgebung, den Teilnehmer des Turniers, ab. TitForTat ist dabei sehr anpassungsfähig, da es gegen ein Programm, das häufig kooperiert, eine hohe Punktzahl erzielt und sich von einem "bösen" Programm, das häufig verrät, nicht ausnutzen lässt.

Inwieweit solche Ergebnisse der Spieltheorie für die Sozialwissenschaften relevant sind, lässt sich streiten. Auch Evolutionäre Spiele liefern interessante Ergebnisse. Hierbei hängt die Population der nächsten Runde, also die Anzahl jeder Art von Programmen, von deren Erfolg in der vergangenen ab. Man kann dann untersuchen, wie sich Populationen entwickeln und auf Eindringlinge, also das zufällige Erscheinen von neuen Programmen, reagieren.

Wir gehen aber auf dieses Gebiet der Spieltheorie nicht weiter ein. Der interessierte Leser sei auf Schalk 2007, S. 76 - 97 verwiesen.

4.7 Braess-Paradoxon

Abseits von Spielen, Wirtschaft und evolutionären Simulationen fand die Spieltheorie auch noch in einem anderen Bereich Anwendung: In der Verkehrsplanung. Schauen wir uns dazu am besten ein Beispiel an.

Abbildung 3: Verkehrslage beim Braess-Paradoxon

Jeden Morgen fährt die gleiche Anzahl an Pendlern von Stadt A nach Stadt D zur Arbeit. Da eine direkte Verbindung wegen einem Berg nicht existiert, müssen sie über die dazwischengelegenen Städte B und C fahren. Jedem Fahrer stehen zwei Wege zur Verfügung, die über verschiedene Straßentypen führen. Man kann entweder über eine Landstraße (Straße 1) nach B und dann weiter über eine Autobahn (Straße 3) fahren ("unterer Weg"). Oder man wählt die Route über Straße 2 (Autobahn) nach C und dann weiter über eine Landstraße (Straße 4) nach D ("oberer Weg"). Die Städte und Straßen sind in Abbildung 3 dargestellt. Die Zeit, die man für die Fahrt über die beiden Straßentypen benötigt, ist dabei abhängig von dem Verkehrsaufkommen, also der Anzahl der Fahrzeuge, die sie benutzen.

Seidie Zeit (in Minuten), die jedes Auto benötigt, um über Straßezu fahren, wennAutos sich darauf befinden.

Die Fahrzeit über Landstraßen ist stark verkehrsabhängig:

Die von Autobahnen dagegen weniger:

Berechnen wir nun die Fahrzeit beider Wege für eine Gesamtzahl vonAutos.^[16] Zu jedem Zeitpunkt ist diese Anzahl konstant, d.h. wir "verlieren" auf unserem Weg keine Autos. Dadurch erhalten wir mehrere Gleichungen:

(1) (In A teilen sich die Autos auf die zwei Wege auf.)
(2) (Gleichviel Autos fahren in Stadt B hinaus wie hinein.)
(3) (Gleichviel Autos fahren in Stadt C hinaus wie hinein.)

Jeder Autofahrer stellt nun einen Spieler dar. Er kann jeden Morgen selbst entscheiden, welchen Weg (Aktion) er wählt. Dabei verhält er sich möglichst rational, d.h. er wählt den schnellsten Weg. Wir nehmen zusätzlich noch an, dass jeder Autofahrer im Radio vor der Abfahrt die Information erhält, wie viel die Fahrtzeit am vorherigen Tag auf jedem Weg betrug. Die Autofahrer werden ihre Route also solange anpassen bis die Fahrtzeit für den oberen Weg gleich der für den unteren Weg ist. Dann sieht kein Autofahrer mehr einen Grund, die Route zuwechseln, denn immerhin erhält er dadurch keinen Zeitvorteil. Es handelt sich also um ein Nash-Gleichgewicht, das in diesem Fall stabil ist, also bestehen bleibt, wenn es einmal erreicht wurde. Weicht nämlich auch nur ein Fahrer vom Gleichgewicht ab, so erhöht er die Fahrzeuganzahl auf der von ihm gewählten Strecke und damit auch seine Fahrtzeit. Das Gleichgewicht liefert uns

Abbildung in dieser Leseprobe nicht enthalten

Beschreiben wir nun die Fahrtzeiten in Abhängigkeit des Verkehrsaufkommens

Abbildung in dieser Leseprobe nicht enthalten

nutzen (2) und (3)

Abbildung in dieser Leseprobe nicht enthalten

und vereinfachen

Abbildung in dieser Leseprobe nicht enthalten

so erhalten wir miteine gleichmäßige Auslastung der beiden Wege mit je Autos. Die Fahrtzeit der beiden Wege beträgt dabei

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Braess-Paradoxon mit zusätzlichem Tunnel

Nun ist der Bevölkerung diese Fahrtzeit zu lang, weshalb der Verkehrsminister beschließt, einen Tunnel durch den Berg zwischen Stadt B und C bauen zu lassen (s.h. Abbildung 4). Die Fahrtzeit auf dieser fünften Straße beträgt mitdie Anzahl der Autos, die durch den Tunnel fahren,

Abbildung in dieser Leseprobe nicht enthalten

Es liegt wieder ein Nash-Gleichgewicht vor, weshalb die Gleichheit aller Fahrzeiten gelten muss:

Abbildung in dieser Leseprobe nicht enthalten

Wir verlieren wieder keine Autos:

Abbildung in dieser Leseprobe nicht enthalten

Schauen wir uns nur den ersten Teil des Nash-Gleichgewichts an:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

Aus dem zweiten Teil des Nash-Gleichgewichts erhalten wir

Abbildung in dieser Leseprobe nicht enthalten

Die Fahrtzeit für den oberen Weg (und damit auch die für die anderen Wege) beträgt schließlich:

Überraschenderweise hat damit der Bau des Tunnels nicht zu einer Verbesserung der Verkehrssituation, sondern zu einer Verschlechterung geführt. Würden alle Fahrer den Tunnel ignorieren und stattdessen nur den oberen oder unteren Weg benutzen, so betrüge die Fahrtzeit wieder 83 Minuten. Die Versuchung jedes Autofahrers ist dann jedoch groß, den Tunnel allein zu benutzen. Wechselt z. B. einer der Fahrer des oberen Weges auf den mittleren, dann würde seine Fahrtzeit nur 81 Minuten betragen. Jedoch zum Leid der anderen. Die Fahrtzeit des oberen Weges betrage dann 82 Minuten, die des unteren Weges jedoch 93 Minuten. Schauen also alle Fahrer ohne Rücksicht auf die Gemeinschaft auf ihren eigenen Vorteil, so führt dies zu einer schlechteren Situation für alle.

Nachdem der Mathematiker Dietrich Braess diese Erkenntnis 1968 veröffentlichte, konnte man das Phänomen mehrmals beobachten. Darunter in New York, wo die Sperrung einer Straße die Verkehrslage verbesserte und in Stuttgart, wo das Bauen einer neuen Straße die Verkehrssituation verschlechterte (vgl. Blum 2006).

5 Kombinatorische Spieltheorie

Matrix- und Bimatrixspiele mögen schön zum Rechnen sein, jedoch muss man zur Analyse alle verfügbaren Strategien kennen. Dies gestaltet sich bei den uns bekannten Gesellschaftsspielen als praktisch unmöglich, jedoch gibt es für diese auch einfachere Verfahren.

Definition 5.0.1: Ein Kombinatorisches Spiel erfüllt folgende Bedingungen:^[17]

1. Es gibt genau zwei Spieler.

2. Das Spiel hat endlich viele Positionen.

3. Die Spieler wechseln sich mit dem Ziehen ab.

4. Die Regeln legen fest, zu welchen Positionen der Spieler, der am Zug ist, von der aktuellen Position aus ziehen darf. Dabei haben beide Spieler an jeder Position die gleichen Zugmöglichkeiten (neutrales Spiel).

5. Es liegt perfekte Information vor.

6. Je nach Regel ist der Spieler, der eine Position erreicht, von der es keine Zugmöglichkeiten mehr gibt, der Gewinner oder Verlierer. Dementsprechend verliert bzw. gewinnt der andere Spieler.

7. Das Spiel endet immer nach endlich vielen Zügen.

Man kann den Begriff auch noch allgemeiner fassen, z. B. unendlich viele Positionen zulassen, die Zugmöglichkeiten spielerabhängig gestalten oder ein Spielende nicht zwingend voraussetzen, was dann zu einem Unentschieden führen kann. Für unsere Zwecke genügt jedoch die speziellere Definition.

Bemerkung: Aus der Definition folgt, dass es keine Natur, gleichzeitige Züge oder geheime Informationen gibt.

Bekannte Beispiele für kombinatorische Spiele sind Schach, Dame und nach geeigneter Modifikation der Spielregeln auch Go. Der Leser möge sich überlegen, ob sie auch kombinatorische Spiele nach der obigen Definition 5.0.1 sind.

5.1 P- und N-Positionen

Schauen wir uns am besten ein geeignetes Beispiel an. Beim Streichholzspiel (vgl. ebd., S. I-3) gibt es folgende Regeln:

Zwei Spieler A und B wechseln sich in ihren Zügen ab. Vor ihnen liegt ein Stapel Streichhölzer, z. B. 21 Stück. Diesen Stapel können sie jederzeit zählen, d.h. sie wissen immer wie viel Streichhölzer noch daliegen. Ein Zug besteht nun darin, 1 bis 3 Streichhölzer vom Stapel zu entfernen, keines wegzunehmen, ist also verboten. Derjenige, der das letzte Streichholz entfernt, gewinnt das Spiel.

Versuchen wir nun herauszufinden, ob es eine Gewinnstrategie gibt, also eine Strategie, die uns immer gewinnen lässt.

Liegen nur noch 1, 2 oder 3 Streichhölzer auf dem Tisch, so kann der Spieler, der an der Reihe ist, gewinnen, indem er alle wegnimmt. Bei vier Streichhölzern ist dies nicht mehr möglich. Im Gegenteil: Egal wie viele er wegnimmt, es bleiben 1 bis 3 Streichhölzer liegen, was es dem Gegner ermöglicht zu gewinnen. Bei 5 bis 7 Streichhölzern ist es möglich den Stapel auf 4 Streichhölzer zu verringern, was dem Gegner keine Chance lässt. Denn nach seinem Zug sind 1 bis 3 Streichhölzer übrig, was es dem anderen Spieler ermöglicht zu gewinnen. Die Position mit acht Streichhölzern ist uns auch schon bekannt. Ein Zug von dieser Position aus führt immer zu 5 bis 7 Streichhölzern, eine Position, von der man gewinnen kann, wie wir gerade gesehen haben.

Man kann diese Überlegungen fortsetzen und bemerkt, dass man von Positionen mit 1 bis 3, 5 bis 7, 8 bis 11, usw. Streichhölzern immer gewinnen kann. Wir nennen diese N-Positionen. Voraussetzung ist, dass man so viele Streichhölzer entfernt, so dass eine Anzahl übrig bleibt, die durch 4 teilbar ist. Der Gegner hat dann 4, 8, 12, usw. Streichhölzer vor sich liegen (P-Positionen). Unabhängig von seinem Zug bleiben 1 bis 3, 5 bis 7, usw. Streichhölzer übrig. Wir befinden uns also wieder auf einer N-Position. Führen wir das Spiel in dieser Weise weiter, so ist es uns immer möglich, so viele Streichhölzer wegzunehmen, dass der Gegner sich auf einer P-Position befindet. Er kann von dort aus jedoch nur auf eine N-Position ziehen. Da man mindestens ein Streichholz pro Zug entfernen muss, wird der Stapel immer kleiner bis wir uns irgendwann auf einer N-Position mit 1 bis 3 Streichhölzern befinden. Nun ist es uns möglich zu gewinnen, indem wir alle Streichhölzer entfernen.

Die Gewinnstrategie besteht also darin, dass man bei jedem Zug so viele Streichhölzer entfernt, dass eine durch 4 teilbare Anzahl (die Null zähle hier ausnahmsweise auch dazu) übrig bleibt. Dies ist uns jedoch nur möglich, wenn wir uns nicht selber auf einer P-Position befinden. Bei unserem Beispiel mit 21 Streichhölzern ist es also wichtig, dass wir beginnen dürfen, um im ersten Zug ein Streichholz zu entfernen. Beginnt unser Gegner, so können wir zwar immer noch die Möglichkeit bekommen auf eine P-Position zu ziehen, jedoch ist dies von unserem Gegner abhängig. Zieht er immer auf eine P-Position, z. B. weil er ebenfalls die Gewinnstrategie für dieses Spiel kennt, so verlieren wir zwingend.

Definieren wir nun P- und N-Positionen genauer und klären deren Namensgebung:

Definition 5.1.1: P- bzw. N-Positionen sind bestimmte Positionen in einem kombinatorischen Spiel:

a) Alle Züge von einer P-Position führen zu einer N-Position.

b) Mindestens ein Zug von einer N-Position führt zu einer P-Position.

Bezeichnet man alle Endpositionen, also Positionen, von denen kein Zug mehr möglich ist, als P-Positionen, wenn der Spieler, der dorthin zieht, gewinnt und andernfalls als N-Positionen, so kann man per Induktion durch die oben gegebene Definition möglichst viele P- und N-Positionen finden. Bei dem Streichholzspiel sind wir so vorgegangen. Eine Gewinnstrategie besteht nun darin, immer auf P-Positionen zu ziehen. Von dieser Position kann der Gegner nur N-Positionen erreichen, was uns das Ziehen auf eine P-Position wiederum ermöglicht. Es wird damit gewährleistet, dass man sich immer auf N-Positionen und der Gegner sich immer auf P-Positionen befindet. Sehen die Spielregeln vor, dass man beim Erreichen einer Endposition gewinnt, so können nur wir diese erreichen, da sie eine P-Position ist. Im gegenteiligen Fall verliert man beim Erreichen einer Endposition, welche dann jedoch eine N-Position ist, auf die nur der Gegner ziehen kann. Da das Spiel immer endet führt dies dazu, dass wir gewinnen.

Daher rühren auch die Bezeichnungen: Von einer P -Position aus ist es dem vorherigen (engl.: previous) Spieler, also dem Spieler, der auf diese Position gezogen hat, möglich zu gewinnen. Bei einer N -Position ist es dem nächsten (engl.: next) Spieler, also dem Spieler, der von dieser Position aus zieht, möglich zu gewinnen.^[18]

5.2 Nim

Mit Streichhölzern kann man noch mehr interessante Spiele erstellen. Eines davon ist Nim. Hierbei wird eine beliebige Anzahl von Streichhölzern in drei Stapel aufgeteilt. Dabei dürfen wieder beide Spieler die Streichhölzer nachzählen, dass heißt, sie wissen immer wie viele sich in jedem Stapel befinden. Die Spieler wählen abwechselnd einen (nicht-leeren) Stapel aus und entfernen dann daraus eine beliebige Anzahl. Dabei muss mindestens ein Streichholz entfernt werden, es kann aber auch der ganze Haufen weggenommen werden. Wichtig ist, dass die anderen Stapel dabei unberührt bleiben. Wer das letzte Zündholz nimmt, gewinnt.

Seidie Anzahl der Streichhölzer im i-ten Stapel, so lässt sich jede Position im Spiel durch einen Tupelbeschreiben. Hierbei istdie einzige Endposition und damit auch P-Position. Einfach gestaltet sich das Spielen, wenn nur noch ein Stapel übrig ist. Ist man an der Reihe, so entfernt man alle Streichhölzer des einzigen Haufens und gewinnt somit. Also sind, undfür jeweils alleN-Positionen. Sind noch zwei Stapel übrig, so kann man sich leicht überlegen, dass Positionen, bei denen die Streichholzanzahl in beiden Stapeln gleich sind, P-Positionen und die restlichen N-Positionen sind. Entfernt man nämlich von irgendeiner P-Position (z. B.) den Regeln gemäß Streichhölzer, so verringert man eine Stapelgröße, lässt die andere aber gleichbleibend. Man zieht also immer zu einer N-Position, da sich die Stapelgrößen unterscheiden. Von dort aus ist es aber nun einfach möglich zu einer P-Position zu gelangen. Man entfernt von dem größeren der beiden Stapel so viele Streichhölzer, dass beide Haufen genau gleichgroß sind. Letztendlich erreicht man somit die Endposition.

Bei drei und mehr Stapeln wird uns ein intuitives Vorgehen nicht zum Ziel führen. Stattdessen schauen wir uns ein Verfahren an, wie man einfach erkennen kann, ob eine Spielsituation eine P-Positionen ist.

Satz 5.2.1: In einem Nim-Spiel mitStapeln istgenau dann eine P-Position, wenn die Nim-Summeder Komponenten Null ergibt.

Es bleibt natürlich noch zu klären, was die Nim-Summe ist. Da diealle nicht-negative ganze Zahlen sind, können wir sie im Binärsystem, also dem Zahlensystem zur Basis 2, darstellen. Wir schreiben die Zahlen dann in Klammern mit einer 2 als Basis im Index, um Verwechslungen mit dem Dezimalsystem zu vermeiden.

Beispiele:

Wir können in diesem Binärsystem eineVerknüpfungeinführen. Sie entspricht der schriftlichen Addition ohne Übertrag oder mit Fachbegriff auch bitweises exklusives ODER genannt. Hierbei ist die i-te Stelle in der Summe genau dann 1, wenn es auch die i-te Stelle der beiden Summanden sind (ziffernweise Addition Modulo 2).

Beispiel:

Die Nim-Summe von 5 und 14 ist nicht Null, weshalb nach dem obigen Satzeine N-Position ist. Dies deckt sich mit unserer Erkenntnis bei Nim-Spielen mit zwei Stapeln.

Definition 5.2.2: Die Verknüpfung bitweises exklusives ODERwird Nim-Summe genannt.

Für allegilt dabei:

(Assoziativgesetz)

(Kommutativgesetz)

(Existenz eines neutralen Elements)

(Jede Zahl ist zu sich selbst Inverses.)

(Kürzungsregel)

Der einfache Beweis dieser Eigenschaften sei dem Leser überlassen. Sie ermöglichen uns nun auch die Nim-Summe von mehreren Zahlen zu bilden. Möchten wir beispielsweise herausfinden, ob eine P-Position ist, so addieren wir die Stapelgrößen im Binärsystem ohne Übertrag

und sehen, dass die Summe ungleich Null ist. Es handelt sich also um eine N-Position. Durch welchen Spielzug gelangen wir nun aber zu einer P-Position?

Beim Addieren gehen wir ziffernweise vor. Steht in der Spalte über einer Ziffer im Ergebnis eine ungerade Anzahl an Einsen, so ist diese Ziffer auch Eins. Andernfalls ist sie Null. Wir müssen also nur einen Zug finden, der bewirkt, dass in jeder Spalte eine gerade Anzahl von Einsen steht. Dies erreichen wir z. B. durch Entfernen von 5 des ersten, 3 des zweiten oder 3 Streichhölzern des dritten Stapels.

Wie man dabei systematisch vorgeht, sieht man in dem Beweis des Satzes 5.2.1 (vgl. Ferguson 2007, S. I-10f.):

sei die Menge aller Positionen mit Nim-Summe Null, die Menge mit Nim-Summe ungleich Null. Prüfen wir nun anhand von Definition 5.1.1, ob alle Elemente inP-Positionen und alle Elemente inN-Positionen sind. Da man beim Entfernen des letzten Streichholzes gewinnt, musseine P-Position sein. Tatsächlich ist die Nim-Summe Null und damit.

a) Alle Züge von einer P-Position führen zu einer N-Position:

Ziehen wir von einer P-Positionzu einer anderen, so entfernen wir vom i-ten Stapel eine gewisse Anzahl Streichhölzer. Wir erhalten somit die neue Position mit. Wäre diese nun in der Menge P enthalten, so muss wegengelten:

Durch die Kürzungsregel erhalten wir aber, was bedeuten würde, dass von keinem Stapel ein Streichholz entfernt wurde. Da dies gegen die Regeln ist, folgt .

b) Mindestens ein Zug von einer N-Position führt zu einer P-Position:

Wir haben also mehrere Zahlen gegeben (Größe der Stapel), deren Nim-Summe ungleich Null ist. Unser Ziel ist es nun durch Verkleinern einer Zahl eine Nim-Summe von Null zu erhalten. Wäre das bloße Ersetzen einer Zahl ungeachtet der Größe erlaubt, so gestaltet sich dies einfach: Wir schauen in jede Spalte der schriftlichen Addition nach der Anzahl der Einsen und wählen unsere neue Zahl so, dass die Anzahl immer gerade ist. Jedoch dürfen wir eine Zahl nur durch eine kleinere ersetzen, die zu ersetzende Zahl muss also groß genug sein. Wählen wir eine Zahl, die in der von links beginnend ersten Spalte mit einer ungeraden Anzahl Einsen auch eine Eins besitzt, so ist diese groß genug. Beim Anpassen der Ziffern dieser Zahl wird nämlich diese Eins zur Null und somit die Zahl definitiv kleiner als unsere Ausgangszahl.

Damit sindundnach Definition die Mengen aller P- bzw. N-Positionen. □

Teil b) des Beweises liefert uns auch gleich eine Möglichkeit von einer N-Position auf eine P-Position zu ziehen. Verdeutlichen wir dies einmal an einem Beispiel:

In der ersten Spalte befindet sich eine gerade Anzahl an Einsen, was auch an der 0 als erste Ziffer der Nim-Summe zu erkennen ist. Erst in der zweiten Spalte befindet sich eine ungerade Anzahl. Als einzige Zahl, deren zweite Ziffer eine 1 ist, bietet sich diean. Wenn wir diese aufsetzen, so wird die Nim-Summe Null:

Wir haben damit zur N-Positioneine P-Positiongefunden.

Nim lässt sich in der Praxis also nur mit Hilfe eines Zettels und Stifts gewinnen - vorausgesetzt unser Gegner ist nicht mit den gleichen Waffen gerüstet, wenn er beginnen darf.

6 Quellenverzeichnis

Blum, Wolfgang (2006): Ewig lockt die Schnellstraße. In: Süddeutsche Zeitung vom 24.01.2006. URL: http://www.sueddeutsche.de/wissen/artikel/800/68732/ - Download vom 27.12.2007.

Ferguson, Thomas S. (2007): Game Theory. University of California at Los Angeles. Letzte Aktualisierung: 06.09.2007. URL: http://www.math.ucla.edu/~tom/Game_Theory/ - Download vom 29.10.2007.

International Business Machines Corporation (IBM) (1997): Kasparov vs Deep Blue: a contrast in styles. Dissimilar processes yield similar conclusions. URL: http://www.research.ibm.com/deepblue/meet/html/d.2.shtml - Download vom 25.12.2007.

Kummer, Bernd (2006): Fixpunkte (und einige weitere grundlegende Existenzsätze) und ihre Anwendungen in der Spieltheorie und Optimierung. Proseminar WiSem 2005/06. Letzte Aktualisierung: 02.01.2006. URL: http://www.mathematik.hu-berlin.de/~kummer/scripts/fixp_spi.pdf - Download vom 01.01.2008.

Nash, John F. (1950): Non-cooperative Games. URL: http://www.princeton.edu/mudd/news/faq/topics/Non-Cooperative_Games_Nash.pdf - Download vom 02.01.2008.

Rasmusen, Eric: Games And Information. An Introduction to Game Theory. 4. Auflage, Malden, Oxford, Carlton (Victoria): Blackwell Publishing 2007.

Schalk, Andrea (2007): COMP30191 (was: CS3191). The Theory of Games and Game Models. Letzte Aktualisierung: 06.09.2007. URL: http://www.cs.man.ac.uk/~schalk/3192/notes.pdf - Download vom 29.10.2007.

7 Register

Abbildung in dieser Leseprobe nicht enthalten

8 Selbstständigkeitserklärung

Ich versichere, dass ich die vorgelegte Arbeit selbstständig und nur mit den angegebenen Hilfsmitteln angefertigt habe. Wörtlich oder indirekt übernommenes Gedankengut wurde von mir als solches kenntlich gemacht.

Datum: 7. Januar 2008 Unterschrift:

(Dennis Grunert)

[...]

---

^[1] Bei nur einem Spieler verwendet man die sogenannte Entscheidungstheorie zur Analyse.

^[2] In der deutschen Literatur wird auch häufig der englische Begriff "Common Knowledge" oder "Gemeinsames Vorwissen" verwendet.

^[3] Man kann auch Informationsmengen für jeden Spieler definieren, wenn er gar nicht an der Reihe ist. Bei Basic Endgame Poker (Abschnitt 2.2) z. B. erfährt Spielerin B nach der Aktion fold nie, welche Karte Spieler A auf der Hand hielt, da die Auszahlung an beiden Endknoten gleich ist. Diese befinden sich also in derselben Informationsmenge. Spielrelevant können verschiedene Informationen an Endknoten jedoch nur bei wiederholtem Spielen sein.

^[4] Diese Namen sind uns schon aus vorherigen Beispielen bekannt. Traditionell ist der zweite Spieler immer weiblich. Dies kann jedoch zu Unstimmigkeiten in der deutschen Sprache führen, wenn nicht bekannt ist, welcher Spieler gemeint ist. Trotzdem beuge ich mich hier der Tradition.

^[5] ist dabei die Menge aller-Matrizen mit Einträgen in.

^[6] Der Autor distanziert sich von jeder Aussage Arnolds, dass Kultur keinen Spaß mit sich bringen würde.

^[7] Aufgrund des Erscheinungsbilds schreiben wir Vektoren im Allgemeinen als Zeilenvektoren. Diesen Sachverhalt muss man bei der Matrizenmultiplikation berücksichtigen.

^[8] Hierbei istder transponierte Vektor von.

^[9] Sobald ein garantierter Gewinn für alle reinen Strategien von Spielerin B existiert, ist dieser auch aus der Definition 3.3.1 gemischter Strategien für diese garantiert.

^[10] Es wird analog zu Ferguson 2007, S. II-9 vorgegangen.

^[11] deut.: Sicherheitsstufe

^[12] Da die Strategien in einem Bimatrixspiel nummeriert sind, schreiben wir wieder kurz, wenn wir das Strategieprofilmeinen.

^[13] Beweise befinden sich in Kummer 2006, S. 9ff.

^[14] Der Leser möge sich klarmachen, warumeine gemischte Strategie ist. Jede Komponente muss dazu zwischen 0 und 1 liegen und die Summe aller Komponenten 1 ergeben.

^[15] Axelrod legte dem Turnier eine andere Auszahlungsmatrix mit positiven Einträgen zugrunde. Dies ist möglich, da beim Gefangenendilemma die Einträge nur verschiedene Eigenschaften erfüllen müssen, die konkreten Werte sind dabei nebensächlich.

^[16] Um realistischere Zahlen zu erhalten, kann man sich die Anzahl in Tausender vorstellen.

^[17] vgl. Ferguson 2007, S. I-4

^[18] Im Deutschen trifft man auch die Bezeichnungen G-Situation (Gewinner) für N-Position und U-Situation (unsicher) für P-Position an.