Robust multidimensional mean-payoff games are undecidable

DOI10.1007/978-3-662-46678-0_20MaRDI QIDQ2949447zbMATH OpenOpenAlexFDO

Authors Yaron Velner

Publication date 1 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Games involving graphs (91A43)

Abstract: Mean-payoff games play a central role in quantitative synthesis and verification. In a single-dimensional game a weight is assigned to every transition and the objective of the protagonist is to assure a non-negative limit-average weight. In the multidimensional setting, a weight vector is assigned to every transition and the objective of the protagonist is to satisfy a boolean condition over the limit-average weight of each dimension, e.g., $LimAvg(x_1)leq0veeLimAvg(x_2)geq0wedgeLimAvg(x_3)geq0$. We recently proved that when one of the players is restricted to finite-memory strategies then the decidability of determining the winner is inter-reducible with Hilbert's Tenth problem over rationals (a fundamental long-standing open problem). In this work we allow arbitrary (infinite-memory) strategies for both players and we show that the problem is undecidable.

Recommendations

• Finite-memory strategy synthesis for robust multidimensional mean-payoff objectives
• The complexity of multi-mean-payoff and multi-energy games
• Hyperplane Separation Technique for Multidimensional Mean-Payoff Games
• Looking at mean-payoff and total-payoff through windows
• Looking at mean-payoff and total-payoff through windows

Cited in

(9)

• On decidability and complexity of low-dimensional robot games
• Hyperplane separation technique for multidimensional mean-payoff games
• Robust equilibria in mean-payoff games
• On the complexity of heterogeneous multidimensional games
• Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions
• Looking at mean-payoff and total-payoff through windows
• Quantitative fair simulation games
• Energy mean-payoff games
• Stochastic games with disjunctions of multiple objectives

This page was built for publication: Robust multidimensional mean-payoff games are undecidable

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