Cyclical games with prohibitions (Q689132): Difference between revisions

We consider a certain combinatorial game on a digraph for two cases of the price function. For one case the game in question extends the cyclical game studied by \textit{A. Ehrenfeucht} and \textit{J. Mycielski} [Int. J. Game Theory 8, 109-113 (1979; Zbl 0499.90098)] and \textit{V. A. Gurvich}, \textit{A. V. Karzanov} and \textit{L. G. Khachiyan} [USSR Comput. Math. Math. Phys. 28, No. 5, 85-91 (1988; Zbl 0695.90105)] which, in its turn, is a generalization of the well-known problem of finding a minimum mean cycle in an edge-weighted digraph. We prove the existence of optimal uniform stationary strategies for both cases and give algorithms to find such strategies.