Der Preis der Anarchie · 2016-09-26 · Damit ein Spiel ein Spiel ist, braucht es Regeln. Diese...

Martin Grötschel Institut für Mathematik, Technische Universität Berlin (TUB)DFG-Forschungszentrum “Mathematik für Schlüsseltechnologien” (FZT 86)Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)

groetschel@zib.de http://www.zib.de/groetschel

Der Preis der AnarchieEgoismus versus Systemoptimium

Martin GrötschelMünchner Wissenschaftstage

im Jahr der Mathematik19. Oktober 2008

InhaltSpieltheorieDas Nash-GleichgewichtPreis der AnarchieFairnessAnwendungen

MartinGrötschel

2

InhaltSpieltheorieDas Nash-GleichgewichtPreis der AnarchieFairnessAnwendungen

MartinGrötschel

3

SpieltheorieIm einem Spiel versucht jeder schlauer (oder besser oder erfolgreicher) zu sein als die anderen Mitspieler. Die Spieltheorie untersucht, was herauskommt, wenn alle Spieler versuchen, das Beste für sich herauszuholen.Damit ein Spiel ein Spiel ist, braucht es Regeln. Diese Regeln sagen,

was jeder einzelne Spieler tun kann und was nichtwas jeder Spieler wissen darf und was nicht und was das Ziel des Spiels ist.

Beispiel: Beim Schach sagen die Regeln, wie sich die Figuren bewegen können, dass man sie alle immer sehen darf und dass das Ziel ist, den König matt zu setzen.Die Spieltheorie beschäftigt sich jedoch immer stärker mit sozialwissenschaftlichen Sachverhalten. Und hier ist es schwerer zu sehen, welche Regeln nun wirklich gelten und woher die Regeln kommen. Insbesondere sind gesellschaftliche Regeln nicht fest. Sie unterliegen Entwicklungen (z. B. durch die Gesetzgebung).

MartinGrötschel

4

Spieltheorie: DefinitionenDie Spieltheorie ist eine Theorie zur mathematischen Analyse von Konflikten. Die Spieltheorie ist eine Entscheidungstheorie, die Situationen untersucht, in denen das Ergebnis nicht von einem Entscheider allein bestimmt werden kann. Das Ergebnis hängt von den individuellen Entscheidungen aller Beteiligten ab. Hierbei gibt es Situationen, wo jeder für sich allein (ohne Rücksicht auf andere) entscheidet, die Spieler können aber auch gemeinsam (kooperativ) agieren.

MartinGrötschel

5

Stein, Schere, Papier

MartinGrötschel

6

B

Stein Schere Papier

Stein 0 +1 -1

A Schere -1 0 +1

Papier +1 -1 0

Wie soll man spielen?

Reine Strategie

Gemischte Strategie

Stein, Schere, Papier, BrunnenDominierte Strategie

MartinGrötschel

7

B

Stein Schere Papier Brunnen

Stein 0 +1 -1 -1

Schere -1 0 +1 -1

A Papier +1 -1 0 +1

Brunnen +1 +1 -1 0

Der Sinn gemischter StrategienPraxis:

Schutz gegen psychologisch überlegene Gegner:Randomisierung

MartinGrötschel

8

Wieland Rhenau,

rhenau@inf.fu-

berlin.de

9

Spiele: einmalig, wiederholt?Einmalige vs. Wiederholte Spiele

Einmaliges Spiel „one-shot-game“Eine DurchführungDanach Auszahlung

Wiederholte SpieleDurchführung mehrmals hintereinanderAuszahlungen werden summiertStrategisch relevant: Spieler kennen Rundenzahl?Ist Wiederholung unendlich „Superspiel“

NullsummenspielEin Spiel heisst Nullsummenspiel, wenn die Summe der Auszahlungen an alle beteiligten Spieler gleich Null ist.Fast alle Gesellschaftsspiele sind Nullsummenspiele:

Schach, Mühle, Dame, GoPoker, SkatStein, Schere, PapierSchiffe versenken…

Ein Spiel mit vollständiger Information ist ein Spiel, bei dem keine versteckten Elemente vorkommen. Versteckte Elemente sind z. B. unbekannte Karten der Gegner (Poker, Skat), Zufallszüge (zufällige Kartenverteilung zu Beginn des Spiels) oder gleichzeitige Züge aller Spieler.Spiele mit vollständiger Information sind z. B.

