UNSPECIFIED (1995) The complexity of mean payoff games. In: 1st Annual International Computing and Combinatorics Conference (COCOON 95), AUG 24-26, 1995, XIAN, PEOPLES R CHINA.

Full text not available from this repository.

Abstract

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
Publisher:	SPRINGER-VERLAG BERLIN
ISBN:	3-540-60216-X
ISSN:	0302-9743
Editor:	Du, DZ and Li, M
Date:	1995
Volume:	959
Number of Pages:	10
Page Range:	pp. 1-10
Publication Status:	Published
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
URI:	http://wrap.warwick.ac.uk/id/eprint/19059

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item