Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR95-040 | 26th July 1995 00:00

The complexity of mean payoff games on graphs


Authors: Uri Zwick, Michael S. Paterson
Publication: 31st July 1995 10:27
Downloads: 3525


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