Grundlagen Spieltheorie

Erstmal mach dich nochmal mit dem Strategiebegriff vertraut, ein Gleichgewicht bezieht sich immer auf Strategien. Diese Teilen jedem Knoten eine Aktion zu, die Strategie für Spieler 1 besteht also aus 3 Elementen. Somit ist keines deiner Vorgestellten Gleichgewichte überhaupt eines.

Jetzt aber zum Finden der Gleichgewichte. Zunächst die normalen Nashggw., dazu bringst du das ganze erstmal in die nicht-extensive Form und stellst alle Strategie-Kombinationen gegenüber und "spielst" sie durch um die jeweiligen Nutzen zu bekommen. Dann kannst du ganz normal rangehen und Nashggw suchen.

Aber Spieler 2 kann doch zunächst auswählen, ob er X oder Y wählt. Wenn er die Auszahlungen kennt (davon muss ich bei solchen Spielen doch ausgehen, oder?) sollte er doch einfach die Strategie Y spielen und demnach Spieler 1 dazu zwingen D zu spielen. Denn die Auszahlung 5 wäre ja immer noch besser als 0 für beide?

Das hier ist widerum genau die Logik die hinter den Teilspielperfekten steckt. Du löst quasi von hinten auf, jedes Teilspiel nacheinander. In deinem Beispiel musst du das ganze noch weiterspinnen, denn gegeben das Spieler zwei ja Y wählen wird, wird Spieler 1 nicht B wählen wollen, womit das (einzige) teilspielperfekte Gleichgewicht [(A,C,D),Y]
zustande kommt.
Warum Teilspielperfektheit? Das von dir vorgeschlagene Gleichgewicht [(B,C,C),X] hat folgendes Problem: Spieler 2 spielt X weil er denkt wenn er Y spielt, spielt Spieler 1 C. Wenn es aber im Spiel wirklich dazu käme das Spieler 2 Y wählt, würde Spieler 1 dann immernoch C spielen?
Das ist auch der Grund warum du auch für die Knoten die nie erreicht werden eine Aktion festlegen musst, da sie dennoch eine wichtige Rolle im Gleichgewicht spielen und andere Aktionen sozusagen erfordern.

Hmmm meine Musterlösung sagt das andersherum.

Zunächst werden die Gleichgewichte so aufgeschrieben wie ich es gemacht habe, zudem wird das zweite Gleichgewicht als unplausibel bezeichnet.
Genauer gesagt, in der Lösung wird "D" für Spieler 1 als unplausibel genannt.

Gibt es vielleicht mehrere Möglichkeiten GG aufzuschreiben?
Oder ist die Lösung von mir definitiv falsch?

Ist meine Übertragung in die Normalform denn richtig? Da kann man ja auch sofort die NGG herauslesen. Aber in der Baumform fällt es mir total schwer (wie macht ihr das denn? könnt ihr das sofort aus der Extensivform ablesen?)

Also Matzes Lösung kann keinen Sinn machen, da er z.T. von einem Informationset (zweite Möglichkeit von Spieler 1) auf zwei actions mapt, was per Konstruktion nicht möglich ist.

Ein Gleichgewicht ist immer ein Profil aus Strategien. Eine Strategie für einen Spieler umfasst ein vollständiges Mapping für alle seine Informationsets. D.h. eine Strategie für Spieler 1 beinhaltet immer eine Strategie für die root (1. node) und für das Informationset nach Spieler 2s Aktion.

Teilspielperfektheit heißt, dass für jedes subgame ein NE gespielt werden muss. Das Spiel hat zwei subgames: ein proper subgame (nachdem Spieler 1 B gespielt hat/hätte) und das Spiel als solches. Solche GG findest du immer per backwards induction, d.h. du fängst beim Baum von hinten an und gehst schrittweise zur root zurück. Sei h das informationset von Spieler 1 nachdem Spieler 2 gezogen hat:

1. Fall: Spieler 1 spielt C an seinem zweiten Informationset (h):
-> X strictly dominates Y, gegeben dass Spieler zwei an den Zug kommt. Wenn Spieler 2 spielt, würde Spieler 1 auch weiterhin X spielen wollen --> NE im Subgame.
Gegeben s2 = X und s1(h) = C. Dann ist der Payoff von Spieler 1 15 > 12 --> Spieler 1 wählt B. => s1 = (B,C) s2 = X. Fertig und subgame perfect.

