Induzione a ritroso

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

L'induzione a ritroso (in inglese: backward induction) è un processo di ragionamento che va a ritroso nel tempo, dalla fine di un problema, allo scopo di determinare una sequenza di azioni ottimale. Si procede in primo luogo considerando l'ultima volta che una decisione può essere presa, individuando una scelta ottimale in quella situazione. Usando questa informazione, si può quindi stabilire che cosa fare in occasione della penultima azione e così via sino a quando, con questa a analisi a ritroso, non si è individuata una azione ottimale per ogni possibile situazione in qualsiasi punto nel tempo.

In teoria dei giochi, l'induzione a ritroso è stata per la prima volta impiegata da John von Neumann e Oskar Morgenstern nel loro lavoro fondatore: Teoria dei Giochi e comportamento economico (1944)[1]. In questo contesto, viene usata per calcolare l'equilibrio perfetto di un sotto-gioco (subgame perfect equilibria) in giochi sequenziali[2].

Per la programmazione dinamica, l'induzione a ritroso costituisce uno dei metodi principali per risolvere l'equazione di Bellman[3][4]. L'unica differenza fra l'uso in questi due campi, è che l'ottimizzazione coinvolge un solo giocatore, il quale seleziona l'azione da eseguire in ogni istante di tempo, quando la teoria dei giochi prevede l'interazione fra più giocator. Quindi, anticipando l'azione dell'ultimo igocatore in ogni situazione, è possibile determinare cosa farà il penultimo giocatore, e così via. Nei campi della pianificazione automatica o della dimostrazione automatica di teoremi, questo metodo è chiamato ricerca a ritroso (in inglese: backward search o backward chaining).

Note[modifica | modifica wikitesto]

  1. ^ (EN) John von Neumann e Oskar Morgenstern, Theory of Games and Economic Behavior, 3ª ed., Princeton University Press, 1953 [1944], Sezione 15.3.1..
  2. ^ (EN) Drew Fudenberg e Jean Tirole, Game Theory, Cambridge, USA, MIT Press, 1991, p. 92.
  3. ^ (EN) Jerome Adda e Russell Cooper, Dynamic Economics: Quantitative Methods and Applications, Cambridge, USA, MIT Press, 2003, p. 28.
  4. ^ (EN) Mario Miranda e Paul Fackler, Applied Computational Economics and Finance, Cambridge, USA, MIT Press, 2002, p. 164.