Qualitative analysis of concurrent mean-payoff games
From MaRDI portal
Publication:2346403
DOI10.1016/J.IC.2015.03.009zbMATH Open1318.91039arXiv1409.5306OpenAlexW2041261743MaRDI QIDQ2346403FDOQ2346403
Authors: Krishnendu Chatterjee, Rasmus Ibsen-Jensen 
Publication date: 1 June 2015
Published in: Information and Computation (Search for Journal in Brave)
Abstract: We consider concurrent games played by two-players on a finite-state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study a fundamental objective, namely, mean-payoff objective, where a reward is associated to each transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite. The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it; or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show that for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies, or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imply a solution to a long-standing open problem (the value problem for turn-based deterministic mean-payoff games) that is not known to be solvable in polynomial time.
Full work available at URL: https://arxiv.org/abs/1409.5306
Recommendations
Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Games involving graphs (91A43)
Cites Work
- The complexity of stochastic games
- The complexity of mean payoff games on graphs
- Stochastic Games
- Title not available (Why is that?)
- Alternating-time temporal logic
- Title not available (Why is that?)
- Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification
- An \(O(n^2)\) time algorithm for alternating Büchi games
- Stochastic games
- Title not available (Why is that?)
- The Asymptotic Theory of Stochastic Games
- The Big Match
- What is decidable about partially observable Markov decision processes with omega-regular objectives
- Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study
- Probabilistic ω-automata
- The complexity of partial-observation stochastic parity games with finite-memory strategies
- Concurrent reachability games
- Positional strategies for mean payoff games
- Cyclic games and an algorithm to find minimax cycle means in directed graphs
- Better Quality in Synthesis through Quantitative Objectives
- Optimal control of diffusion processes with reflection
- Partial-observation stochastic games, how to win when belief fails
- Stochastic Games with Perfect Information and Time Average Payoff
- Recursive Concurrent Stochastic Games
- Title not available (Why is that?)
- Solving partial-information stochastic parity games
- Repeated games with absorbing states
- On Nonterminating Stochastic Games
- Automata, Languages and Programming
- Qualitative reachability in stochastic BPA games
- Quantitative languages
- Concurrent games with tail objectives
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computer Science Logic
- Stochastic limit-average games are in EXPTIME
- Algorithms for Omega-Regular Games with Imperfect Information
- Faster algorithms for mean-payoff games
- Weighted automata and weighted MSO logics for average and long-time behaviors
- Decidable problems for probabilistic automata on infinite words
- Deciding the value 1 problem for probabilistic leaktight automata
- Synthesis from LTL specifications with mean-payoff objectives
- Code aware resource management
- Qualitative concurrent parity games
- Qualitative concurrent parity games: bounded rationality
- Exact algorithms for solving stochastic games
Cited In (20)
- Automata-based controller synthesis for stochastic systems: a game framework via approximate probabilistic relations
- On concurrent games with payoff
- Robust equilibria in mean-payoff games
- Concurrent games with ordered objectives
- Quantitative fairness games
- The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games
- Concurrent Games with Tail Objectives
- Strategy synthesis for zero-sum neuro-symbolic concurrent stochastic games
- The complexity of ergodic mean-payoff games
- Quantitative solution of \(\omega\)-regular games
- CEGAR for compositional analysis of qualitative properties in Markov decision processes
- Quantitative solution of omega-regular games
- A turn-based approach for qualitative time concurrent games
- Faster algorithms for mean-payoff parity games
- Concurrent games with tail objectives
- Concurrent reachability games
- Qualitative concurrent parity games: bounded rationality
- Subgame optimal strategies in finite concurrent games with prefix-independent objectives
- Title not available (Why is that?)
- Qualitative concurrent parity games
This page was built for publication: Qualitative analysis of concurrent mean-payoff games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2346403)
