Indukcja wsteczna

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Indukcja wsteczna (ang. backward induction) to iteracyjny proces stosowany w teorii gier i służący do rozwiązywania gier sekwencyjnych. Algorytm polega na wyznaczeniu najpierw optymalnej strategii dla gracza, który podejmuje decyzję jako ostatni. Następnie wyznaczana jest optymalna gracza, który wykonuje ruch jako przedostatni, traktując jako znaną wyznaczoną we wcześniejszej iteracji strategię ostatniego gracza. Proces ten jest kontynuowany do początku gry, aż ustalone zostaną optymalne strategie wszystkich graczy. Uzyskany w ten sposób profil strategii i związany z nim punkt równowagi określa się jako doskonałej równowagi Nasha w podgrach.

W programowaniu dynamicznym proces analogiczny do indukcji wstecznej jest podstawowym sposobem na rozwiązanie równania Bellmana.

Z pojęciem indukcji wstecznej związany jest również paradoks skazanego.

Linki zewnętrzne[edytuj | edytuj kod]