Mathematiker: Nash

Aus Wikiludia
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Leben

John Forbes Nash jun. wurde am 13.06.1928 in West Virginia geboren. Er studierte zunächst in Pittsburgh, bevor er mit dem Titel Master of Science nach Princeton wechselte. 1950 legte er dort seine Dissertation über nichtkooperative Spiele vor. 1951 ging Nash an das ebenfalls hochrenommierte Massachusetts Institute of Technology (MIT). 1957 nahm John Nash Alicia Larde, eine Physikerin vom MIT, zu seiner Frau. Anfang des Jahres 1959, als seine Frau Alicia schwanger war, begann Nashs geistige Verwirrung. Die Diagnose der behandelnden Ärzte lautete paranoide Schizophrenie. Nash gab in Folge dessen seine Position als Mitglied einer Fakultät am MIT auf und wurde gegen seinen Willen mehrmals in die Nervenklinik eingewiesen. Seine Krankheit konnte Nash jedoch nicht davon abbringen, sich mathematisch zu betätigen. Wann immer seine Situation es zuließ, wandte er sich der Mathematik zu und erreichte respektable Forschungsergebnisse.


Errungenschaften

  • Im Jahr 1994 erhielt Nash zusammen mit John Harsanyi und Reinhard Selten den Preis der schwedischen Reichsbank für Wirtschaftswissenschaften in Gedenken an Alfred Nobel.
  • Unterscheidung in kooperative und nichtkooperative Spiele
„The distinction between cooperative and non-cooperative games is unrelated to the mathematical description by means of pure strategies and pay-off functions of a game. Rather it depends on the possibility or impossibility of coalitions, communication, and side-payments.”
Ein Nash-Gleichgewicht in einem Spiel ist eine (gemeinsame) Strategie aus der Strategiemenge S:
s* = (s1*,...,sn*) ∈ S.
Sie ist dahingehend optimal, dass es sich für keinen der beteiligten Spieler i lohnt, von seiner Individualstrategie si* abzuweichen, wenn alle anderen Spieler an ihrer Wahl sj* festhalten.
Die Nash-Verhandlungslösung für kooperative Spiele beschreibt, wie Verhandlungspartner einen Mehrgewinn aufteilen können, den sie gemeinsam erwirtschaften.


Betrachtet man gemischte Strategien, so nimmt man an, dass jeder Spieler k seine reinen Strategien s1, s2,…, sn(k) kombinieren kann. Dazu ordnet man den reinen Strategien dieses Spielers Gewichte p1,…, pn(k) zu, wobei 0 ≤ pi ≤ 1 und ∑i (pi) = 1, i ∈ {1,…,n(k)} gelten muss. Dann bildet man für diesen Spieler eine neue Strategie, die sich aus den gewichteten reinen Strategien additiv zusammensetzt und somit seine Präferenzen bezüglich den vorhandenen reinen Strategien ausdrückt:
sk = p1*s1 + p2*s2 + … + pn(k)*sn(k)
Wenn die einzelnen reinen Strategien eines Spielers k komplementär zueinander sind, so kann man sich vorstellen, dass das Spiel endlich oft wiederholt wird und die Gewichte die relativen Häufigkeiten darstellen, mit denen sich k für die entsprechenden reinen Strategien entscheidet.
  • Nash lieferte den Beweis, dass abstrakte Riemannsche Mannigfaltigkeiten in euklidische Räume isometrisch eingebettet werden können.
  • Einführung der statischen Interpretation
In statischen Spielen kommen die Spieler nicht durch einen Abfolge eingeschränkt rationaler Überlegungen, also in mehreren Schritten, zur rationalen Lösung, sondern springen direkt dorthin.
Dementsprechend setzt man bei der statischen Interpretation des Nash-Gleichgewichts voraus, dass alle Spieler die gleichen Rationalitätsziele verfolgen, durch die sie unabhängig voneinander ein Nash-Gleichgewicht als gemeinsame optimale Lösung für das Spiel erkennen. Wenn mehrere Nash-Gleichgewichte existieren, so ist a priori jedoch nicht klar, welches Nash-Gleichgewicht gewählt wird.


  • Entwicklung und eingehende Analyse eines topologischen 2-Personen-Spiels, das in Princeton unter dem Namen "Nash" oder auch "John" bekannt wurde.

