Transcript
Wstęp do teorii gier
Sherlock Holmes i prof. Moriarty
Sherlock Holmes and prof. Moriarty • „Sherlock Holmes, pursued by his opponent, Moriarty, leaves London for Dover. The train stops at a station on the way, and he alights there rather than travelling on to Dover. He has seen Moriarty at the railway station, recognizes that he is very clever and expects that Moriarity will take a faster special train in order to catch him in Dover. Holmes' anticipations turns out to be correct. But what if Moriarity had been still more clever, had estimated Holmes' mental abilities better and had foreseen his actions accordingly? Then, obviously, he would have travelled to the intermediate station [Canterbury]. Holmes again would have had to calculate that, and he himself would have decided to go on to Dover. Whereupon, Moriarity would again have “reacted” differently.”, Morgenstern 1935
Sherlock Holmes and prof. Moriarty M
D(q)
C(1-q)
4,25
12,5
H D(p)
C(1-p) 16,10 8,15 Holmes: Moriarty wie, że ja chcę jechać do Dover, zatem muszę wysiąść w Canterbury. Ale Moriarty jest przecież bardzo przebiegły. Dlatego może on przewidzieć mój ruch i również pojechać do Canterbury. Zatem, powinienem pojechać do Dover. Ale Moriarty i to również może przewidzieć – w końcu jest równie mądry jak ja.
Sherlock Holmes i prof. Moriarty Czyli jakkolwiek bym nie rozumował, Moriarty jest w stanie odgadnąć gdzie pojadę i tym samym mnie złapie
Sherlock Holmes i prof. Moriarty Rozwiązanie dylematu Holmes’a: Jeśli ja sam nie wiem co zrobię, wówczas Moriarty nie może zgadnąć mojej akcji – Ignorance is a bliss (Niewiedza jest błogosławieństwem)
Sherlock Holmes i prof. Moriarty M
D(q)
C(1-q)
D(p)
4,25
12,5
C(1-p)
16,10
8,15
H
Równowaga strategii mieszanych: • Moriarty wybiera strategię q, przy której Holmes jest obojętny, czy jechać do Dover czy do Canterbury:
• Holmes wybiera strategię p, przy której Moriarty jest obojętny:
Sherlock Holmes i prof. Moriarty q
1
BMoriarty(p)
BHolmes(q)
1/4
1 1/5
p
Sherlock Holmes i prof. Moriarty M H D(p) C(1-p) 1/5D+4/5C
D(q) (4,25) (16,10) (13.6,13)
C(1-q) (12,5) (8,15) (8.8,13)
1/4D+3/4C (10,10) (10,13.75) (10,13)
Doniesienie o przestępstwie, czyli czemu ludzie w tłumie są obojętni • 20 osób widzi przestępstwo i decyduje, czy zadzwonić na policję – Jeśli ja nie zadzwonię i nikt inny też nie: 0 – Jeśli ja nie zadzwonię, ale ktoś inny tak: 10 – Jeśli ja zadzwonię: 10-5=5
• Jest N równowag Nasha w czystych strategiach – W każdej równowadze dokładnie jedna osoba dzwoni – Ale jak zdecydować kto? (norma społeczna)
• Rozpatrzmy równowagę symetryczną (każdy wybiera tą samą strategię)
Doniesienie o przestępstwie • Równowagi symetryczne: • Nikt nie dzwoni na policję – nie może być równowagą • Każdy dzwoni na policję – nie może być równowagą • Jedyna opcja – symetryczna równowaga strategii mieszanych
• Każda osoba musi być obojętna między zadzwonieniem a nie dzwonieniem: Gdzie p – prawdopodobieństwo, że ktoś inny zadzwoni
• Każda osoba zadzwoni z prawdopodobieństwem α = 0.0358
Eliminacja strategii zdominowanych przez strategię mieszaną
Eliminacja strategii zdominowanych przez strategię mieszaną
• T jest akcją, która nigdy nie jest najlepszą odpowiedzią • Z tego wynika, że istnieje prawdopodobieństwo p takie, że U1(pM+(1-p)B,i)>U1(T,i), dla każdej akcji i gracza kolumnowego
Eliminacja strategii zdominowanych przez strategię mieszaną
Statyczne vs dynamiczne gry Gra statyczna: • Gracze poruszają się jednocześnie • Naturalnie prezentowana w postaci tabelki (forma standardowa, strategiczna, normalna) Gra dynamiczna z doskonałą informacją: • Gracze poruszają się sekwencyjnie • Są doskonale poinformowani o wcześniejszych ruchach swoich i swoich przeciwników • Kolejność ruchów jest sprecyzowana • Naturalnie prezentowana w postaci drzewa (forma ekstensywna)
Doskonała a zupełna informacja • Doskonała vs niedoskonała informacja – Czy gracze mają wszelką możliwą wiedzę co do wcześniejszych ruchów (swoich własnych, przeciwników i natury)? • Zupełna vs niezupełna informacja – Czy wszystkie elementy gry (gracze, zbiory akcji i strategii, wypłaty) są wiedzą wspólną dla graczy? • 3 ważne słowa: – strategia – pełny plan akcji dla każdego wierzchołka decyzyjnego danego gracza – akcja – co zrobić w danym wierzchołku decyzyjnym – ruch – akcja rzeczywiście podjęta przez gracza
Szeryf Kane vs Frank Miller p1(d0) 1-p1(d0) p2(d1) 1-p2(d1)
p1(d2) 1-p1(d2) p2(d3) 1-p2(d3) p1(d4) 1-p1(d4) p2(d5) 1-p2(d5) p1(d6)
1-p1(d6)
W L
L W
W L
L W
W L
W L L W
Szeryf Kane vs Frank Miller
p1(d0) 1-p2(d1) p1(d2) 1-p2(d3) p1(d4) 1-p2(d5) p1(d6)
Dylemat więźnia – wersja dynamiczna
Dylemat więźnia – wersja dynamiczna
Biedronka i Lidl • Lidl zastanawia się, czy wybudować kolejny supermarket na ulicy Szadkowskiego w Warszawie blisko Biedronki • Jeśli Lidl zbuduje sklep, Biedronka zdecyduje, czy zaangażować się z wojnę cenową (attrition war)
Biedronka i Lidl – forma strategiczna
• Dwie równowagi Nasha – problem selekcji • Niektóre równowagi Nasha mogą zawierać niewiarygodne groźby – nieracjonalne zachowanie poza ścieżką równowagi
Równowaga indukcji wstecznej • Równowaga indukcji wstecznej likwiduje „złą” równowagę, która zawiera niewiarygodną groźbę
Trzy firmy
• Równowaga indukcji wstecznej: (OUT; OUT; AAF) • Jest jednak dużo więcej równowag Nasha, na przykład (IN; IN; AFA) – niewiarygodna groźba Tesco.
Subgame Perfect Nash Equilibrium • Zbiór SPNE jest podzbiorem NE • SPNE wymaga racjonalności sekwencyjnej • SPNE jest NE w każdej podgrze – Podgra to kontynuacja gry po tym, jak parę ruchów już zostało dokonanych – Akcja to możliwa decyzja w wierzchołku decyzyjnym – Strategia to kompletny plan akcji dla wszystkich możliwych sytuacji w grze (Tesco ma dwie akcje w każdym ze swoich wierzchołków decyzyjnych, ale aż 8 strategii AAA, AAF, …, FFF)
Gry w formie ekstensywnej (drzewo) vs gry w formie strategicznej (tabelka) • Gra w postaci strategicznej składa się z: – Zbiór graczy – Dla każdego gracza: • Zbiór akcji • Funkcja wypłat dla każdego profilu akcji
• Gry w postaci ekstensywnej zawierają więcej informacji: – Kolejność ruchów – Akcje, które mają do dyspozycji gracze na różnych etapach gry – Informacja dostępna dla graczy podczas gry
Drzewo – graf acykliczny • Wierzchołki: – Wierzchołki decyzyjne oraz losowe – Korzeń i liście
• • • • •
Krawędzie (gałęzie) Etykiety graczy Etykiety akcji Wypłaty Zbiory informacji
Strategie w grach ekstensywnych • Strategia czysta gracza jest to plan akcji w każdym wierzchołku decyzyjnym tego gracza • W równowadze indukcji wstecznej każdy gracz gra optymalnie w każdym wierzchołku decyzyjnym (gra sekwencyjnie racjonalną strategię) • Równowaga a wynik gry w równowadze
Dr Strangelove • Komandor floty powietrznej Stanów Zjednoczonych rozkazuje 34 B-52, aby rozpocząć nuklearny atak na Związek Radziecki • Zamyka wszystkie kanały komunikacji z bazą i samolotami • Amerykański prezydent zaprasza rosyjskiego ambasadora do war room i wyjaśnia sytuację • Decydują się zadzwonić do rosyjskiego premiera Dimitrija
Dr Strangelove • Co jest wynikiem jeśli Stany Zjednoczone nie wiedzą o istnieniu doomsday device? • Co jest wynikiem jeśli wiedzą? • Zobowiązanie (commitment) musi być obserwowalne • Co jeśli Związek Sowiecki może zdezaktywować urządzenie? • Zobowiązanie musi być nieodwracalne Thomas Schelling: The power to constrain an adversary depends upon the power to bind oneself
