Spieltheorie - Eine kleine Einführung mit Beispielen

Spieltheorie - Eine kleine Einführung mit Beispielen

Spieltheorie Andreas Diekmann ETH Zrich Spieltheorie ist wie Statistik ein Gebiet der Mathematik. Sie bildet heute die Grundlage der konomie (Kartelle, Auktionsregeln, Regelung von Mrkten usw.). Anwendungen finden sich in den Sozialwissenschaften (Soziologie, Sozialpsychologie, Politikwiss. u.a.), in der Informatik (Rechnernetze), in der Biologie (evolutionre Spieltheorie), z.B. reziproker Altruismus unter nicht-verwandten Organismen und selbst in der medizinischen Forschung (z.B. Infektion durch Salmonellen, Diard et al., 2013, Nature

494; Entstehung von Tumoren, Basabta et al., 2008, Cell Proliferation 41 Roulette: Entscheidung unter Risiko Was ist Spieltheorie? Im Sinne der Spieltheorie: Roulette spielen? Eine Entscheidung fr einen Zug im Schach oder bei Stein, Schere, Papier treffen? Ein Men auf der Speisekarte auswhlen? Einem Privatpatienten eine eintrgliche, aber womglich wenig ntzliche Therapie vorschlagen, die dieser ablehnen oder akzeptieren kann?

Was ist Spieltheorie? Im Sinne der Spieltheorie: Roulette spielen? Kein Spiel Eine Entscheidung fr einen Zug im Schach oder bei Stein, Schere, Papier treffen? Ein Spiel Ein Men auf der Speisekarte auswhlen? Kein Spiel

Einem Privatpatienten eine eintrgliche, aber womglich wenig ntzliche Therapie vorschlagen, die dieser ablehnen oder akzeptieren kann? Ein Spiel Entscheidungen und Spieltheorie 1. Entscheidungen unter Sicherheit oder Risiko (z. B. Roulette): Keine Spieltheorie! 2. Entscheidungsprobleme, bei denen das Ergebnis von den Handlungen anderer Personen abhngt (strategische Interdependenz von Handlungen)

Das ist die Domne der Spieltheorie. Entscheidungstheorie A. Ein Akteur entscheidet 1. Entscheidungen unter Sicherheit 2. Entscheidungen unter Risiko (z.B. Roulette, Wahrscheinlichkeiten der Konsequenzen sind bekannt). 3. Entscheidungen unter Unsicherheit (die Wahrscheinlichkeiten der Konsequenzen sind nicht bekannt). B. Mehrere Akteure (N 2) entscheiden und das Ergebnis hngt von der Kombination ihrer Strategien ab. Damit befasst sich die Spieltheorie! Der unberechenbare Torwart

beim Elfmeter Elfmeterschtze entscheidet: Soll ich den Ball in die linke oder in die rechte Ecke schiessen? Torwart entscheidet: Soll ich mich nach links oder rechts werfen? Simultane Entscheidung bei hoher Ballgeschwindigkeit und menschlicher Reaktionszeit! Torwart und Elfmeterschtze: Links oder rechts? Elfmeterschtze Links Torwart

Rechts Links 1, -1 -1, 1 Rechts -1, 1 1, -1 z.B. links, links: Auszahlung an den Torwart betrgt 1,

Auszahlung an den Elfmeterschtzen -1 Nullsummenspiel Optimale Strategie? Torwart und Elfmeterschtze: Links oder rechts? Elfmeterschtze Links Torwart Rechts Links 1, -1

-1, 1 Rechts -1, 1 1, -1 z.B. links, links: Auszahlung an den Torwart betrgt 1, Auszahlung an den Elfmeterschtzen -1 Nullsummenspiel Optimale Strategie? Spieler whlen links oder rechts mit Wahrscheinlichkeit .

Elfmeter in der dt. Bundesliga Elfmeterschtze Torwart Links Rechts Links 202 (23%) 220 (25%)

Rechts 225 (26%) 231 (26%) 878 Elfmeter aus der Spielsaison 92/93 bis 03/04. Nach Berger und Hammer (2007). Spaltenspieler Zeilenspieler S1 S2

S3 Z1 2, -2 4, -4 9, -9 Z2 6, -6 5, -5

7, -7 Z3 8, -8 3, -3 1, -1 Auch ein Nullsummenspiel. Was ist hier die rationale Wahl? Auszahlung an Zeilenspieler: Erste Ziffer, Auszahlung an Spaltenspieler 2. Ziffer. Z.B. Zeilenspieler whlt Z1, Spaltenspieler whlt S2: Ergebnis (4,-4). Zeilenspieler Erhlt 4, Spaltenspieler -4). S1