Unabhängig von Nashs Arbeit wurde dieses Spiel jedoch bereits einige Jahre zuvor von dem Dänen Piet Hein unter dem Namen Hex veröffentlicht.

Dissertation John Nashs zum Thema: Non-cooperative Games

  • Umfang: 32 Seiten
  • Abgabe im Mai 1950
Nash würdigt in seiner Einführung die Arbeit von Morgensterns und von Neumanns.
Er stellt jedoch heraus, dass in seiner Arbeit im Gegensatz zu deren Ansatz jegliche Art der Koalitionsbildung ausgeschlossen ist. Die Spieler handeln unabhängig voneinander, ohne jegliche Form von Zusammenarbeit oder Kommunikation. Es gibt außerdem keine Ausgleichszahlungen, also Beträge, die einer Person aus dem eigenen Etat zugewiesen werden, um diese zur Annahme der Gemeinschaftslösung zu bewegen.


Definitionen

  • Ein endliches (n-Personen) Spiel besteht aus einer Menge von n Spielern/Positionen, jeweils mit einer endlichen Menge an reinen Strategien ∏iα mit einer zugehörigen Auszahlungsfunktion Pi, für jeden Spieler, i Є {1,…, n}, die jeder Kombination aus reinen Stategien der einzelnen Spieler ein reelle Zahl zuordnet.


  • eine gemischte Strategie des Spielers i ist eine Menge von nichtnegativen Zahlen, die sich zu 1 aufaddieren und in bijektiver Beziehung zu den reinen Strategien dieses Spielers stehen:


si = ∑α ( c * ∏ ) = c *∏ + c* ∏ + c *∏ + … mit ∑α (c) = 1 und c ≥ 0.


Die si können als Punkte in einem Simplex verstanden werden, dessen Eckpunkte durch die ∏ repräsentiert werden. Dieses Simplex kann als konvexe Teilmenge eines reellen Vektorraumes angesehen werden, wodurch die Linearkombination von reinen Strategien zu gemischten Strategien ersichtlich wird.


  • Die Auszahlungsfunktion Pi besitzt eine eindeutige Fortsetzung auf das konvexe Polytop, das von den n-Tupeln der gemischten Strategien aufgespannt wird; sie ist n-linear.


  • Sei ς = (s1, … , sn) ein n-Tupel, bestehend aus gemischten Strategien der einzelnen Spieler, also eine (Gesamt-)Strategie. Dann definiert (ς; ti) die Strategie, die durch das Ersetzen der i-ten Komponente von ς mit der gemischten Strategie ti erzeugt wird:


(ς; ti) = (s1,…, si-1, ti, si+1, …, sn)


  • Ein n-Tupel ς ist g.d. ein Gleichgewichtspunkt, wenn für alle i aus {1,…, n} gilt:


Pi(ς)= max { Pi(ς; ri), ri Є si für i=1,…,n}


Somit stellt ein Gleichgewicht ein n-Tupel dar, bei dem für jeden einzelnen Spieler dessen Auszahlung maximiert wird unter der Voraussetzung, dass alle anderen Spieler ihre Strategien beibehalten. In diesem Punkt ist die Strategie jedes Spielers bezüglich der Strategien der Gegner optimal.


  • Eine gemischte Strategie si benutzt eine reine Strategie ∏, wenn gilt:
si = ∑α ( c * ∏ ) und c > 0.
Dies kann man auf die Gesamtstrategien, also die n-Tupel ς ausweiten: benutzt si die Strategie ∏, so tut dies auch ς.


Existenz von Gleichgewichtspunkten

Theorem:

Jedes endliche (nichtkooperative) Spiel hat (mindestens) einen Gleichgewichtspunkt


Beweis:

ς sei ein Tupel gemischter Strategien und P(ς) sei die Auszahlung an Spieler i, wenn dieser die reine Strategie ∏ wählt und die anderen Spieler ihre entsprechenden Strategien aus ς benutzen. Für jede ganze Zahl λ wird eine stetige Funktion von ς definiert:

qi(ς) = maxα {P(ς)},
Φ (ς, λ) = P(ς) - qi(ς) + 1/λ,
Φ+ = max{0, Φ (ς, λ)} (Positivteil von Φ)


Setze fα = ∑α Φ+

Es gilt:

α Φ+ ≥ maxα+} = 1/λ > 0, so dass
C'(ς,λ) = Φ+(ς,λ) / f β stetig ist.


Definiere:

s'i(ς,λ) = ∑α * C'(ς,λ) und ς'(ς,λ) = ( s'1, s'2, .., s'n).


Weil alle Operationen die Stetigkeit erhalten, ist die Abbildung ς → ς'(ς,λ) stetig. Da der Raum der n-Tupel ς eine topologische Zelle ist, muss damit für jedes λ ein Fixpunkt existieren.

Somit gibt es eine Teilfolge ςμ, die gegen ς* konvergiert, wobei ςμ unter der Abbildung ς → ς'(ς,λ (μ) ) festgehalten wird.


Angenommen, ς* sei kein Gleichgewichtspunkt.

Dann muss für ς* = (s1*, ...,sn*) mindestens eine Komponente si* nicht-optimal im Vergleich zu anderen Strategien des Spielers i sein. Damit verwendet si* eine reine Strategie ∏, die nicht-optimal ist. Das bedeutet, dass

P(ς*) < qi(ς*) und damit P(ς*) - qi(ς*) < -ε


Wenn μ groß genug gewählt wird, folgt aus der Stetigkeit:

|[ Pμ) - qiμ)] - P(ς*) - qi(ς*)] | < ε/2 und 1/λμ < ε/2.

Außerdem:

Pμ) - qiμ) + 1/λμ < 0, was gleichbedeutend ist mit
Φμ), λ(μ)) < 0 mit Φ+μ,λ(μ)} = 0 genau dann, wenn C'(ςμ, λ(μ)) = 0.


Aus dieser letzten Gleichung wird ersichtlich, dass ∏ nicht in ςμ benutzt wird, da ja ςμ = ∑α * C'(ςμ, λ(μ) ) gilt, weil ςμ ein Fixpunkt ist.

Damit gilt außerdem ςμ → ς*.

Aber ∏ wird in der Strategie ς* nicht benutzt- Widerspruch!

Damit ist ς* ein Gleichgewichtspunkt. q.e.d.

Symmetrie von Spielen

  • Ein Automorphismus oder eine Symmetrie eines Spiels sei eine Permutation seiner reinen Strategien, wobei gelte:
  • Befinden sich mehrere Strategien in der Strategiemenge eines einzelnen Spielers, so sind diese nach der Permutation wieder gemeinsam in der Strategiemenge eines Spielers. Also werden die n gesamten Mengen der reinen Strategien der einzelnen Spieler vertauscht. Somit wird durch eine solche Permutation Φ der reinen Strategien eine Permutation Ψ der n Spieler induziert.
  • Sei ξ ein n-Tupel von reinen (Einzel-) Strategien und χ die entsprechende Permutation auf diesen Tupeln; sei außerdem Pi(ξ) die Auszahlung an Spieler i, wenn die Spieler die Strategie ξ umsetzen. Dann kann man fordern, dass aus j= iΨ folgt: Pjχ )= Pi (ξ).
  • Ein symmetrisches n-Tupel ς eines Spieles ist gegeben, wenn für alle aus Symmetrien abgeleiteten Permutationen gilt, dass ςχ = ς.


  • Beweis, dass jedes endliche Spiel einen symmetrischen Gleichgewichtspunkt besitzt.

Gegeben:  s_{i0} = \frac {\sum_{\alpha}\pi_{i\alpha}}{\sum_{\alpha}1} mit  s_{i0}^\phi = s_{j0} mit j = iθ, für ein bestimmtes n-Tupel s0 = (s10,s20,...,sn0).

Daraus folgt, dass jedes Spiel mindestens ein symmetrisches n-Tupel hat.

Falls s = (s1,...,sn) und t = (t1,...,tn) symmetrisch sind, dann ist  \frac {s+t}{2} = (\frac{s_{1}+t_{1}}{2}, \frac {s_{2}+t_{2}}{2}, ..., \frac {s_{n}+t_{n}}{2}) auch symmetrisch weils^\chi = s \Longleftrightarrow s_{j} = s_{i}^\phi , mit j = iθ.

Folglich ist  \frac {s_{j}+t_{j}}{2} = \frac{s_{i}^\phi + t_{i}^\phi}{2} = (\frac {s_{i} + t_{i}}{2})^\phi und es gilt  (\frac{s+t}{2})^\chi = \frac {s+t}{2} .