2. Fall Spieler 1 spielt D --> Y > X für Spieler zwei. Gegeben das Spieler zwei Y spielt würde 1 auch weiterhin D spielen. => NE im subgame. Gegeben s2 = Y und s1(h) = D würde Spieler 1 an der root A spiele (12 > 5). => s1 =(A,D) s2 = Y. Auch subgame perfect, da NE für beide subgames.

3. Fall Spieler 1 ist indifferent zwischen C und D. Da ist nur der Fall wenn Spieler 2 X mit Prb(s2 = x) = 1/4 ist. D.h. zwei muss auch indifferent sein: Sein Payoff für X und Y ist nur gleich wenn Prb(s1 = C |h) = 3/4. => Mixed strategie eq. für das das subgame mit s1(h) = (3/4, 1/4) und s2 = (1/4, 3/4); Der Payoff für beide Spieler, gegeben dass das subgame erreicht wird, ist 15/4. Daher bevorzugt Spieler 1 an der root A. => equilibrium ist s1 = (A,(3/4, 1/4)) s2 = (1/4,3/4). Auch subgame perfect.

4. Fall: s1 =(A,C) s2 = Y. Betrachte unilaterale Abweichungen: Payoff für Spieler 2 ist immer 12, d.h. er würde nicht abweichen. s1 könnte auf (A,D) payoff = 12 oder (B,C) payoff = 0 oder (B,D) payoff = 5 abweichen, was alles <= 12, daher ist ein NE. Warum es nicht subgame perfect ist: Gegeben dass Spieler zwei tatsächlich zum Zuge kommt und Y spielt, würde 1 auf jeden Fall D spielen wollen. Daher ist es nicht subgame perfect, aber dennoch ein Nash Equilibrium.

Das sollten aus dem Stegreif alle sein.

MfG,
Manti

Du sprichst hier von Information. Ich bin mir nicht sicher, ob OP das so klar ist, bzw. das so gemeint ist. Bei uns hätte ich die Darstellung allerdings auch so interpretiert.

Danke für die ausführliche Antwort! ♠_thumbsup:

Habe jetzt eine neue Frage und den Threadtitel mal bearbeitet.

Original von Fireandice23
Hi

Kann mir jemand das Fundamentallemma und das Folktheorem verständlich mit einem kleinen Beispiel erklären?

Fundamentallemma: Eine gemischte Strategie ist nur dann optimal, wenn jede mit positiver WSK gewählte reine Strategie ebenfalls optimal ist.

Hat jemand dafür ein Beispiel?

Fundamentallemma dürfte wohl dem SMIF (Single most important fact) (Wo wird Game Theory eigentlich noch in deutsch gelehrt?) entsprechen:
Stell dir einfach vor, du hast zwei Aktionen zwischen denen du randomisierst: Du würdest ja nur randomisieren, wenn du indifferent zwischen den beiden bist, anonsten würde es ja einen höheren payoff versprechen, auf die bessere Alternative auszuweichen. D.h. die mixed strategie wird nur gespielt, wenn es keine pure stratgey gibt, die einen höheren payoff verspricht UND du indifferent zwischen den Aktionen bist, d.h. beide müssten als reine Strategie ebenfalls optimal sein.
Bsp.: (symmetrisches) Schere Stein Papier. Das unique mixed str. equilibrium ist, dass beide Spieler mit 1/3 Wahrscheinlichkeit Schere, Stein oder Papier spielen. Gegeben dieser Strategie deines Gegners, ist jede deiner drei möglichen pure Strategies optimal.

Folk Theorems gibt es ziemlich viele. Welches genau meinst du denn? Allgemein sagen alle für unterschiedliche Fälle, dass es für ein unendlich oft wiederholtes Spiel möglich ist, eine discountrate zu finden, sodass der durchschnittliche payoff gegenüber dem NE des stage games für beide schwach verbessert werden kann. (Manchmal in Form konvexer Kominationen aus payoff vectoren, manchmal in Form von anderen stageoutcomes, etc.)
Bsp.: Gefangenendilemma in unendlicher Wiederholung.

Original von Mantikorrrr

Original von Fireandice23
Hi

Kann mir jemand das Fundamentallemma und das Folktheorem verständlich mit einem kleinen Beispiel erklären?

Fundamentallemma: Eine gemischte Strategie ist nur dann optimal, wenn jede mit positiver WSK gewählte reine Strategie ebenfalls optimal ist.

