Mean cost cyclical games

• 成果类型: Article
• 署名作者: Pisaruk, NN
• 署名单位: Belarusian State University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.24.4.817
• 发表日期: 1999
• 页码: 817-828
• 关键词: graphs

摘要

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.