Dies zeigt, dass die kompakte Menge der symmetrischen n-Tupel eine konvexe Untermenge von dem n-Tupel-Raum ist.

Sei die Abbildung  T: s\rightarrow s* . Mit s2 = Ts1 gilt  s_{2}^\chi = Ts_{1}^\chi . Wenn s1 symmetrisch ist, also  s_{1}^\chi = s_{1} dann gilt  s_{2}^\chi = Ts_{1} = s_{2} .

Folglich bildet diese Abbildung T die Menge der symmetrischen n-Tupel auf sich selbst ab.

Da diese Menge ein Element ist, muss es einen symmetrischen Fixpunkt s geben, welches ein symmetrisches GG sein muss.

Lösbarkeit von Spielen

  • Austauschbarkeitsbedingung: Si bezeichne eine Menge gemischter Strategien des Spielers i, ri Є Si.
Ein Spiel ist lösbar, wenn seine Menge von Gleichgewichtspunkten Θ die Bedingung (t; ri) Є Θ und ς Є Θ => (ς; ri) Є Θ für alle i aus {1,…, n} erfüllt. In diesem Sinne ist ein 2-Personen-Nullsummenspiel immer lösbar.


  • Die Lösung eines lösbaren Spiels ist dessen Menge Θ von Gleichgewichtspunkten.


  • Ein Spiel wird streng lösbar (strongly solvable)genannt, wenn es eine Lösung Θ besitzt, so dass für alle i Є {1,…,n} gilt: (ς Є Θ und Pi(ς; ri) = Pi(ς)) => (ς; ri) Є Θ. Dann ist Θ die strenge Lösung des Spiels. In einem lösbaren Spiel sei Si die Menge aller gemischten Strategien si des Spielers i, für die es jeweils eine (Gesamt-) Strategie t gibt, sodass das n-Tupel (t; si) einen Gleichgewichtspunkt darstellt. Dann wird Si als Menge der Gleichgewichtsstrategien des Spielers i bezeichnet. Strenge Lösungen existieren nur, wenn es einen Sattelpunkt in reinen Strategien gibt.


  • Wenn Θ eine Teilmenge der Menge der Gleichgewichtspunkte ist, die Bedingung (t; ri) Є Θ und ς Є Θ => (ς; ri) Є Θ für alle i aus {1,…, n} erfüllt und bezüglich dieser Eigenschaft maximal ist, dann wird Θ als Unter-Lösung (sub-solution)bezeichnet.
Für jede Unter-Lösung Θ definiert man die i-te Faktormenge (factor set) Si als die Menge aller si, für die es Strategien t gibt, so dass (t; si) in Θ liegt.
Wenn eine Unter-Lösung eindeutig ist, dann ist sie eine Lösung.


Satz:

Eine Unter-Lösung θ , ist die Menge aller n-Tupel (s_1, s_2,\ldots,s_n), s. d jedes s_i \in S_i, wobei Si die i-te Faktormenge von θ ist. Geometrisch ist θ das Produkt seiner Faktormengen.


Beweis:

Sei das n-Tupel (s_1,\ldots, s_n). Laut Definition existiertt_1, t_2,\ldots, t_n s. d. jedesi(t_i; s_i)\in\theta. Mit Hilfe der Austauschbarkeitsbedingung bekommen wir (t_1; s_1)\in \theta, (t_1; s_1; s_2)\in\theta,..., (t_1; s_1; s_2;\ldots; s_n)\in\theta und als letztes(s_1, s_2,\ldots, s_n)\in\theta, was zu zeigen war.


Satz:

Die Faktormengen S_1, S_2,\ldots, S_n einer Unter-Lösung sind abgeschlossen und konvex als Untermengen der Räume der gemischten Strategien.


Beweis:

Es genügt 2 Sachen zu zeigen:

(a) Wenn si und s_i\!\,'\in S_i dann s_i\!\,*=\frac{(s_i+s_i\!\,')}{2}\in S_i

(b) Wenn s_i\!\,** ein Grenzpunkt von Si ist, dann s_i\!\,** \in S_i.


Zu (a):

