Inducció cap enrere
La inducció cap enrere és el procés de raonament enrere en el temps, des del final d'un problema o situació, per determinar una seqüència d'accions òptimes. Es procedeix examinant l'últim punt en què s'ha de prendre una decisió i després identificar quina acció seria la més òptima en aquell moment. Amb aquesta informació, es pot determinar què fer en el penúltim moment de la decisió. Aquest procés continua cap enrere fins que s'ha determinat la millor acció per a cada situació possible (és a dir, per a cada conjunt d'informació possible) en cada moment. La inducció cap enrere va ser utilitzada per primera vegada el 1875 per Arthur Cayley, que va descobrir el mètode mentre intentava resoldre el famós problema del Secretari.[1]
En el mètode d'optimització matemàtica de la programació dinàmica, la inducció cap enrere és un dels principals mètodes per resoldre l'equació de Bellman.[2][3] En teoria de jocs, la inducció cap enrere és un mètode utilitzat per calcular els equilibris perfectes de subjocs en jocs seqüencials.[4] L'única diferència és que l'optimització només implica un encarregat de prendre les decisions, que tria què fer en cada moment, mentre que la teoria de jocs analitza com interactuen les decisions de diversos jugadors. És a dir, anticipant què farà l'últim jugador en cada situació, és possible determinar què farà el penúltim jugador, etc. En els camps relacionats de la planificació i programació automatitzada i la demostració de teoremes automatitzats, el mètode s'anomena recerca cap enrere o encadenat cap enrere. Als escacs s'anomena anàlisi retrògrada.
La inducció cap enrere s'ha utilitzat per resoldre jocs sempre que existeix el camp de la teoria de jocs. John von Neumann i Oskar Morgenstern van suggerir resoldre jocs de suma zero i de dues persones per inducció cap enrere a la seva Teoria dels jocs i el comportament econòmic (1944), el llibre que va establir la teoria de jocs com a camp d'estudi.[5][6]
Referències
[modifica]- ↑ Rust, John. Dynamic Programming (en anglès). The New Palgrave Dictionary of Economics: Palgrave Macmillan, 9 September 2016. ISBN 978-1-349-95121-5.
- ↑ Jerome Adda and Russell Cooper, "Dynamic Economics: Quantitative Methods and Applications", Section 3.2.1, page 28. MIT Press, 2003.
- ↑ Mario Miranda and Paul Fackler, "Applied Computational Economics and Finance", Section 7.3.1, page 164. MIT Press, 2002.
- ↑ Drew Fudenberg and Jean Tirole, "Game Theory", Section 3.5, page 92. MIT Press, 1991.
- ↑ Mathematics of Chess, webpage by John MacQuarrie.
- ↑ John von Neumann and Oskar Morgenstern, "Theory of Games and Economic Behavior", Section 15.3.1. Princeton University Press. Third edition, 1953. (First edition, 1944.)