Induzione a ritroso
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 un'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ù giocatori. Quindi, anticipando l'azione dell'ultimo giocatore 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
- ^ (EN) John von Neumann e Oskar Morgenstern, Theory of Games and Economic Behavior, 3ª ed., Princeton University Press, 1953 [1944], Sezione 15.3.1..
- ^ (EN) Drew Fudenberg e Jean Tirole, Game Theory, Cambridge, USA, MIT Press, 1991, p. 92.
- ^ (EN) Jerome Adda e Russell Cooper, Dynamic Economics: Quantitative Methods and Applications, Cambridge, USA, MIT Press, 2003, p. 28.
- ^ (EN) Mario Miranda e Paul Fackler, Applied Computational Economics and Finance, Cambridge, USA, MIT Press, 2002, p. 164.
V · D · M | |
---|---|
Definizioni | Gioco in forma normale · Gioco in forma estesa · Gioco cooperativo · Insieme informativo · Preferenza · Payoff · Belief · Best response · Gioco equo |
Soluzioni di Equilibrio | Equilibrio di Nash · Equilibrio bayesiano · Equilibrio bayesiano perfetto (EBP) · Ottimo paretiano |
Strategie | Strategie dominanti · Strategia pura · Strategia mista · Trigger strategy · Collusione tacita · Induzione a ritroso · Tit for tat |
Classi di giochi | Gioco a informazione completa · Gioco statico · Gioco dinamico o sequenziale · Gioco ripetuto · Gioco di segnalazione · Gioco a somma zero |
Giochi | Dilemma del prigioniero · Dilemma del viaggiatore · Gioco del pollo · Dilemma del volontario · Battaglia dei sessi · Caccia al cervo · Matching pennies · Gioco dell'ultimatum · Morra cinese · Oligopolio di Cournot · Duopolio di Stackelberg · Modello di Bertrand · Gioco del centipede |
Teoremi | Teorema minimax · Teorema dell'impossibilità di Arrow |