Hat jemand dafür ein Beispiel?

Fundamentallemma dürfte wohl dem SMIF (Single most important fact) (Wo wird Game Theory eigentlich noch in deutsch gelehrt?) entsprechen:
Stell dir einfach vor, du hast zwei Aktionen zwischen denen du randomisierst: Du würdest ja nur randomisieren, wenn du indifferent zwischen den beiden bist, anonsten würde es ja einen höheren payoff versprechen, auf die bessere Alternative auszuweichen. D.h. die mixed strategie wird nur gespielt, wenn es keine pure stratgey gibt, die einen höheren payoff verspricht UND du indifferent zwischen den Aktionen bist, d.h. beide müssten als reine Strategie ebenfalls optimal sein.
Bsp.: (symmetrisches) Schere Stein Papier. Das unique mixed str. equilibrium ist, dass beide Spieler mit 1/3 Wahrscheinlichkeit Schere, Stein oder Papier spielen. Gegeben dieser Strategie deines Gegners, ist jede deiner drei möglichen pure Strategies optimal.

Folk Theorems gibt es ziemlich viele. Welches genau meinst du denn? Allgemein sagen alle für unterschiedliche Fälle, dass es für ein unendlich oft wiederholtes Spiel möglich ist, eine discountrate zu finden, sodass der durchschnittliche payoff gegenüber dem NE des stage games für beide schwach verbessert werden kann. (Manchmal in Form konvexer Kominationen aus payoff vectoren, manchmal in Form von anderen stageoutcomes, etc.)
Bsp.: Gefangenendilemma in unendlicher Wiederholung.

Uni Essen. Wird das sonst immer in englisch gelehrt? Vielleicht wird es bei uns in deutsch gemacht, weil unser Prof. ein Buch geschrieben hat und es mehr oder weniger als Pflichtlektüre eingeführt hat und kein Skript zur Verfügung stellt :evil:. Blöd wenn man dann zu Beginn des Semesters das Fach als trivial einstuft und nicht mehr hingeht und kurz vor der Klausur erst feststellt wie umfangreich das doch alles ist und jetzt bei einfachen Dingen schon Probleme hat.

Ich habe hier noch ein "Spiel", wo man kein reines Gleichgewicht finden kann.
Spieler 1: Finanzamt
Spieler 2: Steuerzahler

Strategien Sp1: Vertrauen, Kontrolle
Strategien Sp2: Ehrlich, Unehrlich

Hier gibt es ja auch keine pure Strategie und somit kein NGG.
Wenn ich das gemischte Gleichgewicht berechne, erhalte ich folgende Wahrscheinlichkeiten:
Vertrauen: 50%
Kontrolle: 50%

Ehrlich: 80%
Unehrlich: 20%

Hier handelt es sich ja nicht um ein symmetrisches Spiel. Kann man hier trotzdem Bezug auf das Fundamentallemma nehmen?

Vielen Dank!

Also erst einmal ist ein NGG in mixed strategies auch ein NGG. Geben tut es hier pure strategies schon, aber sie sind nicht in der Schnittmenge der Best-Responses beider Spieler enthalten.
Den SMIF benutzt du bereits implizit zum Lösen des Spiels, das hat generell nichts mit Symmetrie zu tun.

Original von Fireandice23
Hmmm meine Musterlösung sagt das andersherum.

Ja obv. Informationsmenge übersehen.

Ist meine Übertragung in die Normalform denn richtig? Da kann man ja auch sofort die NGG herauslesen. Aber in der Baumform fällt es mir total schwer (wie macht ihr das denn? könnt ihr das sofort aus der Extensivform ablesen?)

Spoiler

Das ist falsch, du musst die Spielergebnisse abtragen, wo kommt bspw. dein (12,5) her?
Dann kannst dus auch ganz schnell nach NGG lösen und kommst auf die von Mantikorrr (bis auf Fall 3)

Original von Mantikorr
4. Fall:

Wenn du Fall 3 als Lösung zulässt, also das er mischt, bekommst du hier nach der Logik von Fall 4, doch im Grunde unendlich viele weitere NGG, oder?

Original von pmatze

Original von Fireandice23
Hmmm meine Musterlösung sagt das andersherum.

Ja obv. Informationsmenge übersehen.

