Mean cost cyclical games (Q2757610)

The author studies a two-player game on a graph where each arc has associated a cost, and one player moves a chip along the graph to minimize average cost, while the other tries to maximize this cost by forbidding directions out of the vertex where the chip is. The game had been studied by \textit{A. V. Karzanov} and \textit{V. N. Lebedev} [Math. Program. 60A, 277-293 (1993; Zbl 0781.90109)]. The present paper contributes to this line by finding a solution in uniform stationary strategies and an algorithm to compute the optimal strategies whose complexity is pseudopolynomial.