Vorlesung: Nicht-kooperative Spieltheorie [0.5cm] Teil 1

Organisatorisches und Inhalte der Vorlesung
Nutzentheorie
Vorlesung: Nicht-kooperative Spieltheorie
Teil 1: Organisatorisches, Inhalte der Vorlesung
und Nutzentheorie
Dr. Thomas Krieger
Wintertrimester 2009
und
Dr. Thomas Krieger
Vorlesung: Nicht-kooperative Spieltheorie
1 / 15
Organisatorisches und Inhalte der Vorlesung
Nutzentheorie
Organisatorisches
Ort und Zeit
Vorlesungsfolien und Übungsblätter unter http://www.
unibw.de/inf4/lehre/wahlpflicht/spieltheorie
Klausur oder mündliche Prüfung?
Kombination aus Vorlesung und Übung
und
Dr. Thomas Krieger
Vorlesung: Nicht-kooperative Spieltheorie
2 / 15
Organisatorisches und Inhalte der Vorlesung
Nutzentheorie
Inhalte der Vorlesung (1)
Teil 1: Nutzentheorie
Binäre Relationen und Präferenzordnungen, Repräsentierbarkeit
durch eine Nutzenfunktion, Satz von Birkhoff
Teil 2: Normalformspiele
Cournot’sches Oligopolspiel, Nash-Gleichgewicht, Satz von
Nikaido-Isoda und Satz von Nash, Axiomatische Rechtfertigung
von Nash-Gleichgewichten, gemischte Strategien und das
Antwortkriterium, Minimax- und Maximin versus
Nash-Gleichgewicht, Besonderheiten von Normalformspielen
(n-Personenspiele (n ≥ 3), Satz von Wilson, Satz von Wu),
Verfahren zur Bestimmung von Nash-Gleichgewichten
und
Dr. Thomas Krieger
Vorlesung: Nicht-kooperative Spieltheorie
3 / 15
Organisatorisches und Inhalte der Vorlesung
Nutzentheorie
Inhalte der Vorlesung (2)
Teil 3: Gleichgewichtsauswahltheorie
Chancen, Grenzen und Nutzen derselben, Beispiele und
Gegenbeispiele
Teil 4: Nullsummenspiele
Minimax und Maximin, Sattelpunkte, Verfahren zur
Berechnung von Sattelpunkten, Beispiel: Angriff und
Verteidigung
Teil 5: Spiele in extensiver Form
reine und gemischte Strategien, Verhaltensstrategien, Satz von
Kuhn, teilspielperfekte Gleichgewichte und
Rückwärtsinduktion, Beispiel: Schmuggler und Patroullie
und
Dr. Thomas Krieger
Vorlesung: Nicht-kooperative Spieltheorie
4 / 15
Organisatorisches und Inhalte der Vorlesung
Nutzentheorie
Einleitende Bemerkungen
Jeder Spieler besitzt in einem Spiel eine Menge an
Handlungsmöglichkeiten (Strategien).
Die eigene Handlung eines Spielers führt in Abhängigkeit von
den Handlungen der anderen Spieler zu Ergebnissen
x , y , z, . . . ∈ M, die aus Sicht der einzelnen Spieler subjektiv
bewertet werden. M ist Menge der Ergebnisse oder
Alternativen.
Ziel: (subjektive) Einschätzungen der möglichen
Spielausgänge messen, d.h., mit reellen Zahlen so bewerten,
dass insbesondere einer höheren („besseren“) Einschätzung
auch ein höherer Zahlenwert entspricht.
und
Dr. Thomas Krieger
Vorlesung: Nicht-kooperative Spieltheorie
5 / 15
Organisatorisches und Inhalte der Vorlesung
Nutzentheorie
Binäre Relationen
Was brauchen wir, um Alternativen vergleichen zu können?
Definition 1
Eine binäre (oder zweistellige) Relation auf M 6= ∅ ist eine
Teilmenge des kartesischen Produktes M × M, also R ⊆ M × M.
Wir schreiben statt (x , y ) ∈ R auch xRy . Ist (x , y ) 6∈ R, so
schreiben wir ¬ xRy
Grundsätzlich sind vier Fälle möglich:
(xRy ∧ yRx ), (xRy ∧ ¬ yRx ), (¬ xRy ∧ yRx ) und
(¬ xRy ∧ ¬ yRx )
und
Dr. Thomas Krieger
Vorlesung: Nicht-kooperative Spieltheorie
6 / 15
Organisatorisches und Inhalte der Vorlesung
Nutzentheorie
Repräsentierbarkeit durch Nutzenfunktion (1)
Definition 2
Auf M 6= ∅ seien eine binäre Relation R und eine Funktion
u : M −→ R1 gegeben. Die Relation R wird durch u repräsentiert,
falls gilt:
xRy
⇐⇒
u(x ) < u(y ) .
u heisst Nutzenfunktion zu R.
Wozu brauchen wir überhaupt Nutzenfunktionen?
(Entscheidungsproblem wird zu numerischem
Optimierungsproblem)
u ist eine sogenannte order-preserving function.
Welche binären Relationen sind durch eine Nutzenfunktion
repräsentierbar?
Dr. Thomas Krieger
Vorlesung: Nicht-kooperative Spieltheorie
und
7 / 15
Organisatorisches und Inhalte der Vorlesung
Nutzentheorie
Repräsentierbarkeit durch Nutzenfunktion (2)
Lemma 3
Ist die binäre Relation R auf M 6= ∅ durch eine Nutzenfunktion
repräsentierbar, dann ist R
(i) asymmetrisch, d.h., wenn xRy =⇒ ¬ yRx , und
(ii) negativ transitiv, d.h., wenn xRy , dann gilt für jedes z ∈ M
entweder xRz oder zRy oder beides.
=⇒ Beweis siehe Tafel (nur mittels der Anordnungsaxiome von R).
Bearbeiten Sie Aufgabe 1 des Arbeitsblatt zur Nutzentheorie
Unter gewissen Voraussetzungen an M bzw. R gilt auch die
Umkehrung des obigen Satzes (Satz von Birkhoff)
und
Dr. Thomas Krieger
Vorlesung: Nicht-kooperative Spieltheorie
8 / 15
Organisatorisches und Inhalte der Vorlesung
Nutzentheorie
Präferenzordnung und die Indifferenzrelation
Die Aussagen von Lemma 3 legen folgende Definition nahe:
Definition 4
Eine asymmetrisch und negativ transitive binäre Relation auf
M 6= ∅ heisst Präferenzordnung (prä-ferre = vorziehen) und wird
mit ≺ bezeichnet.
Aus den vier möglichen Fällen der letzte Fall liefert:
Definition 5
Sei ≺ eine Präferenzordnung auf M 6= ∅. Dann wird die
Indifferenzrelation ∼ auf M definiert durch:
x ∼ y : ⇐⇒ ¬ (x ≺ y ) ∧ ¬ (y ≺ x ) .
Ist u eine Nutzenfunktion auf M, die ≺ repräsentiert, so gilt:
x ∼y
⇐⇒
Dr. Thomas Krieger
u(x ) = u(y ) .
und
Vorlesung: Nicht-kooperative Spieltheorie
9 / 15
Organisatorisches und Inhalte der Vorlesung
Nutzentheorie
Wichtige Eigenschaften von Präferenzordnungen
Lemma 6
Es sei ≺ eine Präferenzordnung auf M 6= ∅. Dann gilt:
Für alle x , y ∈ M gilt genau eine der folgenden Beziehungen
x ≺ y , y ≺ x oder x ∼ y .
≺ ist transitiv.
=⇒ Beweis siehe Tafel.
und
Dr. Thomas Krieger
Vorlesung: Nicht-kooperative Spieltheorie
10 / 15
Organisatorisches und Inhalte der Vorlesung
Nutzentheorie
Wichtige Eigenschaften der Indifferenzrelation
Lemma 7
Es sei ≺ eine Präferenzordnung auf M 6= ∅. Dann gilt:
∼ ist reflexiv, symmetrisch und transitiv, also eine
Äquivalenzrelation. Mit M\ ∼ wird die Menge der
Äquivalenzklassen bezeichnet.
Für a, b ∈ M\ ∼ gilt:
∃x ∈ a
∃ y ∈ b : x ≺ y ⇐⇒ ∀ x ∈ a
∀y ∈ b : x ≺ y
Auf M\ ∼ wird durch a ≺0 b ⇐⇒ ∃x ∈ a ∃y ∈ b : x ≺ y
eine strikte, d.h., eine schwach vollständige
(a 6= b =⇒ a ≺0 b ∨ b ≺0 a) Präferenzordnung definiert.
=⇒ Beweis siehe Tafel.
und
Dr. Thomas Krieger
Vorlesung: Nicht-kooperative Spieltheorie
11 / 15
Organisatorisches und Inhalte der Vorlesung
Nutzentheorie
Repräsentierbarkeit durch Nutzenfunktion (3)
Bearbeiten Sie Aufgabe 2 des Arbeitsblatt zur Nutzentheorie
Weiter zum Ziel: Klasse der durch Nutzenfunktionen
repräsentierbaren Präferenzordnungen ≺ auf M bestimmen.
Lemma 8
Die lexikographische Präferenzordnung auf R2 ist nicht durch eine
Nutzenfunktion repräsentierbar.
=⇒ Beweis siehe Tafel.
Bearbeiten Sie Aufgabe 3 des Arbeitsblatt zur Nutzentheorie
Lexikographische Ordnungen sind also i.A. zu kompliziert, um
durch eine (eindimenionale) Nutzenfunktion repräsentiert
werden zu können.
und
Dr. Thomas Krieger
Vorlesung: Nicht-kooperative Spieltheorie
12 / 15
Organisatorisches und Inhalte der Vorlesung
Nutzentheorie
Repräsentierbarkeit durch Nutzenfunktion (4)
Theorem 9 [Birkhoff, 1973]
Es sei ≺ eine Präferenzordnung auf M 6= ∅ und M\ ∼ sei endlich
oder abzählbar unendlich, dann existiert eine Nutzenfunktion
u : M −→ R1 mit
x ≺y
⇐⇒
u(x ) < u(y ) für alle
x, y ∈ M .
=⇒ Beweis siehe Tafel.
Wichtige Folgerung: Ist M endlich oder abzählbar unendlich,
dann sind die Voraussetzungen des obigen Satzes erfüllt.
Auch wenn M\ ∼ nicht abzählbar ist, kann eine
Nutzenfunktion existieren (Stichwort: ordnungsdicht),
Beispiel: M = R, Präferenzordnung < und u(x ) := x .
und
Dr. Thomas Krieger
Vorlesung: Nicht-kooperative Spieltheorie
13 / 15
Organisatorisches und Inhalte der Vorlesung
Nutzentheorie
Abschliessende Bemerkungen
Einordnung der lexikographischen Ordnung auf R2 : vergleiche
Lemma 8 und Aufgabe 3.
u : M −→ R1 repräsentiere ≺ und f : R −→ R sei eine streng
monoton wachsende Funktion. Dann repräsentiert f (u(x ))
ebenfalls ≺. (Bemerkung: wieviel größer vs. ob überhaupt
größer)
Verallgemeinerungen des Theorems sind möglich
(Birkhoff/Debreu)
Bisher: Nutzenfunktion(en) unter Sicherheit, später auch
Unsicherheit
Vorschau auf nächste Vorlesung: . . .
und
Dr. Thomas Krieger
Vorlesung: Nicht-kooperative Spieltheorie
14 / 15
Organisatorisches und Inhalte der Vorlesung
Nutzentheorie
Literatur für diesen Abschnitt:
P. C. Fisburn: Utility Theory for Decision Making. John Wiley & Sons, Inc.,
New York u.a., 1970
D. M. Kreps: Mikroökonomische Theorie. Verlag Moderne Industrie,
Landsberg/Lech, 1994.
B. Rauhut, N. Schmitz, E.-W. Zachow: Spieltheorie: Einführung in die
mathematische Theorie strategischer Spiele. Teubner-Verlag, Stuttgart, 1979.
G. Birkhoff: Lattice Theory. 3. Auflage, American Mathematical Society,
Providence Rhode-Island, 1973.
G. Debreu: Representation of a Preference Ordering by a Numerical Function.
In: R. Thrall, C. Coombs and R. Davis (Hrsg.), Decision Process, John Wiley &
Sons, Inc., New York u.a., 1954.
M. Pasche: Spieltheorie. Vorlesungsunterlagen, Friedrich-Schiller Universität,
Jena, ohne Jahr.
und
Dr. Thomas Krieger
Vorlesung: Nicht-kooperative Spieltheorie
15 / 15

Download Report