Inductie inversa

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 11 iulie 2017; verificările necesită 3 modificări .

Inducția inversă este o metodă de găsire a secvenței optime de acțiuni. Presupune o cronologie inversă: se determină mai întâi acțiunea optimă la ultimul pas, apoi se determină optimele anterioare. Ultima acțiune care ar trebui efectuată chiar la începutul jocului este dezvăluită. Procedura continuă până când optimul este găsit în fiecare dintre seturile de informații , adică în fiecare dintre situațiile de joc disponibile pentru percepție de către jucător.

Din punct de vedere al optimizării matematice , mai precis al programării dinamice, inducerea înapoi este una dintre metodele de rezolvare a ecuației Bellman [1] [2] . În teoria jocurilor, permite găsirea unui echilibru perfect în sub-jocuri ale unui joc secvenţial [3] . Pentru a găsi un echilibru, este necesar să se caracterizeze strategiile optime ale tuturor jucătorilor, adică să se aplice o inducție inversă fiecărui arbore individual sau să se construiască un arbore general. În programarea și expedierea automată și demonstrarea automată a teoremei , metoda de inducție inversă se numește „căutare înapoi” sau „inferență înapoi”. În terminologia șahului , inducția inversă se numește analiză retrogradă .

Inducerea înapoi este la fel de veche ca teoria jocurilor în sine. John von Neumann și Oskar Morgenstern l-au folosit pentru a rezolva jocuri antagoniste . Lucrarea lor Theory of Games and Economic Behavior (1944) este considerată textul fondator al teoriei jocurilor [4] [5] .

Vezi și

Note

  1. ^ Jerome Adda și Russell Cooper, „Dynamic Economics: Quantitative Methods and Applications”, Secțiunea 3.2.1, pagina 28. MIT Press, 2003.
  2. ↑ Mario Miranda și Paul Fackler, „Applied Computational Economics and Finance”, Secțiunea 7.3.1, pagina 164. MIT Press, 2002.
  3. ^ Drew Fudenberg și Jean Tirole , „Game Theory”, Secțiunea 3.5, pagina 92. MIT Press, 1991.
  4. ↑ John von Neumann și Oskar Morgenstern, „Theory of Games and Economic Behavior”, Secțiunea 15.3.1. Princeton University Press. (Prima ediție, 1944.)
  5. ↑ Mathematics of Chess Arhivat 12 noiembrie 2017 la Wayback Machine , pagina web de John MacQuarrie.