The complexity of mean payoff games
UNSPECIFIED (1995) The complexity of mean payoff games. In: 1st Annual International Computing and Combinatorics Conference (COCOON 95), XIAN, PEOPLES R CHINA, AUG 24-26, 1995. Published in: COMPUTING AND COMBINATORICS, 959 pp. 1-10.Full text not available from this repository.
We study the complexity of finding the values and optimal strategies of mean payoff games, a family of perfect information games introduced by Ehrenfeucht and Mycielski. We describe a pseudo-polynomial time algorithm for the solution of such games, the decision problem for which is in NP boolean AND co-NP. 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 co-NP, but no polynomial or pseudo-polynomial time algorithm is known for them.
|Item Type:||Conference Item (UNSPECIFIED)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Series Name:||LECTURE NOTES IN COMPUTER SCIENCE|
|Journal or Publication Title:||COMPUTING AND COMBINATORICS|
|Editor:||Du, DZ and Li, M|
|Number of Pages:||10|
|Page Range:||pp. 1-10|
|Title of Event:||1st Annual International Computing and Combinatorics Conference (COCOON 95)|
|Location of Event:||XIAN, PEOPLES R CHINA|
|Date(s) of Event:||AUG 24-26, 1995|
Actions (login required)