Ist meine Übertragung in die Normalform denn richtig? Da kann man ja auch sofort die NGG herauslesen. Aber in der Baumform fällt es mir total schwer (wie macht ihr das denn? könnt ihr das sofort aus der Extensivform ablesen?)

Spoiler

Das ist falsch, du musst die Spielergebnisse abtragen, wo kommt bspw. dein (12,5) her?
Dann kannst dus auch ganz schnell nach NGG lösen und kommst auf die von Mantikorrr (bis auf Fall 3)

Original von Mantikorr
4. Fall:

Wenn du Fall 3 als Lösung zulässt, also das er mischt, bekommst du hier nach der Logik von Fall 4, doch im Grunde unendlich viele weitere NGG, oder?

Die 12,5 dachte ich kommen so zusammen:
Spieler 1 spielt A,C und Spieler 2 X. Demnach erhält Spieler 1 12 aus A und Spieler 2 erhält 5 durch X und Entscheidung C von 1.
Ist das nicht richtig?

Original von Fireandice23

Original von pmatze

Original von Fireandice23
Hmmm meine Musterlösung sagt das andersherum.

Ja obv. Informationsmenge übersehen.

Ist meine Übertragung in die Normalform denn richtig? Da kann man ja auch sofort die NGG herauslesen. Aber in der Baumform fällt es mir total schwer (wie macht ihr das denn? könnt ihr das sofort aus der Extensivform ablesen?)

Spoiler

Das ist falsch, du musst die Spielergebnisse abtragen, wo kommt bspw. dein (12,5) her?
Dann kannst dus auch ganz schnell nach NGG lösen und kommst auf die von Mantikorrr (bis auf Fall 3)

Original von Mantikorr
4. Fall:

Wenn du Fall 3 als Lösung zulässt, also das er mischt, bekommst du hier nach der Logik von Fall 4, doch im Grunde unendlich viele weitere NGG, oder?

Die 12,5 dachte ich kommen so zusammen:
Spieler 1 spielt A,C und Spieler 2 X. Demnach erhält Spieler 1 12 aus A und Spieler 2 erhält 5 durch X und Entscheidung C von 1.
Ist das nicht richtig?

Nein, so funktioniert das nicht, spielt Spieler 1 A ist das Spiel vorbei und beide erhalten 12. Das X und C spielen also auf den ersten Blick keine Rolle, weil es ja nie dazu kommt, aber um zu wissen ob A oder B besser ist, muss Spieler 1 wissen was passieren würde wenn er denn B wählt. Deshalb müssen Strategien immer zu jeder Entscheidungsmöglichkeit die theoretisch im Spiel erreicht werden könnte (auch wenn sie bspw durch eine vorherige Aktion quasi ausgeschlossen werden) eine Aussage, bezüglich der aktion die gespielt wird, treffen.

Original von pmatze

Original von Fireandice23

Original von pmatze

Original von Fireandice23
Hmmm meine Musterlösung sagt das andersherum.

Ja obv. Informationsmenge übersehen.

Ist meine Übertragung in die Normalform denn richtig? Da kann man ja auch sofort die NGG herauslesen. Aber in der Baumform fällt es mir total schwer (wie macht ihr das denn? könnt ihr das sofort aus der Extensivform ablesen?)

Spoiler

Das ist falsch, du musst die Spielergebnisse abtragen, wo kommt bspw. dein (12,5) her?
Dann kannst dus auch ganz schnell nach NGG lösen und kommst auf die von Mantikorrr (bis auf Fall 3)

Original von Mantikorr
4. Fall:

Wenn du Fall 3 als Lösung zulässt, also das er mischt, bekommst du hier nach der Logik von Fall 4, doch im Grunde unendlich viele weitere NGG, oder?

Die 12,5 dachte ich kommen so zusammen:
Spieler 1 spielt A,C und Spieler 2 X. Demnach erhält Spieler 1 12 aus A und Spieler 2 erhält 5 durch X und Entscheidung C von 1.
Ist das nicht richtig?

Nein, so funktioniert das nicht, spielt Spieler 1 A ist das Spiel vorbei und beide erhalten 12. Das X und C spielen also auf den ersten Blick keine Rolle, weil es ja nie dazu kommt, aber um zu wissen ob A oder B besser ist, muss Spieler 1 wissen was passieren würde wenn er denn B wählt. Deshalb müssen Strategien immer zu jeder Entscheidungsmöglichkeit die theoretisch im Spiel erreicht werden könnte (auch wenn sie bspw durch eine vorherige Aktion quasi ausgeschlossen werden) eine Aussage, bezüglich der aktion die gespielt wird, treffen.

