Der Begriff des Nash-Gleichgewichts ist ein zentraler Begri¤ der mathematischen Spieltheorie. Es handelt sich dabei um ein Lösungskonzept von Spielen, das sich dadurch auszeichnet, dass die Spieler ihre Strategieentscheidungen nicht revidieren wollen, wenn ihnen die Lösung empfohlen wird. Dieses Lösungskonzept ist allgemein für nicht-kooperative Spiele akzeptiert und wird als Gleichgewicht bezeichnet.
Die Spieltheorie (engl. game theory) ist ein Teilgebiet der Mathematik, das sich mit der Modellierung und Untersuchung von Gesellschaftsspielen, von im weitesten Sinn gesellschaftsspielähnlichen Interaktionssystemen sowie mit den in
solchen Systemen eingesetzten Strategien beschäftigt. Dabei ist die Spieltheorie weniger eine zusammenhängende Theorie als vielmehr ein Instrument zur Analyse von strategischen Entscheidungssituationen. Lösungen von Spielen, die sich dadurch auszeichnen, dass die Spieler ihre Strategieentscheidungen nicht revidieren wollen wenn ihnen die Lösung empfohlen wird, werden als Gleichgewicht bezeichnet. Im Rahmen dieser Arbeit soll insbesondere auf ein allgemein
akzeptiertes Konzept zur Lösung von nicht-kooperativen Spielen eingegangen werden, das Nash-Gleichgewicht. In einem weiteren Schritt wird genauer auf eine oft verwendete Art von Spielen, die sogenannten streng kompetitiven Spiele oder auch Nullsummenspiele, eingegangen und kurz angedeutet, wie die Theorie der nicht-kooperativen Spiele auf jene der kooperativen erweitert werden kann.
Inhaltsverzeichnis
1 Einleitung
2 Terminologie und Definitionen
3 Existenz eines Gleichgewichts
3.1 Existenzbeweis unter Verwendung des Fixpunktsatzes von Brouwer
3.2 Existenzbeweis unter Verwendung des Fixpunktsatzes von Kaku-tani
4 Nash-Equilibrium in streng kompetitiven Spielen
5 Einblick in kooperative Spiele
6 Schlusswort und Ausblick
1 Einleitung
Die Spieltheorie (engl. game theory) ist ein Teilgebiet der Mathematik, das sich mit der Modellierung und Untersuchung von Gesellschaftsspielen, von im weitesten Sinn gesellschaftsspielähnlichen Interaktionssystemen sowie mit den in solchen Systemen eingesetzten Strategien beschäftigt. Dabei ist die Spieltheorie weniger eine zusammenhängende Theorie als vielmehr ein Instrument zur Analyse von strategischen Entscheidungssituationen. Lösungen von Spielen, die sich dadurch auszeichnen, dass die Spieler ihre Strategieentscheidungen nicht revidieren wollen wenn ihnen die Lösung empfohlen wird, werden als Gleichgewicht bezeichnet. Im Rahmen dieser Arbeit soll insbesondere auf ein allgemein akzeptiertes Konzept zur Lösung von nicht-kooperativen Spielen eingegangen werden, das Nash-Gleichgewicht. In einem weiteren Schritt wird genauer auf eine oft verwendete Art von Spielen, die sogenannten streng kompetitiven Spiele oder auch Nullsummenspiele, eingegangen und kurz angedeutet, wie die Theorie der nicht-kooperativen Spiele auf jene der kooperativen erweitert werden kann.
2 Terminologie und Definitionen
Wir präsentieren hier die Basiskonzepte wie auch die notwendigen Definitionen zum allgemeinen Verständnis der Spieltheorie. Die Herleitung der Idee und der Lösung von nicht-kooperativen Spielen folgen daraus implizit.
Definition 1 Ein strategisches n-Personen Spiel G kann als Tripel
Abbildung in dieser Leseprobe nicht enthalten
geschrieben werden. Dabei setzt sich das Spiel aus n Spielern zusammen, wobei jeder Spieler i über eine endliche Anzahl von reinen Strategien nia 2 Hi verfügt а — 1, 2,m. Die nia können in einer Menge Hi C Rm, der Strategiemenge des Spielers i, zusammengefasst werden. Wir notieren mit Xi2nHi — Hi x H2 x ... x Hn die entsprechende Produktmenge beziehungsweise das kartesische Produkt aus den Strategiemengen der einzelnen Spieler. Weiters wird jedem Spieler i eine stetige, quasikonkave1 Auszahlungsfunktion ai : Xi2nHi ! R zugeordnet, welche die n -Tupel der Strategien nach R abbildet.2
Implizit wird in dieser Definition angenommen, dass sich die gewählten Strategien in Spielausgängen niederschlagen, die dann zu verschiedenen Auszahlungen führen. Für eine explizite Modellierung kann der direkte Einbau von Spielausgängen hilfreich sein.
Definition 2 (gemischte Strategie oder Randomisierung) Eine gemischte Strategie Si eines Spielers i ist eine Kombination seiner reinen Strategien Wia 2 Di und wird ebenfalls als ein Element von D betrachtet. Wir schreiben Si = ΣCiaría 2 Di mit βία > 0 und Σcia = 1. Die gemischten Strategien si können also als Linearkombinationen angesehen werden. Wir unterstellen von nun an, dass die Menge Di der Si eine nicht-leere, kompakte und konvexe Teilmenge des Euklidischen Raumes ist.3
Bemerkung 3 Wir bemerken, dass eine pure Strategie Wia auch immer als eine gemische Strategie Si geschrieben werden kann.
Beispiel 4 Ein Unternehmen i kann als Output die Menge жц = 0 und Wi2 = M produzieren sowie jede Menge zwischen 0 und M: 0 6 Si 6 M. Die Strategiemenge Di = [0, M] ist konvex, weil jede konvexe Kombination zwischen 0 und M, das heisst AM + (1 — λ)0 = AM mit 0 6 λ 6 1, produziert werden kann. Da die Menge nach oben und unten beschränkt ist und 0 und M enthalten sind, ist Di auch kompakt.
Die allgemeine Formulierung und die hohe Abstraktion erlauben es, diese Definition in einer Reihe von Situationen anzuwenden. Ein Spieler kann ein Individuum sein oder eine beliebige andere Entscheidungseinheit, wie zum Beispiel eine Regierung, ein Verwaltungsrat, eine marxistische Revolutionsarmee, ja sogar sogar eine Blume oder ein Tier. Allerdings sind die Anwendungsmöglichkeiten dadurch beschränkt, dass jedem Spieler eine Auszahlungsfunktion zugeordnet werden muss. Als Auszahlungsfunktionen oder Präferenzrelationen können jedoch bereits die einfachen Gefühle eines Spieler bezüglich verschiedener Endzustände oder im Falle eines nicht-menschlichen Organismus die Wahrscheinlichkeit des reproduktiven Erfolgs verwendet werden.
Selbstverständlich bevorzugt Spieler i Strategie Wi1 gegenüber Wis falls
Abbildung in dieser Leseprobe nicht enthalten
bei gegebenen Wja für j = 1, ...,i — 1,i + 1,...,n. Weiters ist es einfach einzusehen, dass ai problemlos auf gemischte Strategien erweitert werden kann. ai ist dann ebenfalls linear in den gemischten Strategien (vlg. Ritzberger, 2003). Abbildung in dieser Leseprobe nicht enthalten
dann ist Abbildung in dieser Leseprobe nicht enthalten
So ein n-Tupel s kann als Punkt in einem Vektorraum angesehen werden - dem Produktraum der Vektorräume, die die gemischten Strategien enthalten. Weiters führen wir die Substitutionsnotation
Abbildung in dieser Leseprobe nicht enthalten
ein. Nachfolgend geben wir mehrere verschiedene Kriterien für ein Gleichgewicht (vgl. Nash, 1951).
Definition 5 (Gleichgewicht) Ein n-Tupel s ist genau dann ein Gleichgewicht von G —< n, (Πί) i2n, (ai)i2n > falls für alle Spieler i gilt:
Abbildung in dieser Leseprobe nicht enthalten
Wenn s — (s1, S2, ..., sn) und Si die pure Strategie nia benutzt, also a¡a > 0, sagen wir, dass s die pure Strategie nia benutzt. Wegen der Linearität von
ai(s1, s2, ..., sn) in si gilt:
Abbildung in dieser Leseprobe nicht enthalten
Definieren wir aia(s) : — ai(s;wia), so ergibt sich trivialerweise folgende notwendige und hinreichende Bedingung, dass s ein Equilibrium ist:
Abbildung in dieser Leseprobe nicht enthalten
Wenn s — (s1, S2, ..., sn) und Si — Σciaría, dann ist afis) —Σciaaia(s). Damit also die Formulierung (3) hält, muss a¡a — 0 sein, falls aia(s) < max(aiß(s)). Dies ist gleichbedeutend zu sagen, dass s die pure Strategie nia nicht benutzt, es sei denn, es handelt sich um eine optimale pure Strategie für Spieler i.Wir schreiben also
Abbildung in dieser Leseprobe nicht enthalten
Es handelt sich um eine weitere notwendige und hinreichende Bedingung für ein Gleichgewicht.
In Worten: Ein Gleichgewicht ist ein n-Tupel s so, dass die gewählte Strategie eines jeden Spielers seine Auszahlung maximiert bei gegebenen Strategien der anderen Spieler. Somit ist jede Strategie der Spieler optimal gegen die Strategien der anderen. Nochmals aus anderer Perspektive formuliert: Ausgehend von einem Equilibrium, besteht für keinen Spieler ein Anreiz, von seiner Gleichgewichtsstrategie abzuweichen. Dieses fundamentale Konzept einer Spiellösung wird heute gemeinhin als Nash-Gleichgewicht, Nash-Equilibrium oder Nash-Lösung bezeichnet.
Eine gleichwertige Definition des Nash-Gleichgewichts, die gewöhnlicherweise in der neueren Literatur angeführt wird, lautet wie folgt:
Definition 6 Abbildung in dieser Leseprobe nicht enthalten ein strategisches Spiel. Wir definieren s-i als die Strategien der Spieler n\i und schreiben dementsprechend auch [Abbildung in dieser Leseprobe nicht enthalten] (Strategieraum ohne Strategien des Spielers i). Weiter sei
Abbildung in dieser Leseprobe nicht enthalten
die Menge der besten Strategien („Funktion der besten Antworten“) von Spieler i bei gegebenen s-i. Ein Nash-Equilibrium ist eine Strategie s* für welche
Abbildung in dieser Leseprobe nicht enthalten
Abbildung in dieser Leseprobe nicht enthalten
Definition (6) gibt eine (nicht notwendigerweise effiziente) Methode ein Nash- Gleichgewicht mit Hilfe der „Funktion der besten Antworten“ zu finden.
Beispiel 7 Wir betrachten zwei identische Unternehmen die ein homogenes Gut produzieren, sich um die Nachfrage konkurrieren und sich ihrer wechselseitigen Beziehung bewusst sind („Cournot-Duopol“). Das Gewinnoptimierungsproblem für i = 1, 2 laute
Abbildung in dieser Leseprobe nicht enthalten
wobei si Ausbringungsmengen4, p(.) die Preisfunktion am Markt und Ci (si) die
[...]
1 Sei D C Rn konvex und f : D C Rn ! R. Wir sagen, dass f quasikonkav ist, falls die Menge fx £ D : f (x) > ag konvex ist für alle a £ R. f ist quasikonvex, falls fx G D : f (x) 6 ag konvex ist für alle a £ R.
2 Anstelle von Auszahlungsfunktionen sprechen manche Autoren (vgl. ÜSBÜRNE UND RuBINSTEIN, 1994) auch von Präferenzrelationen. Präferenzrelationen können als eine Verallgemeinerung von Auszahlungsfunktionen angesehen werden.
3 Die Hauptidee der Einführung gemischter Strategien ist es, die diskreten puren Strategien zu „stetig“ zu machen. RlTZBERGER (2003) erwähnt ebenfalls, dass gemischte Strategien als Wahrscheinlichkeitsverteilungsfunktionen oder Verteilungsfunktion von puren Strategien verstanden werden können.
4 Betrachte Si zum Beispiel als gemischte Strategie der zwei reinen Strategien кц = lim s(p) n - 0 und Ki2 = lim s(p), wobei s(p) := p_1(s). n - -1
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X. -
¡Carge sus propios textos! Gane dinero y un iPhone X.