Hyperplane separation technique for multidimensional mean-payoff games Journal Article

Author(s): Chatterjee, Krishnendu; Velner, Yaron
Article Title: Hyperplane separation technique for multidimensional mean-payoff games
Affiliation IST Austria
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.
Keywords: mean-payoff objectives; Cumputer-aided verification; Finite-state graph games; Multidimensional objectives; Pushdown graphs and games
Journal Title: Journal of Computer and System Sciences
Volume: 88
ISSN: 1090-2724
Publisher: Academic Press  
Date Published: 2017-09-01
Start Page: 236
End Page: 259
DOI: 10.1016/j.jcss.2017.04.005
Notes: The research was supported by Austrian Science Fund (FWF) Grant No. P 23499-N23, FWF NFN Grant No. S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), Microsoft faculty fellows award, the RICH Model Toolkit (ICT COST Action IC0901), and was carried out in partial fulfillment of the requirements for the Ph.D. degree of the second author.
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work