Teoria gier. Podstawy matematyczne Rida Laraki, Jérôme Renault, Sylvain Sorin

Spis treści książki

WSTĘP xi Streszczenie xi Podsumowanie książki xiv Wymagania wstępne xvii Lektura uzupełniająca xviii Podziękowania xix Rozdział 1 Wprowadzenie 1 1.1. Interakcja strategiczna 1 1.1.1. Gry strategiczne 1 1.1.2. Gry koalicyjne 1 1.1.3. Wybór społeczny i projektowanie mechanizmów 2 1.2. Przykłady 2 1.2.1. Stabilne dopasowania 2 1.2.2. Problem targowania się 3 1.2.3. Równowaga transportu 3 1.2.4. Aukcje 3 1.2.5. Paradoks Condorceta 4 1.2.6. Gra ewolucyjna 4 1.2.7. Gra stochastyczna 4 1.2.8. Gra powtarzana 5 1.3. Notacje i podstawowe pojęcia 6 1.3.1. Gry strategiczne 6 1.3.2. Dominacja 6 1.3.3. Iterowana eliminacja 7 1.3.4. Najlepsza odpowiedź 7 1.3.5. Mieszane rozwinięcia 7 1.4. Informacja i racjonalność 8 1.4.1. Strategia dominująca i wynik zdominowany 8 1.4.2. Dominacja i optimum w sensie Pareto 9 1.4.3. Kolejność eliminacji 9 1.4.4. Hipotezy wiedzy 9 1.4.5. Dominacja a strategie mieszane 10 1.4.6. Gry dynamiczne a przewidywania 10 1.5. Ćwiczenia 10 Rozdział 2 Gry o sumie zerowej: przypadek skończony 14 2.1. Wprowadzenie 14 2.2. Wartość i strategie optymalne 14 2.3. Reguła minimaksu 17 2.4. Własności zbioru strategii optymalnych 19 2.5. Twierdzenia Loomisa i Ville'a 20 2.6. Przykłady 22 2.7. Gra fikcyjna 22 2.8. Ćwiczenia 26 2.9. Komentarze 34 Rozdział 3 Gry o sumie zerowej: przypadek ogólny 35 3.1. Wprowadzenie 35 3.2. Twierdzenia o minimaksie w przypadku strategii czystych 35 3.3. Reguły minimaksu w strategiach mieszanych 39 3.4. Operator wartości i gra pochodna 41 3.5. Ćwiczenia 43 3.6. Komentarze 47 Rozdział 4 Gry N-osobowe: racjonalność i punkty równowagi 48 4.1. Wprowadzenie 48 4.2. Notacja i terminologia 49 4.3. Dominacja najlepszej odpowiedzi w grach skończonych 49 4.4. Racjonalizowalność w zwartych grach ciągłych 51 4.5. Punkty e-równowagi i równowagi Nasha: defi nicja 53 4.6. Równowaga Nasha w grach skończonych 55 4.7. Równowaga Nasha w grach ciągłych 56 4.7.1. Istnienie równowag w strategiach czystych 57 4.7.2. Istnienie równowag w strategiach mieszanych 58 4.7.3. Charakterystyka i jedyność równowagi Nasha 59 4.8. Gry nieciągłe 61 4.8.1. Rozwiązanie Reny'ego dla gier nieciągłych 61 4.8.2. Równowagi Nasha w grach nieciągłych 64 4.8.3. Przybliżone równowagi Nasha w grach nieciągłych 65 4.9. Semialgebraiczność zbioru równowag Nasha 67 4.10. Uzupełnienie 69 4.10.1. Wykonalne wypłaty i punkt groźby 69 4.10.2. Niezmienność, symetria, punkty ogniskowe i wybór równowagi 70 4.10.3. Zachowanie Nasha kontra zachowanie ostrożne 71 4.10.4 Wpływ wiedzy powszechnej na grę 72 4.11. Twierdzenia o punktach stałych 73 4.12. Ćwiczenia 77 4.13. Komentarze 81 Rozdział 5 Rozmaitość i dynamika równowag 83 5.1. Wprowadzenie 83 5.2. Uzupełnienie dotyczące równowag 84 5.2.1. Równowagi i nierówności wariacyjne 84 5.2.1.1. Gry skończone 84 5.2.1.2. Gry wklęsłe 84 5.2.1.3. Gry populacyjne 84 5.2.1.4. Ogólna ewaluacja 85 5.2.2. Gry potencjalne 86 5.2.2.1. Gry skończone 86 5.2.2.2. Gry ewaluacyjne 86 5.3. Rozmaitości równowag 87 5.4. Pola wektorowe Nasha i dynamiki 90 5.5. Równowagi i ewolucja 91 5.5.1. Dynamiki replikatorów 91 5.5.2. Papier, kamień, nożyce 92 5.5.3. Gry potencjalne 93 5.5.4. Inne dynamiki 94 5.5.4.1. Dynamika replikatora 94 5.5.4.2. Dynamika Browna-von Neumanna-Nasha 94 5.5.4.3. Dynamika Smitha 94 5.5.4.4. Dynamika najlepszej odpowiedzi 94 5.5.5. Własność ogólna 95 5.5.6. ESS 95 5.6. Ćwiczenia 97 5.7. Komentarze 100 Rozdział 6 Gry w postaci ekstensywnej 101 6.1. Wprowadzenie 101 6.2. Gry w postaci ekstensywnej z informacją doskonałą 102 6.2.1. Opis 102 6.2.2. Strategia i postać normalna 103 6.2.3. Półzredukowana postać normalna 104 6.2.4. Zdeterminowanie gier skończonych z informacją doskonałą 105 6.2.5. Natura jako gracz 107 6.2.6. Równowaga doskonała w podgrach 108 6.2.7. Gry nieskończone z informacją doskonałą 110 6.3. Gry w postaci ekstensywnej z informacją niedoskonałą 112 6.3.1. Zbiory informacyjne 112 6.3.2. Redukcja postaci normalnej 113 6.3.3. Strategie randomizowane 114 6.3.4. Pamięć doskonała 116 6.3.5. Równowaga Nasha w strategiach behawioralnych 118 6.4. Doskonalenie równowagi w grach w postaci ekstensywnej 119 6.4.1. Równowaga doskonała w podgrach 120 6.4.2. Równowagi doskonałe sekwencyjne i bayesowskie 121 6.5. Udoskonalenie równowagi w grze o postaci normalnej 123 6.6. Powiązania między udoskonaleniami dla postaci ekstensywnych i normalnych 126 6.7. Indukcja w przód i stabilność strategiczna 128 6.8. Ćwiczenia 131 6.9. Komentarze 135 Rozdział 7 Równowagi skorelowane, uczenie się, równowagi bayesowskie 136 7.1. Wprowadzenie 136 7.2. Równowagi skorelowane 136 7.2.1. Przykłady 137 7.2.2. Struktury informacyjne i gry rozszerzone 138 7.2.3. Równowaga skorelowana 139 7.2.4. Korelacja kanoniczna 140 7.2.5. Charakterystyka 141 7.2.6. Komentarze 141 7.3. Procedury bez żalu 142 7.3.1. Żal zewnętrzny 142 7.3.2. Żal wewnętrzny 144 7.3.3. Kalibracja 146 7.3.4. Zastosowanie w grach 147 7.3.4.1. Zewnętrzna niesprzeczność a zbiór Hannana 148 7.3.4.2. Wewnętrzna niesprzeczność a równowagi skorelowane 149 7.4. Gry z informacją niekompletną (lub gry bayesowskie) 150 7.4.1. Strategie, wypłaty i równowagi 150 7.4.2. Uzupełnienia 151 7.5. Ćwiczenia 153 7.6. Komentarze 156 Rozdział 8 Wprowadzenie do gier powtarzanych 158 8.1. Wprowadzenie 158 8.2. Przykłady 159 8.3. Model standardowej gry powtarzanej 161 8.3.1. Historie i rozgrywki 161 8.3.2. Strategie 161 8.3.3. Wypłaty 162 8.4. Wykonalne i indywidualnie racjonalne wypłaty 164 8.5. Twierdzenia Ludowe 165 8.5.1. Jednolite twierdzenie Ludowe 166 8.5.2. Dyskontowe twierdzenie Ludowe 166 8.5.3. Skończenie powtarzane twierdzenie Ludowe 168 8.5.4. Twierdzenia Ludowe dla doskonałości w podgrach 170 8.5.4.1. Jednolite równowagi doskonałe w podgrach 170 8.5.4.2. Dyskontowe równowagi doskonałe w podgrach 170 8.5.4.3. Skończenie powtarzane równowagi doskonałe w podgrach 173 8.6. Rozszerzenie: gry stochastyczne, informacja niekompletna, sygnały 174 8.6.1. Gra powtarzana z sygnałami 175 8.6.2. Gry stochastyczne: Wielkie Dopasowanie (Big Match) 176 8.6.3. Gry powtarzane z informacją niepełną: Twierdzenie Cav u 180 8.6.3.1. Przypadek ogólny informacji jednostronnie niepełnej 182 8.7. Ćwiczenia 187 Rozdział 9 Rozwiązania ćwiczeń 192 9.1. Podpowiedzi dla rozdziału 1 192 9.2. Podpowiedzi dla rozdziału 2 193 9.3. Podpowiedzi dla rozdziału 3 197 9.4. Podpowiedzi do rozdziału 4 201 9.5. Podpowiedzi dla rozdziału 5 206 9.6. Podpowiedzi do rozdziału 6 209 9.7. Podpowiedzi dla rozdziału 7 214 9.8. Podpowiedzi dla rozdziału 8 218 BIBLIOGRAFIA