Gurvich, Vladimir Backward induction in presence of cycles. (English) Zbl 1420.91029 J. Log. Comput. 28, No. 7, 1635-1646 (2018). Summary: For the classical backward induction algorithm, the input is an arbitrary \(n\)-person positional game with perfect information modelled by a finite acyclic directed graph (digraph) and the output is a profile \((x_1, \dots , x_n)\) 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\) 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\) 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. Cited in 1 Document MSC: 91A43 Games involving graphs 91A20 Multistage and repeated games 91A24 Positional games (pursuit and evasion, etc.) 05C20 Directed graphs (digraphs), tournaments Keywords:deterministic graphical (multistage) game; game in normal and in positional form; saddle point; Nash equilibrium; Nash-solvability; game form; positional structure; directed graph; digraph; directed cycle; acyclic digraph PDFBibTeX XMLCite \textit{V. Gurvich}, J. Log. Comput. 28, No. 7, 1635--1646 (2018; Zbl 1420.91029) Full Text: DOI arXiv