S2 S3 Z1 2, -2 4, -4 9, -9 Z2 6, -6

5, -5 7, -7 Z3 8, -8 3, -3 1, -1 Es gibt einen Sattelpunkt: Minimum in der Zeile, Maximum in der Spalte (bezogen auf Auszahlungen fr den Zeilenspieler).

Zeile whlt Z2, Spalte whlt S2. Der Sattelpunkt ist ein Gleichgewicht. Niemand hat ein Interesse einseitig abzuweichen. Sattelpunkt-Theorem Minimum in der Zeile, Maximum in der Spalte The Final Problem (1893): Sherlock Holmes und Professor Moriarty Kent railways Wikipedia London Victoria Canterbury Dover Holmes berlegt: Soll ich den Zug in Canterbury verlassen? Aber damit rechnet Reichenbachflle,

auch Moriarty. Also doch besser bis Dover? Meiringen Aber das kalkuliert Moriarty auch ein dann doch in Dover aussteigen? usw. Welche ist die rationale Strategie von Holmes, von Moriarty? Sherlock Holmes Professor Moriarty Dover (0,4) Canterbury (0,6) Dover (0,6)

+100, -100 0, 0 Canterbury (0,4) -50, +50 +100, -100 Moriartys Strategie: z* = (0,6; 0,4). Holmes Strategie: s* = (0,4; 0,6). Das Beispiel ist von Oskar Morgenstern (1928). John von Neumann und Oskar Morgenstern, 1944: Theory of Games and Economic Behavior. Princeton, Princeton

University Press: 176-178. John von Neumann (1928) Einer der genialsten Mathematiker des 20. Jahrhunderts hat sich vorwiegend mit Nullsummenspielen befasst. John von Neumann, 1928: Theorie der Gesellschaftsspiele. Mathematische Annalen 100: 295-320 John von Neumann (1928) Minimax-Theorem. Jedes Nullsummenspiel mit endlicher Anzahl Strategien hat ein Gleichgewicht in reinen oder gemischten

Strategien (John von Neumann, 1928: Theorie der Gesellschaftsspiele) Warum hat John von Neumann die Spieltheorie entwickelt? Warum hat John von Neumann die Spieltheorie entwickelt? 1. Er war begeisterter Poker-Spieler und wollte Poker auf eine rationale Grundlage stellen. Warum hat John von Neumann die Spieltheorie entwickelt? 1. Er war begeisterter Poker-Spieler und

wollte Poker auf eine rationale Grundlage stellen. 2. Er wollte Kontroversen mit seiner Frau rational lsen. Warum hat John von Neumann die Spieltheorie entwickelt? 1. Er war begeisterter Poker-Spieler und wollte Poker auf eine rationale Grundlage stellen. 2. Er wollte Kontroversen mit seiner Frau rational lsen. 3. Frau von Neumann soll gesagt haben, sie interessiere sich nur fr Spieltheorie, wenn darin ein Elefant vorkme.

John von Neumann und Oskar Morgenstern, 1947: Theory of Games and Economic Behavior. Princeton, Princeton University Press: 64 (2. Aufl.) Nullsummenspiele: Vollstndig antagonistische Interessen, keine Mglichkeit zur Kooperation Die Welt ist Nonzero (Robert Wright). Dieses Buch zur Spieltheorie wurde von einem Mitspieler in der Weltpolitik empfohlen, nmlich von Bill Clinton auf youtube (Last year I read a book that describes the way the world works.) http://www.youtube.com/watch?v=DnLosZVG54k Die meisten Konfliktsituationen entsprechen Spielen mit gemischten Interessen. Die Akteure haben teils gemeinsame, teils divergierende Interessen. Nicht-Nullsummenspiele Eines der bekanntesten Spiele:

Gefangenendilemma Eine Parabel fr den Konflikt zwischen individuellen Interessen und kollektivem Gut Besuchen Sie Tosca und entdecken Sie ein Gefangenendilemma zwischen Tosca und Scarpia! Gegenseitige Selbstschdigung im einmaligen Gefangenendilemma Gefangenendilemma: 0, 0 ist das Nash-Gleichgewicht, aber 5, 5 wre fr beide besser! Scarpia C = Platzpatronen

D = echte Munition C = Sex mit Scarpia 5, 5 -10,10 D = Scarpia erdolchen 10, -10 0, 0

Tosca C = Coopperation D = Defektion Resultat beidseitiger Defektion (D): Scarpia wird erdolcht, Cavaradossi wird erschossen. Rapoport (1962) John F. Nash (1950, 1951) Nash-Gleichgewicht Jedes Spiel mit endlicher Anzahl von Strategien hat mindestens ein Gleichgewicht in reinen oder gemischten Strategien.

Nash, John F. (1950): Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, USA, 36: 48-49. Nash, John F. (1951): Non-cooperative games. Annals of Mathematics 54: 286295. Nobelpreis zusammen mit J. Harsanyi und R. Selten 1994 Beautiful Mind Evolution von Kooperation In the state of nature life was solitary, poor, nasty, brutish, and short

(Thomas Hobbes 1651) Kooperieren Kooperieren Betrgen 5, 5 Betrgen -10,10 10, -10 0, 0 Evolution von Kooperation unter

Egoisten Kann dennoch unter Egoisten ohne uere Sanktionen (ohne Leviathan, ohne Staat) Kooperation entstehen? Wird das Gefangenendilemma (die Interaktion) wiederholt, ohne das das Ende der Interaktionen bekannt ist und sind die knftigen Ertrge hoch genug, dann ndert sich die strategische Situation grundlegend. Wiederholtes Spiel (iteriertes Spiel) C C D

C D C D C D 3,3 0,5 3,3

0,5 3,3 0,5 3,3 0,5 D 5,0 1,1 5,0 1,1 5,0 1,1 5,0 1,1 ...

Runde 1 2 3 4 Einige Strategien: 1. Immer C: C C C C 2. Immer D D D D D 3. Trigger-Strategie: Kooperieren (C), aber wenn der

Partner einmal D spielt, dann immer D (Friedman) 4. Tit-For-Tat (TFT): Beginnt mit C und whlt immer das, was der Partner vorher gewhlt hat (Anatol Rapoport). ... Evolution von Kooperation unter Egoisten Kann dennoch unter Egoisten ohne uere Sanktionen (ohne Leviathan, ohne Staat) Kooperation entstehen? Wird das Gefangenendilemma (die Interaktion) wiederholt, ohne dass das Ende der Interaktionen bekannt ist und sind die knftigen Ertrge hoch genug, dann werden beide Akteure dauerhaft kooperieren. Beispiel: Sozialer Austausch.

Voraussetzung: Wiederholtes Spiel und hinreichend groer Schatten der Zukunft Computersimulationen von Axelrod (1984): Tit-for-Tat als Gewinnstrategie (Anatol Rapoport) Stellungskrieg im I. Weltkrieg System des Leben und leben lassen Aus Tagebuchaufzeichnungen von Weltkrieg I Soldaten: Der kleine Friede im groen Krieg (Michael Jrgs): Kooperation unter feindlichen Soldaten Im Stellungskrieg an der Westfront Der wahre Grund, dass es in einigen Abschnitten so ruhig war, bestand darin, dass keine Seite die Absicht hatte, in das Gebiet vorzurcken. Wenn die Briten die Deutschen mit Granaten beschossen, reagierten die Deutschen und das Ausma der Zerstrung war auf beiden Seiten gleich. Wenn die Deutschen den vorderen Teil des Schtzengrabens bombardierten und fnf Englnder tteten, wurde zurck gefeuert und fnf Deutsche

