Computational Playability of Backward Induction Solutions
Hidetoshi Tashiro · Institutional Repositories DataBase (IRDB) · 1997
This paper considers the computational playability of backward induction solutions, $i.e$ .whether or not there is an algorithm to play them.We construct a two-person two-stage game with perfect information, in which both players have countably many feasible actions and their payoff functions are computable.We prove that the backward induction solutions of the game, which are proved to exist, are not computably playable because it is impossible to supply the players with algorithms regarding how they should play the solutions.Moreover, we show that if players' payoff functions are polynomial with rational coefficients, then the backward induction solutions are computably playable.