Koncepcja rozwiązania
W teorii gier koncepcja rozwiązania jest formalną regułą przewidywania sposobu gry. Te prognozy nazywane są „rozwiązaniami” i opisują, jakie strategie przyjmą gracze, a tym samym wynik gry. Najczęściej używanymi koncepcjami rozwiązań są koncepcje równowagi , najsłynniejsza równowaga Nasha .
Wiele koncepcji rozwiązań dla wielu gier skutkuje więcej niż jednym rozwiązaniem. Stawia to pod znakiem zapytania dowolne z rozwiązań, więc teoretyk gier może zastosować uściślenie, aby zawęzić rozwiązania. Każda kolejna koncepcja rozwiązania przedstawiona poniżej ulepsza swoją poprzedniczkę, eliminując nieprawdopodobne równowagi w bogatszych grach.
Definicja formalna
Niech klasą wszystkich gier i dla każdej gry będzie zbiorem profili strategii . Pojęcie rozwiązania jest elementem iloczynu bezpośredniego tj . Funkcja takie, że dla wszystkich
Racjonalizacja i iterowana dominacja
W tej koncepcji rozwiązania zakłada się, że gracze są racjonalni, dlatego strategie ściśle zdominowane są eliminowane ze zbioru strategii, które można by zastosować. Strategia jest ściśle zdominowana , gdy gracz ma do dyspozycji inną strategię, która zawsze ma wyższą wypłatę, niezależnie od strategii wybranych przez innych graczy. (Strategie ściśle zdominowane są również ważne w przeszukiwaniu drzewa gry minimax ). Na przykład w (pojedynczym okresie) dylemacie więźnia (pokazanym poniżej) współpraca jest ściśle zdominowana przez defekt dla obu graczy, ponieważ każdy gracz zawsze lepiej gra defektem , niezależnie od tego, co zrobi jego przeciwnik.
| Więzień 2 Współpracuj | Więzień 2 Wada | |
|---|---|---|
| Więzień 1 Współpracuj | −0,5, −0,5 | −10, 0 |
| Wada więźnia 1 | 0, −10 | −2, −2 |
Równowaga Nasha
Równowaga Nasha to profil strategii (profil strategii określa strategię dla każdego gracza, np. w powyższej grze z dylematem więźnia ( współpraca , defekt ) określa, że więzień 1 gra we współpracę , a więzień 2 w defekt ), w którym każda strategia jest najlepsza odpowiedź na każdą inną zagraną strategię. Strategia gracza jest najlepszą odpowiedzią na strategię innego gracza, jeśli nie ma innej strategii, którą można by zastosować, która przyniosłaby wyższą wypłatę w każdej sytuacji, w której strategia innego gracza jest rozgrywana.
Indukcja wsteczna
W niektórych grach istnieje wiele równowag Nasha, ale nie wszystkie z nich są realistyczne. W grach dynamicznych indukcję wsteczną można wykorzystać do wyeliminowania nierealistycznych równowag Nasha. Indukcja wsteczna zakłada, że gracze są racjonalni i podejmą najlepsze decyzje w oparciu o swoje przyszłe oczekiwania. Eliminuje to niewiarygodne groźby, których gracz nie wykonałby, gdyby kiedykolwiek został do tego wezwany.
Rozważmy na przykład dynamiczną grę z istniejącą firmą i potencjalnym nowym graczem w branży. Operator zasiedziały ma monopol i chce utrzymać swój udział w rynku. Jeśli uczestnik wejdzie, urzędujący może albo walczyć, albo go pomieścić. Jeśli operator zasiedziały się dostosuje, uczestnik wejdzie i uzyska zysk. Jeśli operator zasiedziały będzie walczyć, obniży ceny, wyeliminuje wchodzącego z rynku (ponosząc koszty wyjścia) i zniweczy własne zyski.
Najlepszą reakcją dla operatora zasiedziałego, jeśli kandydat wejdzie, jest dostosowanie się, a najlepszą reakcją dla operatora, jeśli operator zasiedziały się dostosuje, jest wejście. Prowadzi to do równowagi Nasha. Jeśli jednak urzędujący zdecyduje się walczyć, najlepszą reakcją dla wchodzącego jest rezygnacja z udziału. Jeśli uczestnik nie wejdzie, nie ma znaczenia, co zdecyduje się zrobić operator zasiedziały. W związku z tym walkę można uznać za najlepszą odpowiedź dla urzędującego, jeśli uczestnik nie wejdzie, co skutkuje kolejną równowagą Nasha.
Jednak tę drugą równowagę Nasha można wyeliminować przez indukcję wsteczną, ponieważ opiera się ona na niewiarygodnym zagrożeniu ze strony urzędującego. Zanim operator zasiedziały dotrze do węzła decyzyjnego, w którym może zdecydować się na walkę, byłoby to irracjonalne, ponieważ uczestnik już wszedł. Dlatego indukcja wsteczna eliminuje tę nierealistyczną równowagę Nasha.
Zobacz też:
Idealna równowaga Nasha w grze podrzędnej
Uogólnieniem indukcji wstecznej jest doskonałość gry podrzędnej. Indukcja wsteczna zakłada, że wszystkie przyszłe gry będą racjonalne. W idealnej równowadze podgry gra w każdej podgrze jest racjonalna (w szczególności równowaga Nasha). Indukcji wstecznej można używać tylko w grach kończących (skończonych) o określonej długości i nie można jej stosować do gier z niedoskonałymi informacjami . W takich przypadkach można zastosować doskonałość gry podrzędnej. Wyeliminowana równowaga Nasha opisana powyżej jest niedoskonała podgrą, ponieważ nie jest to równowaga Nasha podgry, która zaczyna się w węźle osiągniętym po wejściu uczestnika.
Doskonała równowaga bayesowska
Czasami doskonałość gry podrzędnej nie nakłada wystarczająco dużych ograniczeń na nieracjonalne wyniki. Na przykład, ponieważ gry podrzędne nie mogą przebić się przez zbiory informacji , gra z niedoskonałymi informacjami może mieć tylko jedną grę podrzędną - samą siebie - a zatem perfekcji podgry nie można użyć do wyeliminowania jakiejkolwiek równowagi Nasha. Doskonała równowaga bayesowska (PBE) to specyfikacja strategii i przekonań graczy co do tego, który węzeł w zbiorze informacji został osiągnięty w trakcie gry. Przekonanie o węźle decyzyjnym to prawdopodobieństwo, że dany gracz myśli, że ten węzeł jest lub będzie w grze (na ścieżce równowagi ). W szczególności intuicja PBE polega na tym, że określa strategie graczy, które są racjonalne, biorąc pod uwagę przekonania gracza, które określa, a przekonania, które określa, są spójne ze strategiami, które określa.
W grze bayesowskiej strategia określa, w co gracz gra przy każdym zestawie informacji kontrolowanym przez tego gracza. Wymóg, aby przekonania były zgodne ze strategiami, nie jest określony przez doskonałość podgry. Dlatego PBE jest warunkiem spójności przekonań graczy. Tak jak w równowadze Nasha strategia żadnego gracza nie jest ściśle zdominowana, tak w PBE dla dowolnego zestawu informacji strategia żadnego gracza nie jest ściśle zdominowana, począwszy od tego zbioru informacji. Oznacza to, że dla każdego przekonania, które gracz mógłby utrzymać przy tym zbiorze informacji, nie ma strategii, która przyniosłaby większą oczekiwaną wypłatę dla tego gracza. W przeciwieństwie do powyższych koncepcji rozwiązań, strategia żadnego gracza nie jest ściśle zdominowana, zaczynając od dowolnego zestawu informacji, nawet jeśli jest on poza ścieżką równowagi. Tak więc na PBE gracze nie mogą grozić, że zagrają strategiami, które są ściśle zdominowane, począwszy od jakichkolwiek informacji wyznaczających ścieżkę równowagi.
Bayesian w nazwie tej koncepcji rozwiązania nawiązuje do faktu, że gracze aktualizują swoje przekonania zgodnie z twierdzeniem Bayesa . Obliczają prawdopodobieństwa biorąc pod uwagę to, co już miało miejsce w grze.
Indukcja do przodu
Indukcja do przodu jest tak nazywana, ponieważ tak jak indukcja do tyłu zakłada, że przyszła gra będzie racjonalna, tak indukcja do przodu zakłada, że poprzednia gra była racjonalna. Jeśli gracz nie wie, jakiego typu jest inny gracz (tj. istnieją niedoskonałe i asymetryczne informacje), gracz ten może wyrobić sobie przekonanie, jakiego typu jest ten gracz, obserwując jego wcześniejsze działania. Stąd przekonanie utworzone przez tego gracza, jakie jest prawdopodobieństwo, że przeciwnik jest określonego typu, opiera się na racjonalnej grze tego przeciwnika w przeszłości. Gracz może zasygnalizować swój typ poprzez swoje akcje.
Kohlberg i Mertens (1986) wprowadzili koncepcję rozwiązania równowagi stabilnej, udoskonalenie, które spełnia indukcję do przodu. Znaleziono kontrprzykład, w którym taka stabilna równowaga nie spełniała indukcji wstecznej. Aby rozwiązać ten problem, Jean-François Mertens przedstawił to, co teoretycy gier nazywają obecnie koncepcją równowagi stabilnej Mertensa , prawdopodobnie pierwszą koncepcją rozwiązania spełniającą zarówno indukcję do przodu, jak i do tyłu.
Indukcja do przodu daje unikalne rozwiązanie dla płonącej gry pieniężnej .
Zobacz też
- Cho, IK.; Kreps, DM (1987). „Gry sygnalizacyjne i stabilna równowaga”. Kwartalnik Ekonomii . 102 (2): 179–221. CiteSeerX 10.1.1.407.5013 . doi : 10.2307/1885060 . JSTOR 1885060 . S2CID 154404556 .
- Fudenberg Drew ; Tyrol, Jean (1991). Teoria gier . Cambridge, Massachusetts: MIT Press . ISBN 9780262061414 . Podgląd książki.
- Harsanyi, J. (1973) Dziwność liczby punktów równowagi: nowy dowód . International Journal of Game Theory 2: 235–250.
- Govindan, Srihari i Robert Wilson, 2008. „Udoskonalenia równowagi Nasha”, The New Palgrave Dictionary of Economics, wydanie 2. [1]
- Hines, WGS (1987) Stabilne strategie ewolucyjne: przegląd podstawowej teorii . Teoretyczna biologia populacji 31: 195–272.
- Kohlberg, Elon i Jean-François Mertens, 1986. „ O stabilności strategicznej równowagi ”, Econometrica, Towarzystwo Ekonometryczne, tom. 54(5), strony 1003-37, wrzesień.
- Leyton-Brown, Kevin; Shoham, Yoav (2008). Podstawy teorii gier: zwięzłe, multidyscyplinarne wprowadzenie . San Rafael, Kalifornia: Wydawcy Morgan & Claypool. ISBN 978-1-59829-593-1 .
- Mertens, Jean-François, 1989. „Stabilne równowagi - przeformułowanie. Część 1 Podstawowe definicje i właściwości”, Matematyka badań operacyjnych, tom. 14, nr 4, listopad [2]
- Noldeke, G. & Samuelson, L. (1993) Ewolucyjna analiza indukcji wstecznej i do przodu . Gry i zachowania ekonomiczne 5: 425–454.
- Maynard Smith, J. (1982) Ewolucja i teoria gier . ISBN 0-521-28884-3
- Osborne, Martin J.; Rubinstein, Ariel (1994). Kurs teorii gier . MIT Naciśnij . ISBN 978-0-262-65040-3 . .
- Selten, R. (1983) Stabilność ewolucyjna w rozbudowanych grach dwuosobowych . Matematyka soc. nauka 5:269–363.
- Selten, R. (1988) Stabilność ewolucyjna w rozbudowanych grach dwuosobowych – korekta i dalszy rozwój . Matematyka soc. nauka 16:223–266
- Shoham, Yoav; Leyton-Brown, Kevin (2009). Systemy wieloagentowe: podstawy algorytmiczne, teoretyczne i logiczne . Nowy Jork: Cambridge University Press . ISBN 978-0-521-89943-7 .
- Thomas, B. (1985a) O stabilnych zbiorach ewolucyjnych. J. Matematyka. Biol. 22:105–115.
- Thomas, B. (1985b) Stabilne zestawy ewolucyjne w modelach mieszanych strategii . Teoria. Muzyka pop. Biol. 28:332–341