gettet (Belton Cobb 1916). In einem Abschnitt wurde die Zeit von 8 bis 9 am Morgen privaten Geschften gewidmet, und gewisse Pltze, die durch eine rote Fahne markiert waren, waren fr die Scharfschtzen beider Seiten Tabu (Morgan 1916). Ich trank Tee mit der Kompanie als wir Rufe hrten und hinausgingen um nachzuschauen. Wir sahen unsere Leute und die Deutschen auf den Schtzengrben. Pltzlich kam eine Salve, richtete aber keinen Schaden an. Natrlich gingen beide Seiten in Deckung und unsere Mnner begannen auf die Deutschen zu fluchen, als pltzlich ein mutiger Deutscher auf die Brstung stieg und rief: Es tut uns sehr Leid, dass dies passierte. Wir hoffen, niemand wurde verletzt. Es ist nicht unsere Schuld, es ist die verdammte preuische Artillerie! (Rutter 1934). (Zitate aus Ashworth 1980 in Axelrod 1984) Der brave Mann denkt an sich selbst zuletzt! Der brave Mann denkt an sich, selbst zuletzt!

Fairness und (begrenzter) Altruismus oder homo oeconomicus? Nicht nur Eigennutz: Diktator- und Ultimatumspiel Ultimatumspiel: Eine Person teilt den Kuchen (z.B. 100 Fr.) auf. Der Mitspieler hat aber ein Vetorecht. Lehnt er ab, gehen beide leer aus. Rationalittstheorie: Spieler 1 bietet den kleinstmglichen Betrag an (1 Rp.), Spieler 2 wird akzeptieren. In Experimenten dagegen: Fairness und altruistische Reziprozitt (im Ultimatumspiel selbstschdigende Reziprozitt) Zahlreiche Anwendungen: Z.B. Erklrung fr Stabilitt von Normen, Kooperation in Teams,

Effizienzlohntheorie und Erklrung von Arbeitslosigkeit u.a. Kommt dem NashGleichgewicht nahe! Rheinpfalz, 12.9.02 Feldexperiment Kooperation Verkauf von Honig und anderen landwirtschaftlichen Erzeugnissen an einem Selbstbedienungsstand in der Region Luzern. Kunden legen

den Kaufpreis in eine Kasse. Es gibt keine berwachung. Semester paper at ETH Fraschina, Kach, Omlin, Prohaska 2007 Feldexperiment: Kooperation von Kunden beim Kauf landwirtschaftlicher Produkte Semesterarbeit ETH Fraschina, Kach, Omlin,

Prohaska 2007 Friend or Foe Variante eines Gefangenendilemma in TV-Sendung Friend (Split) Foe (Steal) Friend (Split) 1000, 1000 0, 2000

Foe (Steal) 2000, 0 0, 0 Golden Ball: Split or steal in UK TV-Show Friend or Foe Variante von Gefangenendilemma in TV-Sendung. List (2006): Auswertung fr 234 Spieler der Show in den USA. Steve Friend (Split)

Sarah Foe (Steal) Ergebnis: Friend (Split) 50075 , 50075 0, 100150

Kooperation 50 % Foe (Steal) 100150 , 0 0, 0 Mnner 45 % Frauen 56 % Drei Gleichgewichte Grenzfall von GD und Chicken! Wem vertrauen Sie? Partnersuche, Versicherungsnehmer, Einstellung von

Mitarbeitern, Kreditnehmer. Signale des Vertrauens! Asymmetrische Information und Signalspiele In den USA geben Mnner etwa drei Monatseinkommen aus fr Verlobungsringe. Vertrauensspiel: Wem vertrauen Sie? Treugeber C = Cooperation D = Defektion Treuhnder T RPS

0,0 -100,200 E = 50 + (1-)(-100) > 0 50,50 z.B. x = 100, ein ehrlicher Treuhnder zahlt die Investition von 100 zurck und teilt den Gewinn 50:50 auf. > * = (P-S)/(R-S) Soziale Dilemmata hnlich Gefangenendilemma, aber auch

mehr als zwei Akteure Selbstzerstrerische Konkurrenz, Rstungswettlauf Beitrag zu kollektiven Gtern: Z. B. 80 % der Deutschen befrworten Organtransplantationen, aber nur 12 % haben einen Spenderausweis (Trittbrettfahrerproblem). Umweltprobleme, bernutzung knapper Ressourcen Shubik (1971): 1-$-Auktion Englische Auktion: Offen, ansteigend, das hchste Gebot gewinnt. Nur eine Ausnahme:

Der zweithchste Bieter muss ebenfalls fr sein Gebot zahlen, erhlt aber nicht die Ware. X oder Y? (Rapoport) Sie haben die Wahl zwischen X oder Y Auszahlung fr X-Wahl AX = 2x Auszahlung fr Y-Wahl AY = 3x + 3 Beispiel: 20 Spieler, 10 whlen X AX = 20, AY = 33

