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)
[email protected] 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,
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, [email protected] 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, [email protected] 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)
[email protected] 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