Backward induction in presence of cycles

Journal of Logic and Computation. 2018. Vol. 28. No. 7. P. 1635–1646.

Gurvich V.

For the classical backward induction algorithm, the input is an arbitrary n n -person positional game with perfect information modelled by a finite acyclic directed graph (digraph) and the output is a profile (x 1 ,…,x n ) (x1,…,xn) of pure positional strategies that form some special subgame perfect Nash equilibrium (NE). We extend this algorithm to work with digraphs that may have directed cycles. Each digraph admits a unique partition into strongly connected (SC) components, which will be treated as the outcomes of a game. Such games will be called deterministic graphical multistage (DGMS) games. If we merge the outcomes corresponding to all SC components, except terminals, we obtain the so-called deterministic graphical (DG) games, which are frequent in the literature. The outcomes of a DG game are all terminals and one special outcome c c that is assigned to all infinite plays. We modify the backward induction procedure to adapt it for the DG and DGMS games. Yet, we have to pay the price for this extension. The new algorithm always outputs an NE only when n=2 n=2 and, even in this case, the obtained NE may be not subgame perfect. (Although in the zero-sum case it is.) The lack of these two properties is not a fault of the algorithm, just (subgame perfect) NEs in pure positional strategies may fail to exist in the considered game.

Keywords: digraph, Nash equilibrium, Nash-solvability, game in normal and in positional form, deterministic graphical (multistage) game, saddle point, game form, positional structure, directed graph, directed cycle, acyclic digraph

Publication based on the results of: Теоретическая информатика (2018)