x = Anzahl der Personen, die X whlen N-Personen-Gefangenendilemma (N-GD) AX = 2x AY = 3x+3 0 1 2 3 C=X 2

4 6 D=Y 3 6 9 18

19 8 38 40 12 57 60 andere X-Spieler

D ist die dominierende Strategie. D ist die einzige Nash-Gleichgewichtsstrategie Das Ergebnis ist aber Pareto-inferior (ineffizient) Wechselseitige Wahl von C (Kooperation) ergibt ein Pareto-optimales Resultat, ist aber kein NashGleichgewicht. Generalisierung des GD: N-GD Definition eines N-GD, Dawes (1980): D(x) > C (x+1), D(0) < C (N) Die hchste Zahl gewinnt! Schreiben Sie eine ganze Zahl 1 auf einen

Zettel Die hchste Zahl gewinnt. Allerdings wird der Preis durch die Gewinnzahl geteilt. Schreiben mehrere Teilnehmer die hchste Zahl auf, wird der Gewinn unter ihnen gleich aufgeteilt. Der Preis betrgt 100 Fr. und wird von mir ausgezahlt! 1 2 3 4 5 Ergebnis von 1439

6 7 Einsendungen: 8 9 10 100 1'000 1'000'000 1'000'000'000 6, 023 1023 (Avogadro-Zahl) 10100 (googol) 10 10**100 (googolplex) Scientific American, Prize: 1 Mio. US $

Hofstadter (1985: 759) 1133 31 16 8 16 0 9 1 1 49 61 46 33

11 1 9 14 Beauty Contest, Aktienblasen und rationales Handeln Soll man rational handeln, wenn man weiss, die anderen handeln irrational? Sie knnen eine Zahl zwischen 0 und 100 whlen. Auch alle anderen Personen sind in der gleichen Situation und sollen unabhngig voneinander eine Zahl in diesem Bereich whlen. Sie gewinnen 1 Mio , wenn Sie 2/3 des Mittelwerts aller gewhlten Zahlen am nchsten kommen. Bei mehreren Gewinnern wird der Preis geteilt! Die rationale Wahl, die Nash-Gleichgewichtsstrategie, ist?

Beauty Contest, Zahlenwahlspiel Reinhard Selten und Rosemarie Nagel 1998 Hollndische Tulpenmanie 1637 Herbst 1636 60 15. Jan. 1637 120 23. Jan. 1637 385

1. Feb. 1637 1200 3. Feb. 1637 1500 Nach dem Crash (nach 3.2.) ca. 70 Sorte Semper Augustus Preise auf Tulpenauktionen in Gulden fr ein Pfund der (relativ billigen) Sorte Switsers. Zum Vergleich: Preis eines fetten Ochsen 120 Gulden. Aus Mike Dash, 1999.

Aktienkurs der Dt. Telekom Das Allmende-Dilemma Eine Gruppe von 10 Personen besucht ein Restaurant. Sie beschliessen, die Rechnung durch die Zahl der Kpfe zu teilen. Weniger zivilisierte Personen werden einen grsseren Appetit als bei individueller Abrechnung entwickeln. 9/10 der Rechnung wird von den anderen Tischgenossen subventioniert. Folgen alle Gste dieser Logik, wird die Rechnung zum Schaden aller aufgeblht. Gleiche Logik in einem Mietshaus mit gemeinsamer Heizkostenabrechnung. Die Abholzung von Wldern, die berfischung der

Meere und allgemein die bernutzung von Ressourcen sind Beispiele mit gravierenderen Konsequenzen. Die klugen Bauern von Trbel im Wallis Klug eingerichtete Institutionen lsen soziale Dilemmata! Fallstudie: Trbel, Schweiz Allmendenutzung 1. Zugangsregelung: N Teilnehmer 2. Begrenzung der Ressourcennutzung. Winterregel: Nur soviel Vieh darf auf die Allmende, wie im Winter aus eigenem Anbau versorgt werden kann. 3. Gewalthaber verhngt Sanktionen bei