Schach, Mühle, Dame, Go

Die anderen oben genannten jedoch nicht.Martin

Grötschel

10

GewinnstrategienStreicholzspielNicht jedes Spiel besitzt eine „Lösung“ in reinen Strategien.

Minimax-Theorem: Für jedes Zwei-Personen-Nullsummenspiel mit endlich vielen reinen Strategien gibt es eine gemischte Strategie x für Spieler 1, eine gemischte Strategie y für Spieler 2 und einen Wert V, so dass, wenn Spieler 1 die Strategie x spielt, er immer mindestens V gewinnt, und wenn Spieler 2 die Strategie y spielt, er immer höchstens –V verliert.Stein, Schere, Papier: Würfeln!

MartinGrötschel

11

GewinnstrategienSpiele mit vollständiger Information besitzen eine reine Gewinnstrategie!

Schach: Es gibt eine Gewinnstrategie, aber keiner kennt sie.Streichholzspiel: einfache Regel für Gewinnstrategie.Tic Tac Toe: immer unentschiedenMühle: immer unentschieden, d.h. ein guter Spieler verliert nie.(Hierzu wurden rund 10 Billionen Positionen auf einem Computer analysiert.)

MartinGrötschel

12

Kooperativ vs nicht-kooperativDas Gefangenendillemma

MartinGrötschel

13

InhaltSpieltheorieDas Nash-GleichgewichtPreis der AnarchieFairnessAnwendungen

MartinGrötschel

14

Nash GleichgewichtDas Nash-Gleichgewicht, auch Nash-Equilibriumgenannt, ist ein zentraler Begriff der mathematischen Spieltheorie. Es beschreibt in nicht-kooperativen Spielen einen Zustand eines strategischen Gleichgewichts, von dem ausgehend kein einzelner Spieler für sich einen Vorteil erzielen kann, indem er einseitig von seiner Strategie abweicht. Es ist ein grundlegendes Lösungskonzept der Spieltheorie. Definition und Existenzbeweis des Nash-Gleichgewichts gehen auf die 1950 veröffentlichte Dissertation des Mathematikers John Forbes Nash Jr. zurück.Im Jahr 1994 erhielt Nash für diese Leistung (zusammen mit Reinhard Selten und John Harsanyi) den Nobelpreis für Wirtschaftswissenschaften.

MartinGrötschel

15

John Nash 2002 in Beijing

Beautiful Mind (über John Nash)

Film über John Nash gelöscht

Was war in dem Film los?Harold Kuhn:Was der Film zeigt, ist gar kein Nash-Gleichgewicht, sondern eine kooperative Lösung.

MartinGrötschel

18

Formale DefinitionEin Spiel sei durch die Menge der Spieler N, den Strategienraum S = S1x…xSn der Spieler und den Vektor U = (u1, …, un) der Auszahlungsfunktionen gegeben.Eine Strategienkombination S = (s1, …, sn) ist ein Nash-Gleichgewicht, wennui(s1,…, si, …, sn) ≥ ui(s1,…, ti, …, sn) für alle i und alle ti.Es gibt Spiele, die mehrere Nash-Gleichgewichte haben und solche, die überhaupt keines in reinen Strategien haben.Satz von Nash: Jedes Spiel mit endlichem Strategienraum hat ein Nash-Gleichgewicht in gemischten Strategien.

MartinGrötschel

19

Kooperativ vs nicht-kooperativDas Gefangenendillemma

Nash-Gleichgewicht

MartinGrötschel

20

Wieland Rhenau, rhenau@inf.fu-berlin.de 21

Spiel ohne Nash-Gleichgewichtin reinen Strategien

Einfaches Beispiel: „Torschuss“Ein Schütze, ein TorwartVereinfacht: nach links/rechts schießen

links/rechts springen

Es existiert kein Nash-GleichgewichtDer Verlierer kann immer Strategie ändernund damit gewinnen!

Wieland Rhenau, rhenau@inf.fu-berlin.de 22

Mehrere Nash-GleichgewichteSpiel mit dem Untergang

Zwei Autos fahren aufeinander zuWer ausweicht ist der „Angsthase“

