The complexity of mean payoff games on graphs
UNSPECIFIED. (1996) The complexity of mean payoff games on graphs. THEORETICAL COMPUTER SCIENCE, 158 (1-2). pp. 343-359. ISSN 0304-3975Full text not available from this repository.
We study the complexity of finding the values and optimal strategies of mean payoff games on graphs, a family of perfect information games introduced by Ehrenfeucht and Mycielski and considered by Gurvich, Karzanov and Khachiyan. We describe a pseudo-polynomial-time algorithm for the solution of such games, the decision problem for which is in NP boolean AND coNP. Finally, we describe a polynomial reduction from mean payoff games to the simple stochastic games studied by Condon. These games are also known to be in NP boolean AND coNP, but no polynomial or pseudo-polynomial-time algorithm is known for them.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Journal or Publication Title:||THEORETICAL COMPUTER SCIENCE|
|Publisher:||ELSEVIER SCIENCE BV|
|Official Date:||20 May 1996|
|Number of Pages:||17|
|Page Range:||pp. 343-359|
Actions (login required)