Game Theory - Cheatsheet

Nash-Gleichgewicht: Definition und mathematische Formulierung

Definition:

Nash-Gleichgewicht ist ein Konzept in der Spieltheorie, bei dem kein Spieler seinen Nutzen durch einseitiger Änderung seiner Strategie verbessern kann.

Details:

• Formal: Ein Strategienprofil \(S^* = (S_1^*, ..., S_n^*)\) ist ein Nash-Gleichgewicht, wenn gilt: \[\forall i \in \{1, ..., n\}: u_i(S_i^*, S_{-i}^*) \geq u_i(S_i, S_{-i}^*) \text{ für alle } S_i \in S_i.\]
• \(u_i\): Nutzenfunktion des Spielers \(i\)
• \(S_i\): Strategie von Spieler \(i\)
• \(S_{-i}\): Strategien aller anderen Spieler außer \(i\)
• Jeder Spieler maximiert seinen Nutzen, vorausgesetzt die anderen Spieler ändern ihre Strategien nicht.

Nash-Gleichgewicht: Methoden zur Ermittlung

Definition:

Nash-Gleichgewicht: Zustand, in dem kein Spieler durch einseitiges Abweichen seinen Nutzen verbessern kann.

Details:

• Beste-Antwort-Methode: Finde jeden Spieler beste Antworten auf Strategien der anderen.
• Iteriertes Entfernen dominierter Strategien: Entferne sukzessive streng dominierte Strategien.
• Graphische Methode: Nutzbar bei 2-Spieler-Spielen; zeichne beste Antworten in Strategieraum.
• Algebraische Methode: Löse Gleichungen von besten Antworten.
• Sequentielle Spiele (Backward Induction): Beginne am Ende des Spiels und arbeite rückwärts.

Strategische Spiele: Darstellung in Normalform

Definition:

Strategische Spiele, auch Matrixspiele genannt, zeigen die möglichen Strategien und Auszahlungen der Spieler in Normalform. Nützlich zur Analyse der besten Antwort und Nash-Gleichgewichte.

Details:

• Spieler: meist Spieler 1 und Spieler 2
• Strategien: Mengen der möglichen Aktionen
• Auszahlungen: Nutzenfunktionen der Spieler
• Normalform (Matrixnotation): für Spieler 1 und Spieler 2 dargestellt
• Beste Antwort: optimale Antwort auf die Strategie des anderen
• Nash-Gleichgewicht: keine einseitige Abweichung führt zu besserer Auszahlung

Kooperative Spiele: Shapley-Wert

Definition:

Shapley-Wert: Verteilung des Gesamtergebnisses eines kooperativen Spiels basierend auf individuellem Beitrag jedes Spielers

Details:

• Nützlich für fairen Gewinn-/Kostenteiler
• Formel: \[ \phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!(n-|S|-1)!}{n!} [v(S \cup \{i\}) - v(S)] \]
• \(v(S)\): Nutzenfunktion für Koalition \(S\)
• Symmetrie, Dummy-Spieler, Effizienz und Additivität als Eigenschaften

Wiederholte Spiele: Folk-Theorem

Definition:

Folk-Theoreme beschreiben die möglichen Gleichgewichte in unendlich oft wiederholten Spielen.

Details:

• In unendlich oft wiederholten Spielen können fast alle möglichen Outcomes als Nash-Gleichgewichte erreicht werden.
• Die Hauptannahme ist, dass die Spieler geduldig sind (Abzinsungsfaktor nahe bei 1).
• Ein Outcome ist durchsetzbar, wenn:
  • Er Pareto-effizient ist.
  • Spieler durch Abweichen nicht besser gestellt werden.
• Formel für den Abzinsungsfaktor: \[\delta = \frac{1}{1+r}\]
• Multiple Gleichgewichte möglich durch strategische Bestrafung und Belohnung.

Bayes'sche Spiele: Umgang mit unvollständiger Information

Definition:

Bayes'sche Spiele behandeln Strategien in Situationen unvollständiger Information, wobei Spieler ihre eigenen Auszahlungen, jedoch nicht die der anderen kennen.

Details:

• Unvollständige Information: Spieler kennen einige Parameter nicht.
• Bayes Nash Gleichgewicht (BNE): Strategisches Gleichgewicht unter Berücksichtigung der Wahrscheinlichkeiten.
• Nützliche Formeln: Erwartungswert, Nutzenmaximierung.
• Spielertypen: Verschiedene Typen beeinflussen Strategien.
• Erwartungswert: \( E(U_i) = \text{Summe der erwarteten Auszahlungen} \sum_j P(t_j|t_i) * U_i(a_i,a_{-i},t_j)\)
• Bayes Nash Gleichgewicht: \( a_i^{*}(t_i) = \text{argmax}_{a_i} E(U_i|t_i, a_{-i})\)

Methoden zur Analyse dominanter Strategien

Definition:

Methode zur Bestimmung von Strategien, die immer besser oder zumindest nicht schlechter sind als alle anderen Strategien in einem Spiel.

Details:

• Dominante Strategie: Eine Strategie, die für jeden möglichen Zug der anderen Spieler besser oder mindestens gleich gut ist.
• Strikt dominierte Strategie: Eine Strategie, die immer schlechter ist als eine andere Strategie des gleichen Spielers.
• Identifikation dominanter Strategien durch Vergleich von Auszahlungen in der Nutzenmatrix.
• Falls alle Spieler dominante Strategien haben, Gleichgewicht durch Wahl dominanter Strategien.
• Eliminierung strikt dominierter Strategien: Wiederholtes Entfernen strikt dominierter Strategien kann verbleibende Strategien klären.

Vergleich von endlichen und unendlichen Wiederholungen in Spielen

Definition:

Vergleich zwischen Spielen mit begrenzter Anzahl an Wiederholungen und solchen mit unbegrenzter Anzahl an Wiederholungen.

Details:

• Endliche Spiele: Spieler wissen, wann das Spiel endet, beeinflusst Strategiewahlen.
• Unendliche Spiele: Spieler wissen nicht, wann (oder ob) das Spiel endet, führt häufig zu „kooperativen Gleichgewichten“ (z.B. Tit-for-Tat in Gefangenendilemma).
• Wichtig: Diskontierungsfaktor \delta, beschreibt den Zeitwert zukünftiger Auszahlungen.
• Endlich: Rückwärtsinduktion zur Bestimmung des Gleichgewichts.
• Unendlich: Folk Theorem beschreibt Bedingungen für multiple Gleichgewichte.