Indukcja wsteczna

Co to jest indukcja wsteczna?

Indukcja wsteczna w teorii gier to iteracyjny proces wnioskowania wstecz w czasie, od końca problemu lub sytuacji, w celu rozwiązania skończonej, rozległej postaci i gier sekwencyjnych oraz wnioskowania o sekwencję działań optymalnych.

Wyjaśnienie indukcji wstecznej

Indukcja wsteczna jest używana do rozwiązywania gier, odkąd John von Neumann i Oskar Morgenstern ustanowili teorię gier jako przedmiot akademicki, kiedy opublikowali swoją książkę Teoria gier i zachowań ekonomicznych w 1944 roku.

Na każdym etapie gry indukcja wsteczna determinuje optymalną strategię gracza, który wykonuje ostatni ruch w grze. Następnie określa się optymalne działanie przedostatniego poruszającego się gracza, biorąc pod uwagę akcję ostatniego gracza. Ten proces jest kontynuowany wstecz, dopóki nie zostanie określone najlepsze działanie dla każdego punktu w czasie. W efekcie jeden określa równowagę Nasha w każdej podgrze oryginalnej gry.

Jednak wyniki wywnioskowane z indukcji wstecznej często nie pozwalają przewidzieć rzeczywistej gry człowieka. Badania eksperymentalne wykazały, że „racjonalne” zachowanie (zgodnie z przewidywaniami teorii gier) rzadko pojawia się w prawdziwym życiu. Irracjonalni gracze mogą w rzeczywistości uzyskać wyższe wypłaty, niż przewidywano przez indukcję wsteczną, jak pokazano w grze w stonogi.

W grze w stonogi dwóch graczy na przemian ma szansę wziąć większą część rosnącej puli pieniędzy lub przekazać pulę innemu graczowi. Wypłaty są ułożone w taki sposób, że jeśli pula zostanie przekazana przeciwnikowi, a przeciwnik weźmie pulę w następnej rundzie, otrzyma się nieco mniej, niż gdyby ktoś wziął pulę w tej rundzie. Gra kończy się, gdy tylko gracz zabierze skrytkę, przy czym ten gracz dostaje większą część, a drugi gracz mniejszą.

Przykład indukcji wstecznej

Na przykład załóżmy, że gracz A idzie pierwszy i musi zdecydować, czy powinien „wziąć”, czy „przekazać” skrytkę, która obecnie wynosi 2 $. Jeśli bierze, to A i B otrzymują po 1 $, ale jeśli A pasuje, decyzję o podjęciu lub spasowaniu musi teraz podjąć Gracz B. Jeśli B bierze, otrzymuje 3 $ (tj. Poprzednia skrytka w wysokości 2 $ + 1 $) a A dostaje 0 USD. Ale jeśli B spasuje, A teraz decyduje, czy wziąć, czy spasować, i tak dalej. Jeśli obaj gracze zawsze zdecydują się spasować, na koniec gry każdy z nich otrzyma wypłatę w wysokości 100 $.

Celem gry jest to, że jeśli A i B zarówno współpracują, jak i kontynuują spasowanie do końca gry, otrzymają maksymalną wypłatę w wysokości 100 $ każdy. Ale jeśli nie ufają drugiemu graczowi i oczekują, że „skorzystają” przy pierwszej okazji, równowaga Nasha przewiduje, że gracze otrzymają najniższe możliwe roszczenie (w tym przypadku 1 $).

Równowaga Nasha w tej grze, w której żaden gracz nie ma motywacji do odejścia od wybranej strategii po rozważeniu wyboru przeciwnika, sugeruje, że pierwszy gracz zgarnąłby pulę już w pierwszej rundzie gry. Jednak w rzeczywistości robi to stosunkowo niewielu graczy. W rezultacie uzyskują wyższą wypłatę niż wypłata przewidywana w analizie równowagi.

Rozwiązywanie gier sekwencyjnych z wykorzystaniem indukcji wstecznej

Poniżej znajduje się prosta gra sekwencyjna między dwoma graczami. Etykiety z Graczem 1 i Graczem 2 to zestawy informacji odpowiednio dla graczy pierwszego lub dwóch. Liczby w nawiasach na dole drzewka to wypłaty w każdym odpowiednim punkcie. Gra jest również sekwencyjna, więc Gracz 1 podejmuje pierwszą decyzję (w lewo lub w prawo), a Gracz 2 podejmuje decyzję po Graczu 1 (w górę lub w dół).

Indukcja wsteczna, podobnie jak wszystkie teorie gier, opiera się na założeniach racjonalności i maksymalizacji, co oznacza, że ​​Gracz 2 zmaksymalizuje swoją wypłatę w każdej sytuacji. W każdym zestawie informacji mamy dwie możliwości, w sumie cztery. Eliminując wybory, których Gracz 2 nie wybierze, możemy zawęzić nasze drzewo. W ten sposób zaznaczymy linie na niebiesko, które maksymalizują wypłatę gracza przy danym zestawie informacji.

Po tej redukcji Gracz 1 może zmaksymalizować swoje wypłaty teraz, gdy wybory Gracza 2 są znane. Rezultatem jest równowaga znaleziona przez wsteczne indukowanie gracza 1, który wybrał „prawo”, a gracz 2 „w górę”. Poniżej znajduje się rozwiązanie gry z pogrubioną ścieżką równowagi.

Na przykład, można łatwo ustawić grę podobną do tej powyżej, wykorzystując firmy jako graczy. Ta gra może zawierać scenariusze wydawania produktów. Gdyby Firma 1 chciała wypuścić produkt, co mogłaby zrobić Firma 2 w odpowiedzi? Czy Firma 2 wypuści podobny konkurencyjny produkt? Przez prognozowania sprzedaży tego nowego produktu w różnych scenariuszy, możemy założyć grę przewidzieć, w jaki sposób wydarzenia mogą rozwijać. Poniżej znajduje się przykład, jak można modelować taką grę.