Regelverstssen und erhlt 50 % der Busse. Elinor Ostrom 1990, Nobelpreis 2009 fr die Untersuchung von Allmenden (Die Verfassung der Allmende) Institutionen sind Lsungen fr soziale Dilemmata Analyse und Design von Institutionen (z.B. Reputation auf Mrkten (eBay), Sanktionsmechanismen, Allmendedilemma, Auktionsregeln, Emissionszertifikate, Ratingagenturen, Kartellrecht, Verkehrssteuerung etc.: Spieltheorie analysiert und entwickelt Lsungsvorschlge. Institutionen sind Lsungen fr soziale

Dilemmata Analyse und Design von Institutionen (z.B. Reputation auf Mrkten (eBay), Sanktionsmechanismen, Allmendedilemma, Auktionsregeln, Emissionszertifikate, Ratingagenturen, Kartellrecht, Verkehrssteuerung etc.: Spieltheorie analysiert und entwickelt Lsungsvorschlge. Leider haben die Verhandlungen ber die globale Allmende (Klimawandel) bislang nicht zu hnlich weisen Regeln gefhrt, wie sie in Trbel Jahrhunderte existierte haben. Klug geplante Institutionen zahlen sich aus! Ken

Binmore hat mit seinem Team die Regeln zur Versteigerung der Mobilfunkfrequenzen in Grossbritannien auf Grundlage der Spieltheorie entwickelt. Die Einnahmen betrugen 22,5 Milliarden Pfund Sterling (38,5 Milliarden US $). Die kurz danach (2000) durchgefhrte Auktion in der Schweiz war ein Desaster. Die Eidgenossenschaft erzielte fr vier Lizenzen magere 205 Mio Fr. Fr den Schweizer Steuerzahler htte es sich gelohnt, den Spieltheoretiker Binmore als Berater anzuheuern. Wenn Sie etwas mehr wissen mchten

[email protected] THE END

Recently Viewed Presentations

  • Cognitive Processes PSY 334

    Cognitive Processes PSY 334

    Cognitive Processes PSY 334 Chapter 7 - Human Memory: Retention and Retrieval August 7, 2003 Inference-Based Intrusions Sulin & Dooling - subjects add details not present during learning: Carol Harris vs Helen Keller "She was deaf, dumb and blind." 5%...
  • natea.taadfw.org

    natea.taadfw.org

    Protection of Cyber Attack March 27, 2010 Presented by: Patrick Tsay at NATEA Seminar
  • Outline - Fermilab

    Outline - Fermilab

    Combined L3 System Requirements. Machine Protection System: Protect linac beam line components from stray beam. Provide specialized diagnostic system to quickly identify source of trips and increase beam up time.
  • Resource Law Enforcement

    Resource Law Enforcement

    Synonym: Mission effectiveness UNDERVALUED MISSION VALUE MEASURES RESULTS Why is the Mission Effect of Law Enforcement Undervalued? Identified as a good 'first step', it lacks rigorous data validation. It identifies mission requirements in terms of activity (miles of trail patrolled.)
  • Pressure at TDI - CERN

    Pressure at TDI - CERN

    However, some transient are occasionally observed since beginning of August and confirmed since then Following transient, equilibrium pressure are observed at both TDIs for long fills Transient pressure is correlated with temperature increase of at least 15 deg as measured...
  • User Management - MyRheem.com

    User Management - MyRheem.com

    What is User Management. User Management is the security phase of iStore. Customers will be able to manage different users within their organization so that they can access the iStore portal. User Management process includes the following functionalities: Functionality for...
  • Chemotherapeutic Agents / Antibiotics, chapter 34-39 Antibacterial compounds

    Chemotherapeutic Agents / Antibiotics, chapter 34-39 Antibacterial compounds

    from prod. of fermentation ( Glarea lozoyensis) Inhib. synth of b-1,3-D-glucan; cell wall comp. certain fungi Few good inhib. of fungi cell wall comp. compared to antibacterials Chemotherapeutic Agents / Antibiotics, chapter 34-39 Antibacterial compounds (procaryotes)-Antimycobacterials chapt. 37 Antiparasitic agents...
  • Project Management Methodology

    Project Management Methodology

    Project Management is a way of doing business for all project team members Provide project managers easy-to-use checklists and templates that target the fundamental concepts of project management Utilization of the tools will increase the probability of project success Provide...