---
res:
bibo_abstract:
- 'We consider finite-state and recursive game graphs with multidimensional mean-payoff
objectives. In recursive games two types of strategies are relevant: global strategies
and modular strategies. Our contributions are: (1) We show that finite-state multidimensional
mean-payoff games can be solved in polynomial time if the number of dimensions
and the maximal absolute value of weights are fixed; whereas for arbitrary dimensions
the problem is coNP-complete. (2) We show that one-player recursive games with
multidimensional mean-payoff objectives can be solved in polynomial time. Both
above algorithms are based on hyperplane separation technique. (3) For recursive
games we show that under modular strategies the multidimensional problem is undecidable.
We show that if the number of modules, exits, and the maximal absolute value of
the weights are fixed, then one-dimensional recursive mean-payoff games under
modular strategies can be solved in polynomial time, whereas for unbounded number
of exits or modules the problem is NP-hard.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Yaron
foaf_name: Velner, Yaron
foaf_surname: Velner
bibo_doi: 10.1016/j.jcss.2017.04.005
bibo_volume: 88
dct_date: 2017^xs_gYear
dct_language: eng
dct_publisher: Academic Press@
dct_title: Hyperplane separation technique for multidimensional mean-payoff games@
...