Mean Cost Cyclical Games

Abstract
We study the mean cost cyclical game in a more general setting than that in Gurvitch et al. (1988) and Karzanow and Lebedev (1993). The game is played on a directed graph and generalizes the single source shortest path problem, the minimum mean cycle problem (see Karp 1978), and the ergodic extension of matrix games (Moulin 1976). We prove the existence of a solution in uniform stationary strategies and present an algorithm for finding such optimal strategies. In fact, our algorithm is an extension of the algorithms due to Gurvitch et al. (1988) and Karzanow and Lebedev (1993), which were proved to be finite, but exponential in the worst case. We prove that all these algorithms are pseudopolynomial.

This publication has 6 references indexed in Scilit: