Qualitative analysis of concurrent mean-payoff games
From MaRDI portal
Publication:2346403
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3128726 (Why is no real title available?)
- scientific article; zbMATH DE number 3128733 (Why is no real title available?)
- scientific article; zbMATH DE number 1134975 (Why is no real title available?)
- scientific article; zbMATH DE number 1500523 (Why is no real title available?)
- scientific article; zbMATH DE number 1759629 (Why is no real title available?)
- scientific article; zbMATH DE number 1863184 (Why is no real title available?)
- Algorithms for Omega-Regular Games with Imperfect Information
- Alternating-time temporal logic
- An \(O(n^2)\) time algorithm for alternating Büchi games
- Automata, Languages and Programming
- Better Quality in Synthesis through Quantitative Objectives
- Code aware resource management
- Computer Science Logic
- Concurrent games with tail objectives
- Concurrent reachability games
- Cyclic games and an algorithm to find minimax cycle means in directed graphs
- Decidable problems for probabilistic automata on infinite words
- Deciding the value 1 problem for probabilistic leaktight automata
- Exact algorithms for solving stochastic games
- Faster algorithms for mean-payoff games
- Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification
- On Nonterminating Stochastic Games
- Optimal control of diffusion processes with reflection
- Partial-observation stochastic games, how to win when belief fails
- Positional strategies for mean payoff games
- Probabilistic ω-automata
- Qualitative concurrent parity games
- Qualitative concurrent parity games: bounded rationality
- Qualitative reachability in stochastic BPA games
- Quantitative languages
- Recursive Concurrent Stochastic Games
- Repeated games with absorbing states
- Solving partial-information stochastic parity games
- Stochastic Games
- Stochastic Games with Perfect Information and Time Average Payoff
- Stochastic games
- Stochastic limit-average games are in EXPTIME
- Synthesis from LTL specifications with mean-payoff objectives
- The Asymptotic Theory of Stochastic Games
- The Big Match
- The complexity of mean payoff games on graphs
- The complexity of partial-observation stochastic parity games with finite-memory strategies
- The complexity of stochastic games
- Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study
- Weighted automata and weighted MSO logics for average and long-time behaviors
- What is decidable about partially observable Markov decision processes with omega-regular objectives
Cited in
(20)- Concurrent games with ordered objectives
- A turn-based approach for qualitative time concurrent games
- Robust equilibria in mean-payoff games
- Quantitative fairness games
- Subgame optimal strategies in finite concurrent games with prefix-independent objectives
- Strategy synthesis for zero-sum neuro-symbolic concurrent stochastic games
- scientific article; zbMATH DE number 1948169 (Why is no real title available?)
- Concurrent Games with Tail Objectives
- CEGAR for compositional analysis of qualitative properties in Markov decision processes
- Qualitative concurrent parity games: bounded rationality
- The complexity of ergodic mean-payoff games
- Automata-based controller synthesis for stochastic systems: a game framework via approximate probabilistic relations
- Quantitative solution of \(\omega\)-regular games
- Qualitative concurrent parity games
- Concurrent reachability games
- Quantitative solution of omega-regular games
- On concurrent games with payoff
- Concurrent games with tail objectives
- The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games
- Faster algorithms for mean-payoff 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)
