Reverzní indukce

Reverzní indukce je metoda pro nalezení optimálního sledu akcí. Předpokládá obrácenou chronologii: nejprve se určí optimální akce v posledním kroku, poté se určí předchozí optima. Poslední akce, která by měla být provedena na samém začátku hry, je odhalena. Procedura pokračuje, dokud se nenajde optimum v každé z informačních sad , tedy v každé z herních situací dostupných pro vnímání hráčem.

Z hlediska matematické optimalizace , přesněji dynamického programování, je zpětná indukce jednou z metod řešení Bellmanovy rovnice [1] [2] . V teorii her umožňuje najít dokonalou rovnováhu v dílčích hrách sekvenční hry [3] . K nalezení rovnováhy je nutné charakterizovat optimální strategie všech hráčů, tedy aplikovat zpětnou indukci na každý z jednotlivých stromů, nebo sestrojit obecný strom. V automatickém plánování a odesílání a automatickém dokazování teorémů se metoda zpětné indukce nazývá „zpětné vyhledávání“ nebo „zpětná inference“. V šachové terminologii se zpětná indukce nazývá retrográdní analýza .

Zpětná indukce je stará jako teorie her sama. John von Neumann a Oskar Morgenstern jej používali k řešení antagonistických her . Jejich práce Theory of Games and Economic Behavior (1944) je považována za zakládající text teorie her [4] [5] .

Viz také

• Paradox náhlé popravy

Poznámky

1. ↑ Jerome Adda a Russell Cooper, „Dynamická ekonomie: kvantitativní metody a aplikace“, oddíl 3.2.1, strana 28. MIT Press, 2003.
2. ↑ Mario Miranda a Paul Fackler, „Aplikovaná výpočetní ekonomie a finance“, oddíl 7.3.1, strana 164. MIT Press, 2002.
3. ↑ Drew Fudenberg a Jean Tirole, "Teorie her", oddíl 3.5, strana 92. MIT Press, 1991.
4. ↑ John von Neumann a Oskar Morgenstern, „Teorie her a ekonomické chování“, oddíl 15.3.1. Princeton University Press. (První vydání, 1944.)
5. ↑ Mathematics of Chess Archived 12. listopadu 2017 na Wayback Machine , webová stránka od Johna MacQuarrieho.