The complexity of multi-mean-payoff and multi-energy games

DOI10.1016/j.ic.2015.03.001zbMath1309.68082arXiv1209.3234OpenAlexW1981015644MaRDI QIDQ2343132

Jean-François Raskin, Thomas A. Henzinger, Yaron Velner, Krishnendu Chatterjee, Alexander Rabinovich, Laurent Doyen

Publication date: 4 May 2015

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1209.3234

Mathematics Subject Classification ID

2-person games (91A05) Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (30)

Hyperplane separation technique for multidimensional mean-payoff games ⋮ Equilibria for games with combined qualitative and quantitative objectives ⋮ The Theory of Universal Graphs for Infinite Duration Games ⋮ Compositional strategy synthesis for stochastic games with multiple objectives ⋮ Extending finite-memory determinacy to multi-player games ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ Mean-payoff games with \(\omega\)-regular specifications ⋮ Average-energy games ⋮ Reachability games with relaxed energy constraints ⋮ Cooperative concurrent games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Energy Büchi problems ⋮ Subgame-perfect Equilibria in Mean-payoff Games (journal version) ⋮ Automated competitive analysis of real-time scheduling with graph games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Bounding Average-Energy Games ⋮ Deciding Fast Termination for Probabilistic VASS with Nondeterminism ⋮ Simple stochastic games with almost-sure energy-parity objectives are in NP and conp ⋮ Quantitative fair simulation games ⋮ Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games ⋮ Unnamed Item ⋮ Quantitative reductions and vertex-ranked infinite games ⋮ Robust Equilibria in Mean-Payoff Games ⋮ Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions

Cites Work

• Unnamed Item
• Polynomial-time algorithms for energy games with special weight structures
• Faster algorithms for mean-payoff games
• The directed subgraph homeomorphism problem
• Positional strategies for mean payoff games
• The complexity of stochastic games
• Borel determinacy
• A characterization of the minimum cycle mean in a digraph
• The complexity of mean payoff games on graphs
• Strategy synthesis for multi-dimensional quantitative objectives
• Concurrent games with tail objectives
• Hyperplane Separation Technique for Multidimensional Mean-Payoff Games
• Quantitative languages
• Energy Games in Multiweighted Automata
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• Mean-Payoff Automaton Expressions
• Z-Reachability Problem for Games on 2-Dimensional Vector Addition Systems with States Is in P
• Reachability Games on Extended Vector Addition Systems with States
• Half-Positional Determinacy of Infinite Games
• On Omega-Languages Defined by Mean-Payoff Conditions
• Supervisory Control of a Class of Discrete Event Processes
• Looking at Mean-Payoff and Total-Payoff through Windows
• Stochastic Games

This page was built for publication: The complexity of multi-mean-payoff and multi-energy games