Fordított indukció

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2017. július 11-én felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A fordított indukció az optimális műveletsor megtalálásának módszere. Fordított kronológiát feltételez: először az utolsó lépésben az optimális műveletet határozzák meg, majd az előző optimumot. Kiderül az utolsó művelet, amelyet a játék legelején végre kell hajtani. Az eljárás mindaddig folytatódik, amíg meg nem találjuk az optimumot az egyes információhalmazokban , vagyis minden egyes játékhelyzetben, amely a játékos számára elérhető.

A matematikai optimalizálás , pontosabban a dinamikus programozás szempontjából a visszafelé indukció az egyik módszer a Bellman-egyenlet [1] [2] megoldására . A játékelméletben lehetővé teszi a tökéletes egyensúly megtalálását egy szekvenciális játék részjátékaiban [3] . Az egyensúly megtalálásához minden játékos optimális stratégiáinak jellemzésére van szükség, azaz minden egyes fára visszafelé indukciót kell alkalmazni, vagy általános fát kell építeni. Az automatikus ütemezésben és feladásban , valamint az automatikus tételbizonyításban a visszafelé indukciós módszert "visszafelé keresésnek" vagy "visszamenő következtetésnek" nevezik. A sakk terminológiájában a visszafelé indukciót retrográd elemzésnek nevezik .

A visszafelé irányuló indukció egyidős, mint maga a játékelmélet. John von Neumann és Oskar Morgenstern használta az antagonisztikus játékok megoldására . A Theory of Games and Economic Behavior (1944) című munkájukat a játékelmélet alapszövegének tekintik [4] [5] .

Lásd még

Jegyzetek

  1. ↑ Jerome Adda és Russell Cooper, „Dynamic Economics: Quantitative Methods and Applications”, 3.2.1. szakasz, 28. oldal. MIT Press, 2003.
  2. ↑ Mario Miranda és Paul Fackler, "Alkalmazott számítástechnikai közgazdaságtan és pénzügyek", 7.3.1. szakasz, 164. oldal. MIT Press, 2002.
  3. ↑ Drew Fudenberg és Jean Tirole, "Játékelmélet", 3.5. szakasz, 92. oldal. MIT Press, 1991.
  4. ↑ John von Neumann és Oskar Morgenstern, "Játékelmélet és gazdasági viselkedés", 15.3.1. szakasz. Princeton University Press. (Első kiadás, 1944.)
  5. ↑ Mathematics of Chess Archiválva : 2017. november 12. a The Wayback Machine webhelyen, John MacQuarrie weboldala.