Criterion and test for ergodicity of cyclic game forms. (Russian) Zbl 0671.90101
Two-person cyclic games with perfect information are considered. This notion generalizes that of a controllable Markov process with payoffs. A cyclic game form is called ergodic if, using any payoff function, the value of the obtained cyclic game does not depend on the initial position.
The following simple criterion holds: A cyclic game form is not ergodic if and only if its graph G can be split into two subgraphs \(G_ 1\), \(G_ 2\) in such a way that
Player 1 has no moves from \(G_ 2\) to \(G_ 1,\)
Player 2 has no moves from \(G_ 1\) to \(G_ 2,\)
both graphs \(G_ 1\) and \(G_ 2\) have no dead-lock positions; i.e. player 1 (resp. 2) is able “to lock” player 2 (resp. 1) inside \(G_ 1\) (resp. \(G_ 2).\)
It is shown also that the problem to test whether a cyclic game form is ergodic or not is NP-complete. The article is closely related to previous work of the first author [ibid. 43, No.2(260), 135-136 (1988; Zbl 0652.90101)].
The following simple criterion holds: A cyclic game form is not ergodic if and only if its graph G can be split into two subgraphs \(G_ 1\), \(G_ 2\) in such a way that
Player 1 has no moves from \(G_ 2\) to \(G_ 1,\)
Player 2 has no moves from \(G_ 1\) to \(G_ 2,\)
both graphs \(G_ 1\) and \(G_ 2\) have no dead-lock positions; i.e. player 1 (resp. 2) is able “to lock” player 2 (resp. 1) inside \(G_ 1\) (resp. \(G_ 2).\)
It is shown also that the problem to test whether a cyclic game form is ergodic or not is NP-complete. The article is closely related to previous work of the first author [ibid. 43, No.2(260), 135-136 (1988; Zbl 0652.90101)].
Reviewer: V.A.Gurvich
