On the complexity of heterogeneous multidimensional games

DOI10.4230/LIPICS.CONCUR.2016.11MaRDI QIDQ4608663zbMATH OpenOpenAlexFDO

Authors Véronique Bruyère, Quentin Hautem, Jean-François Raskin

Publication date 21 March 2018

Full work available at URL https://dblp.uni-trier.de/db/conf/concur/concur2016.html#BruyereHR16

zbMATH Keywords

multidimensional heterogeneous objectivesquantitative objectivestwo-player zero-sum games played on graphs

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43)

Recommendations

• Looking at mean-payoff and total-payoff through windows
• Looking at mean-payoff and total-payoff through windows
• The complexity of multi-mean-payoff and multi-energy games
• Robust multidimensional mean-payoff games are undecidable
• Hyperplane Separation Technique for Multidimensional Mean-Payoff Games

Cited in

(13)

• Computational complexity in additive hedonic games
• \(N\)-dimensional Blotto game with heterogeneous battlefield values
• Precise complexity of the core in dichotomous and additive hedonic games
• Timed games with bounded window parity objectives
• On the Complexity of n-Player Hackenbush
• Parameterized complexity of games with monotonically ordered \(\omega\)-regular objectives
• Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions
• Life is random, time is not: Markov decision processes with window objectives
• Energy mean-payoff games
• Stackelberg-Pareto synthesis
• Stochastic window mean-payoff games
• Reachability games and friends: a journey through the Lens of memory and complexity (invited talk)
• Stochastic window mean-payoff games

This page was built for publication: On the complexity of heterogeneous multidimensional games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608663)