Mean Cost Cyclical Games
作者： N. N. Pisaruk
关键词: Game theory 、 Extension (predicate logic) 、 Directed graph 、 Combinatorial game theory 、 Combinatorics 、 Matrix games 、 Shortest path problem 、 Ergodic theory 、 Mathematics 、 Exponential function
摘要: We study the mean cost cyclical game in a more general setting than that Gurvitch et al. 1988 and Karzanow Lebedev 1993. The is played on directed graph generalizes single source shortest path problem, minimum cycle problem see Karp 1978, ergodic extension of matrix games Moulin 1976. prove existence solution uniform stationary strategies present an algorithm for finding such optimal strategies. In fact, our algorithms due to 1993, which were proved be finite, but exponential worst case. all these are pseudopolynomial.
sci-hub.se 参考文章(6)
Herve Moulin, Prolongement des jeux à deux joueurs de somme nulle. Une théorie abstraite des duels Mémoires de la Société mathématique de France. ,vol. 45, pp. 5- 111 ,(1976) , 10.24033/MSMF.180
A. Ehrenfeucht, J. Mycielski, Positional strategies for mean payoff games International Journal of Game Theory. ,vol. 8, pp. 109- 113 ,(1979) , 10.1007/BF01768705
V.A. Gurvich, A.V. Karzanov, L.G. Khachivan, Cyclic games and an algorithm to find minimax cycle means in directed graphs Ussr Computational Mathematics and Mathematical Physics. ,vol. 28, pp. 85- 91 ,(1990) , 10.1016/0041-5553(88)90012-2
Uri Zwick, Mike Paterson, The complexity of mean payoff games on graphs Theoretical Computer Science. ,vol. 158, pp. 343- 359 ,(1996) , 10.1016/0304-3975(95)00188-3
Alexander V. Karzanov, Vasilij N. Lebedev, Cyclical games with prohibitions Mathematical Programming. ,vol. 60, pp. 277- 293 ,(1993) , 10.1007/BF01580616
Richard M. Karp, A characterization of the minimum cycle mean in a digraph Discrete Mathematics. ,vol. 23, pp. 309- 311 ,(1978) , 10.1016/0012-365X(78)90011-0