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] .
Spilteori | |
---|---|
Basale koncepter | |
Typer af spil |
|
Løsningskoncepter | |
Eksempler på spil | |