Zwei Nash Gleichgewichte in reiner Strategie:Fahrer1 ausweichen/Fahrer2 weiterfahren undFahrer1 weiterfahren/Fahrer2 ausweichenEin Nash Gleichgewicht in gemischten Strategien ausweichen/ausweichen Weil: beide weichen mit Wahrscheinlichkeit von ½ aus

InhaltSpieltheorieDas Nash-GleichgewichtPreis der AnarchieFairnessAnwendungen

MartinGrötschel

23

Preis der AnarchieDieses Konzept wurde im Jahre 1999 von Elias Koutsoupias, Christos Papadimitriou in ihrem Artikel Worst-case Equilibria im Rahmen von Untersuchungen von Nutzerverhalte auf Netzwerken vorgeschlagen. Frage: Wie schlecht kann eine „stabile Lösung“ sein, die sich bei egoistischem Verhalten der Nutzer einstellt?Egoistisches Verhalten führt zu Nash-Gleichgewichten. Es kann viele solcher Gleichgewichte geben. Etwas salopp: Der Preis der Anarchie ist das Verhältnis von Wert des schlechtesten Nash-Gleichgewichts zum Systemoptimum.

MartinGrötschel

24

Preis der AnarchieGenauer: Jeder Strategiekombination S = (s1, …, sn) wird ein Wert C(S)zugeordnet . (Wir wollen hier minimieren.)Der Preis der Anarchie ist dann definiert als:

Interpretation:Beispiel Gefangenendillemma:

Nash-Gleichgewicht (4, 4), d.h. 8 Jahre Gefängnis.Minimum (1, 1), also 2 Jahre Gefägnis.Der Preis der Anarchie beim Gefangenendillemma ist gleich 4.Folgerung: Kooperation (bzw. zentrale Planung) ist viermal so gut wie egoistisches VerhaltenMartin

Grötschel

25

{ }{ }

max ( ) :StrategiekombinationSistNash-Gleichgewicht

min ( ) :SbeliebigeStrategiekombination

C Sp

C S=

MATHEON-Projekte im Verkehr und Netzwerken, Rolf Möhring

MartinGrötschel

26

MATHEON-Projekte im Verkehr und Netzwerken, Rolf Möhring

MartinGrötschel

27

MATHEON-Projekte im Verkehr und Netzwerken, M. Grötschel (ZIB)

MartinGrötschel

28

MATHEON-Projekte im Verkehr und Netzwerken, M. Grötschel (ZIB)

MartinGrötschel

29

MATHEON-Projekte im Verkehr und Netzwerken, M. Grötschel (ZIB)

MartinGrötschel

30

Steuerung des IndividualverkehrsDas Braess-Paradox: Erweitert man ein Straßennetz um eine weitere Straße, so kann sich für jeden Fahrer die Fahrzeit verlängern. (Dietrich Braess, „Über ein Paradoxon aus der Verkehrsplanung“, 1968).Es gibt hunderte von Artikeln hierzu, aus der Tagespresse:

(G. Szpiro), Irrationales bei Airlines und Passagieren. Das Braess-Paradoxon am Beispiel der Flugroutenwahl. Neue Zürcher Zeitung 9. Jan. 2006, S. 5 W. Blum, Ewig lockt die Schnellstraße. Psychologen bestätigen ein mathematisches Paradoxon: Manchmal lösen zusätzliche Strecken den Stau erst aus. Süddeutsche Zeitung 24. Jan. 2006, S. 9 A. Rooch. Auf Umwegen schneller zum Ziel. 6. Folge der WAZ-Serie "Was ist Mathematik?" - Das Braess-Paradoxon. Westdeutsche Allgemeine Zeitung 5. August 2006.

MartinGrötschel

31

Das Braess-Paradox

MartinGrötschel

32

Alle Fahrer wollen von A nach D.

Verkehrsdichte x = 1000 Autos/h

tAC(x) = tBD(x) = 50 + x Minuten

tAB(x) = tCD(x) = 0 + 10x Minuten

Stündlich 6000 Autofahrer.

Nash-Gleichgewicht: Auf jeder Strecke fahren3000 Autos, Fahrzeit: 83 min/Auto

Neue Strecke BC

tBC(x) = (10 + x) Minuten

