The value 1 problem under finite-memory strategies for concurrent mean-payoff games

conference paper The value 1 problem under finite-memory strategies for concurrent mean-payoff games published yes Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Rasmus Ibsen-Jensen author 3B699956-F248-11E8-B48F-1D18A9856A870000-0003-4783-0389 KrCh department SODA: Symposium on Discrete Algorithms Modern Graph Algorithmic Techniques in Formal Verification project Game Theory project Quantitative Graph Games: Theory and Applications project Microsoft Research Faculty Fellowship project 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). SIAM2015San Diego, CA, United States eng Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms 978-161197374-7 1409.669010.1137/1.9781611973730.69 201511018-1029 K. Chatterjee and R. Ibsen-Jensen, “The value 1 problem under finite-memory strategies for concurrent mean-payoff games,” in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, United States, 2015, vol. 2015, no. 1, pp. 1018–1029. Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Value 1 Problem under Finite-Memory Strategies for Concurrent Mean-Payoff Games.” Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 2015, no. 1, SIAM, 2015, pp. 1018–29, doi:<a href="https://doi.org/10.1137/1.9781611973730.69">10.1137/1.9781611973730.69</a>. Chatterjee K, Ibsen-Jensen R. 2015. The value 1 problem under finite-memory strategies for concurrent mean-payoff games. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2015, 1018–1029. K. Chatterjee, R. Ibsen-Jensen, in:, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2015, pp. 1018–1029. Chatterjee K, Ibsen-Jensen R. The value 1 problem under finite-memory strategies for concurrent mean-payoff games. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 2015. SIAM; 2015:1018-1029. doi:<a href="https://doi.org/10.1137/1.9781611973730.69">10.1137/1.9781611973730.69</a> Chatterjee, K., & Ibsen-Jensen, R. (2015). The value 1 problem under finite-memory strategies for concurrent mean-payoff games. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 2015, pp. 1018–1029). San Diego, CA, United States: SIAM. <a href="https://doi.org/10.1137/1.9781611973730.69">https://doi.org/10.1137/1.9781611973730.69</a> Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Value 1 Problem under Finite-Memory Strategies for Concurrent Mean-Payoff Games.” In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015:1018–29. SIAM, 2015. <a href="https://doi.org/10.1137/1.9781611973730.69">https://doi.org/10.1137/1.9781611973730.69</a>. 107962022-02-25T12:18:43Z2025-06-26T06:54:08Z