Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-040 | 26th July 1995 00:00

The complexity of mean payoff games on graphs

RSS-Feed




TR95-040
Authors: Uri Zwick, Michael S. Paterson
Publication: 31st July 1995 10:27
Downloads: 2275
Keywords: 


Abstract:

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\,\cap\,\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\,\cap\,\coNP$, but no
polynomial or pseudo-polynomial time algorithm is known for them.

This is the full version of the paper. An extended abstract
version of the paper will appear in the proceedings COCOON'95.



ISSN 1433-8092 | Imprint