Oh man, wieso fällt mir das so schwer. Ich habe da irgendwie ein Brett vor dem Kopf.

Nochmal langsam und von vorne.
Spieler 1 hat folgende reine Strategien:
(A,C), (A,D), (B,C), (B,D)
Spieler 2 hat nur (X) und (Y)

Spielt 1 (B,C) und 2 spielt X habe ich die Auszahlung 15,5
Spielt 1 (B,C) und 2 spielt Y habe ich die Auszahlung 0,0

Spielt 1 (B,D) und 2 spielt X habe ich die Auszahlung 0,0
Spielt 1 (B,D) und 2 spielt Y habe ich die Auszahlung 5,15

Das ist doch soweit richtig wenn ich das in die Normalform abtrage, oder?

Kannst du mir dann für (A,C) und (A,D) die Auszahlung sagen?

Einfach immer (12,12) da Spieler 1 zuerst A wählt und das was auf dem anderen Pfad passieren würde keine Rolle spielt, da das Spiel ja vorbei ist.

Hmmmm

Das heißt alle Strategien von SP 1 Mit A werden zu einer Auszahlung von 12,12 fuehren.

Aber dann hätte ich drei NGG.
(AC),Y
(AD),Y
Und natuerlich (BC)X

Original von pmatze
Wenn du Fall 3 als Lösung zulässt, also das er mischt, bekommst du hier nach der Logik von Fall 4, doch im Grunde unendlich viele weitere NGG, oder?

Ja, stimmt.

Neue Frage

Original von Fireandice23
Hi

Ich habe nochmal eine Frage.
Folgende Situation haben wir:
Verkäufer hat für ein Gut eine Wertschätzung von 20€. Der Käufer hat eine Wertschätzung von 100€
Folgende Preise können verwendet werden: (10,20,30,40,50,60,70,80,90).

a) wenn es eine Verhandlungsrunde gibt und der Verkäufer das Angebot abgeben darf. Wie hoch wird der Preis sein?
b) wenn es eine Verhandlungsrunde gibt und der Käufer das Angebot abgeben darf. Wie hoch wird der Preis sein?
c) in der ersten Runde wird keine Einigung erzielt. Wie hoch wird das Angebot des Käufer sein, wenn zusätzlich noch abdiskontiert wird?

Meine Lösungen:
a) der Preis wird bei 90€ liegen.
b) es wenn eine Runde gibt, wird der Preis bei 20 liegen?
c) Irgendwie kam ich mit der Fragestellung nicht zurecht. In der Spieltheorie sollte ich doch von rationalen Entscheidungen ausgehen.
Demnach würde man doch nie in eine zweite Verhandlungsrunde kommen. Aber wenn es trotzdem eine zweite Runde gibt, sollte ich als Käufer wieder die Wertschätzung des Verkäufers bieten.
Problematisch wird es jetzt aber mit dem abdiskontieren. Bietet der Käufer 20€, sind es ja real weniger.
Deswegen müsste man den Verlust ausgleichen.
Da man aber keine kleineren Schritte machen kann, würde ich jetzt als Käufer 30€ bieten.

Was sagt ihr?

a) und b) passen schonmal.

zu c) bin ich nicht sicher was die frage soll, aber wenn abdiskontiert wird, dann ja wohl der wert des gegenstandes, also wird er nicht 30€ sondern unter 20€ (bzw 20€ da diskret) bieten.
und ja du hast recht, im NGG wird immer in der ersten Runde gehandelt. aber die Tatsache das es in die zweite Runde gehen könnte, wird den Preis der ersten Runde beeinflussen.

c) ist schlecht gestellt: Es geht hier explizit um das subgame, nachdem der Käufer das erste Angebot rejected hat. Da der Käufer weiß, dass der VK jedes Angebot oberhalb von aufdiskontiert 20 (seine Evaluation in t0 ist 20 => in t1 nur noch 20*discount rate) annehmen wird, gilt folgendes: Sei die discount rate r \in [0,1], dann wird er das minimale x \in {10,...,90} wählen, sodass r*x => 20. Dann accepted der VK und beide haben schwach positiven Profit.

Zur Hintergründen und Lösung dieser Art von Spiele, siehe "Rubinstein's Bargaining".