Omvendt induktion

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 11. juli 2017; checks kræver 3 redigeringer .

Omvendt induktion er en metode til at finde den optimale rækkefølge af handlinger. Antager en omvendt kronologi: den optimale handling ved det sidste trin bestemmes først, derefter bestemmes de foregående optimum. Den sidste handling, der skal udføres i begyndelsen af ​​spillet, afsløres. Proceduren fortsætter, indtil det optimale er fundet i hvert af informationssættene , det vil sige i hver af de spilsituationer, der er tilgængelige for perception af spilleren.

Fra synspunktet om matematisk optimering , mere præcist dynamisk programmering, er baglæns induktion en af ​​metoderne til at løse Bellman-ligningen [1] [2] . I spilteorien tillader det at finde en perfekt ligevægt i underspil af et sekventielt spil [3] . For at finde en ligevægt er det nødvendigt at karakterisere de optimale strategier for alle spillere, det vil sige at anvende baglæns induktion på hvert af de individuelle træer, eller konstruere et generelt træ. I automatisk planlægning og afsendelse og automatisk teorembeviser kaldes baglæns induktionsmetoden "bagudsøgning" eller "tilbageudledning". I skakterminologi kaldes baglæns induktion retrograd analyse .

Baglæns induktion er lige så gammel som spilteorien selv. John von Neumann og Oskar Morgenstern brugte det til at løse antagonistiske spil . Deres arbejde Theory of Games and Economic Behavior (1944) betragtes som den grundlæggende tekst i spilteorien [4] [5] .

Se også

Noter

  1. Jerome Adda og Russell Cooper, "Dynamic Economics: Quantitative Methods and Applications", Afsnit 3.2.1, side 28. MIT Press, 2003.
  2. Mario Miranda og Paul Fackler, "Applied Computational Economics and Finance", afsnit 7.3.1, side 164. MIT Press, 2002.
  3. Drew Fudenberg og Jean Tirole, "Game Theory", afsnit 3.5, side 92. MIT Press, 1991.
  4. John von Neumann og Oskar Morgenstern, "Theory of Games and Economic Behavior", afsnit 15.3.1. Princeton University Press. (Første udgave, 1944.)
  5. Mathematics of Chess Arkiveret 12. november 2017 på Wayback Machine , webside af John MacQuarrie.