Sei t\in \theta . Dann haben wir p_j(t; s_i) \geq p_j(t; s_i; r_j) und p_j(t; s_i\!\,') \geq p_j(t; s_i\!\,'; r_j) für jedes rj. Wir benutzen hier folgendes Kriterium für ein GG-Punkt: p_i(s)=\max_{r_i}[p_i(s; r_i)], s sei ein n-Tupel. Durch Addieren dieser Ungleichungen, durch die Linearität von  p_j(s_1,\ldots,s_n) in si, und Teilen durch 2, bekommen wir p_j(t; s_i\!\,*)\geq p_j(t; s_i\!\,*; r_j), mit s_i\!\,*=\frac {s_i+s_i\!\,'}{2}. Daraus folgt, dass(t;si) ein Gleichgewichtspunkt für jedes t \in \theta ist. Wenn wir die Menge aller solchen Gleichgewichte (t; s_i\!\,*) mit θ addieren, dann bemerken wir, dass die vergrößerte Menge die Austauschbarkeitsbedingung erfüllt. θ ist eigentlich maximal, folglich gilts_i\!\,* \in S_i .


Zu (b):

Wir wissen s_i\!\,** ist ein Grenzpunkt von Si. Deshalb ist das n-Tupel (t; s_i\!\,**), mit t \in \theta, ein Grenzpunkt der Menge aller n-Tupel der Form (t;si), mit s_i \in S_i. Da diese Menge eine Menge der Gleichgewichtspunkte ist, folgt dass jeder Punkt ein GG-Punkt ist, falls die Menge abgeschlossen ist. Abschließend ist (t; s_i\!\,**) ein GG-Punkt, d. h. s_i\!\,** \in S_i aus demselben Grund wie beim s_i\!\,*.

Der Wert eines Spiels

Sei Θ die Menge der Gleichgewichtspunkte eines Spiels. Man definiert

vi+ = max ς ∈ Θ( Pi(ς) ) und
vi- = minς ∈ Θ( Pi(ς) )


Wenn vi+ = vi- gilt, dann schreibt man: vi = vi+ = vi-

vi+ ( bzw. vi-) wird als oberer (bzw. unterer) Wert des Spiels für den Spieler i bezeichnet.

Wenn vi existiert, so definiert es den Wert des Spiels für den Spieler i. Wenn es nur einen Gleichgewichtspunkt gibt, so existieren diese Werte für die einzelnen Spieler.

Dominanz

Man sagt, dass si` die Strategie si dominiert, wenn für alle t gilt: pi(t; si) > pi(t; si). Dies bedeutet, dass die Wahl von si` dem Spieler i eine höhere Auszahlung generiert als si; und das unabhängig davon, welche Strategien die anderen Spieler wählen. Offensichtlich kann ein Gleichgewichtspunkt keine dominierte Strategie enthalten. Folglich können bei der Suche nach Gleichgewichtspunkten alle dominierten Strategien gestrichen werden.


Anwendung der Theorie, Resümee

  • Nash erkennt, dass es in Wirtschaft und Politik durchaus vorkommen kann, dass Einzelinteressen unbemerkt in nicht-kooperative Spiele einwirken, beispielsweise durch die Arbeit von Interessensgruppen und Lobbyarbeit.
  • Als Anwendungsgebiete seiner Theorie nennt Nash n-Personen Spiele, in denen der Grundsatz des fair-play eine nicht-kooperative Spielweise bedingt.

Seine konkreten Thesen illustriert Nash am Beispiel des 3-Personen-Pokerspiels.

  • Außerdem erläutert er die Möglichkeit, kooperative Spiele in nicht-kooperative Form überzuführen. Dazu wählt man eine dynamische Betrachtung des Spiels und entwickelt für die Verhandlungen vor Spielbeginn ein geeignetes Modell, das in das Spiel einfließt und zu einem umfassenderen nicht-kooperativen Spiel führt, das dann die Gesamtsituation widerspiegelt.

Die Analyse eines kooperativen Spiels entspricht somit der Suche nach einem geeigneten Modell für die Verhandlungen und einer abschließenden Untersuchung des entstehenden nicht-kooperativen Spiels.


Quellen

Artikel

  • Nash1951

Bücher

  • Kuhn2002
  • Nasar1998
  • Siegfried2006
  • Frängsmyr1995
Meine Werkzeuge