The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games

DOI10.1137/1.9781611973730.69MaRDI QIDQ5363044zbMATH OpenOpenAlexFDO

Authors Krishnendu Chatterjee, Rasmus Ibsen-Jensen

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 2-person games (91A05) Stochastic games, stochastic differential games (91A15) Games involving graphs (91A43)

Abstract: We consider concurrent mean-payoff games, a very well-studied class of two-player (player 1 vs player 2) zero-sum games on finite-state graphs where every transition is assigned a reward between 0 and 1, and the payoff function is the long-run average of the rewards. The value is the maximal expected payoff that player 1 can guarantee against all strategies of player 2. We consider the computation of the set of states with value 1 under finite-memory strategies for player 1, and our main results for the problem are as follows: (1) we present a polynomial-time algorithm; (2) we show that whenever there is a finite-memory strategy, there is a stationary strategy that does not need memory at all; and (3) we present an optimal bound (which is double exponential) on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy).

Recommendations

• The complexity of partial-observation stochastic parity games with finite-memory strategies
• Qualitative analysis of concurrent mean-payoff games
• On the Value Problem in Weighted Timed Games.
• On concurrent games with payoff
• Approximating the value of a concurrent reachability game in the polynomial time hierarchy
• Subgame optimal strategies in finite concurrent games with prefix-independent objectives
• Strategy-proofness and essentially single-valued cores revisited
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games

Cited in

(7)

• Qualitative analysis of concurrent mean-payoff games
• On concurrent games with payoff
• On memoryless quantitative objectives
• scientific article; zbMATH DE number 7204389 (Why is no real title available?)
• The complexity of ergodic mean-payoff games
• On values of games
• CEGAR for compositional analysis of qualitative properties in Markov decision processes

This page was built for publication: The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games

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