Abstract: Computing best responses is essential to strategy evaluation in game theory, yet general algorithms for imperfect-information extensive-form games suffer from exponential complexity. For games with perfect recall, Von Stengel (1996) established that best responses can be computed in linear time through a sequence-form linear program, which implicitly performs backward induction—though this connection remains indirect and embedded within abstract LP machinery. This paper provides an explicit, constructive proof that backward induction directly computes best responses in imperfect-information games with perfect recall. We introduce counterfactual best response values as the core inductive quantity and prove they satisfy a recursive relationship aligned with the game tree structure. This enables a direct backward induction algorithm that traverses information sets from leaves to root, making optimal action selections based on local subtree computations. Our approach unifies the computational procedure with its theoretical justification, offering a more intuitive, tree-structured alternative to LP-based methods while maintaining O(n) time complexity. This work clarifies the fundamental connection between backward induction and best response computation in imperfect-information settings.

Key words: best response, imperfect-information games, backward induction, counterfactual best response, perfect recall