Nash-Gleichgewicht: 2000 Autos auf ABD2000 Autos auf ACD2000 Autos auf ABCDFahrzeit: 92 min/Auto

Auftreten von Braess-Paradoxen in der realen WeltEs gibt reale Beispiele dafür, dass das Braess-Paradoxon nicht nur ein theoretisches Konstrukt ist.

1969 führte in Stuttgart die Eröffnung einer neuen Straße dazu, dass sich in der Umgebung des Schlossplatzes der Verkehrsfluss verschlechterte. Auch in New York konnte das umgekehrte Phänomen 1990 beobachtet werden. Eine Sperrung der 42. Straße sorgte für weniger Staus in der Umgebung. Weitere empirische Berichte gibt es über Auftreten auf den Straßen Winnipegs.

MartinGrötschel

33

MartinGrötschel

34

Weiteres Beispiel2 parallele Straßen

Fahrzeit oben: x = Anzahl der FahrzeugeFahrzeit unten: 100100 Fahrzeuge wollen von links nach rechts.Alle werden oben fahren, jeweils mit der Fahrzeit 100.Beste Lösung: 50 oben, 50 untenPreis der Anarchie: 10.000/7.500 = 4/3

x

100

InhaltSpieltheorieDas Nash-GleichgewichtPreis der AnarchieFairnessAnwendungen

MartinGrötschel

35

Selfish Routing (egoistische Routenwahl)

Fahrer wählen die Route, die Ihnen am günstigsten erscheint.Es ist natürlich nicht ganz klar, was das in der Praxis heisst.Navigationssysteme und Psychologie

MartinGrötschel

36

Zentrales Verkehrsmanagement

MartinGrötschel

37

Technologische AnforderungenExakte Kenntnis aller Fahrzeugpositionen und –zieleZweiseitige Verbindung zu zentralem ServerServer kennt gegenwärtigen Zustand vollständig.

Systemoptimum kann berechnet werden.Aber:

Einige Routen können viel zu lang sein.

Zentrales Verkehrsmanagement

MartinGrötschel

38

Systemoptimumohne „Fairnessbedingungen”

Systemoptimummit „Fairnessbedingungen”

Zentrales Verkehrsmanagement

MartinGrötschel

39

Systemoptimumohne „Fairnessbedingungen”

Systemoptimummit „Fairnessbedingungen”

Was ist Fairness?

MartinGrötschel

40

Unfairness einer „Routenplanungspolitik“ im Bezug auf ein Nutzergleichgewicht

Unfairness = 1 im NutzergleichgewichtUnfairness kann beliebig groß werden (in der Theorie)

( , )OD-Paar

Reisezeit für OD-Paar ( , ) im Routenplan Reisezeit für OD-Paar ( , ) im Nutzergleichgewicht

maxu v

u vu v

Fairness-Analyse

MartinGrötschel

41

Fairness-Analyse für einige Städte

MartinGrötschel

42

InhaltSpieltheorieDas Nash-GleichgewichtPreis der AnarchieFairnessAnwendungen

MartinGrötschel

43

MartinGrötschel

44

Herlitz in FalkenseeBüroartikel, Glückwunschkarten, etc.

MartinGrötschel

45

Integrierter innerbetrieblicher Transport

Logistik

MartinGrötschel

46

Logistik-Film gelöscht

Aufzug-Optimierung

MartinGrötschel

47

Aufzug-Film gelöscht

Anwendungen in der Telekommunikation

MartinGrötschel

48

Dissertation, TU Berlin 2007

MartinGrötschel

49

Zelluläre Funknetze

Funkschnittstelle

Ein UMTS-Funknetz

Antenne

Zelle

Zelluläres Netz

Zelluläres Netz

Zelluläres Netz

Zelluläres Netz

Martin Grötschel Institut für Mathematik, Technische Universität Berlin (TUB)DFG-Forschungszentrum “Mathematik für Schlüsseltechnologien” (FZT 86)Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)

groetschel@zib.de http://www.zib.de/groetschel

Der Preis der AnarchieEgoismus versus Systemoptimium

Martin GrötschelMünchner Wissenschaftstage

im Jahr der Mathematik19. Oktober 2008

Vielen Dank für Ihre Aufmerksamkeit