Käänteinen induktio

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 11. heinäkuuta 2017 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Käänteinen induktio on menetelmä optimaalisen toimintosarjan löytämiseksi. Oletuksena käänteinen kronologia: optimaalinen toiminta viimeisessä vaiheessa määritetään ensin, sitten määritetään aiemmat optimit. Viimeinen toiminto, joka tulisi suorittaa heti pelin alussa, paljastetaan. Toimenpide jatkuu, kunnes jokaisesta tietojoukosta löytyy optimi , eli kussakin pelitilanteessa, joka on pelaajan havaittavissa.

Matemaattisen optimoinnin , tarkemmin sanottuna dynaamisen ohjelmoinnin, näkökulmasta taaksepäin induktio on yksi Bellman-yhtälön [1] [2] ratkaisumenetelmistä . Peliteoriassa se mahdollistaa täydellisen tasapainon löytämisen peräkkäisen pelin alipeleissä [3] . Tasapainon löytämiseksi on tarpeen karakterisoida kaikkien pelaajien optimaaliset strategiat, toisin sanoen soveltaa taaksepäin induktiota jokaiseen yksittäiseen puuhun tai rakentaa yleinen puu. Automaattisessa aikataulutuksessa ja lähettämisessä sekä automaattisessa lauseen todistamisessa taaksepäin induktiomenetelmää kutsutaan "takaisinhakuksi" tai "taaksepäätelmäksi". Shakkiterminologiassa taaksepäin induktiota kutsutaan retrogradiseksi analyysiksi .

Taaksepäin induktio on yhtä vanha kuin peliteoria itse. John von Neumann ja Oskar Morgenstern käyttivät sitä vastakkaisten pelien ratkaisemiseen . Heidän työnsä Theory of Games and Economic Behavior (1944) pidetään peliteorian perustana [4] [5] .

Katso myös

Muistiinpanot

  1. ↑ Jerome Adda ja Russell Cooper, "Dynamic Economics: Quantitative Methods and Applications", jakso 3.2.1, sivu 28. MIT Press, 2003.
  2. ↑ Mario Miranda ja Paul Fackler, "Applied Computational Economics and Finance", jakso 7.3.1, sivu 164. MIT Press, 2002.
  3. ↑ Drew Fudenberg ja Jean Tirole, "Peliteoria", jakso 3.5, sivu 92. MIT Press, 1991.
  4. ↑ John von Neumann ja Oskar Morgenstern, "Pelien teoria ja taloudellinen käyttäytyminen", jakso 15.3.1. Princeton University Press. (Ensimmäinen painos, 1944.)
  5. ↑ Mathematics of Chess Arkistoitu 12. marraskuuta 2017 the Wayback Machine , verkkosivun kirjoittaja John MacQuarrie.