conference paper published yes Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Laurent Doyen author KrCh department LICS: Logic in Computer Science Rigorous Systems Engineering project Quantitative Graph Games: Theory and Applications project Efficient Algorithms for Computer Aided Verification project Graph games provide the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic reactive processes, the traditional model is perfect-information stochastic games, where some transitions of the game graph are controlled by two adversarial players, and the other transitions are executed probabilistically. We consider such games where the objective is the conjunction of several quantitative objectives (specified as mean-payoff conditions), which we refer to as generalized mean-payoff objectives. The basic decision problem asks for the existence of a finite-memory strategy for a player that ensures the generalized mean-payoff objective be satisfied with a desired probability against all strategies of the opponent. A special case of the decision problem is the almost-sure problem where the desired probability is 1. Previous results presented a semi-decision procedure for -approximations of the almost-sure problem. In this work, we show that both the almost-sure problem as well as the general basic decision problem are coNP-complete, significantly improving the previous results. Moreover, we show that in the case of 1-player stochastic games, randomized memoryless strategies are sufficient and the problem can be solved in polynomial time. In contrast, in two-player stochastic games, we show that even with randomized strategies exponential memory is required in general, and present a matching exponential upper bound. We also study the basic decision problem with infinite-memory strategies and present computational complexity results for the problem. Our results are relevant in the synthesis of stochastic reactive systems with multiple quantitative requirements. IEEE2016New York, NY, USA eng 1604.06376 00038760920002510.1145/2933575.2934513 05-08-July-2016247 - 256 K. Chatterjee, L. Doyen, in:, IEEE, 2016, pp. 247–256. Chatterjee, K., &#38; Doyen, L. (2016). Perfect-information stochastic games with generalized mean-payoff objectives (Vol. 05-08-July-2016, pp. 247–256). Presented at the LICS: Logic in Computer Science, New York, NY, USA: IEEE. <a href="https://doi.org/10.1145/2933575.2934513">https://doi.org/10.1145/2933575.2934513</a> K. Chatterjee and L. Doyen, “Perfect-information stochastic games with generalized mean-payoff objectives,” presented at the LICS: Logic in Computer Science, New York, NY, USA, 2016, vol. 05-08-July-2016, pp. 247–256. Chatterjee K, Doyen L. Perfect-information stochastic games with generalized mean-payoff objectives. In: Vol 05-08-July-2016. IEEE; 2016:247-256. doi:<a href="https://doi.org/10.1145/2933575.2934513">10.1145/2933575.2934513</a> Chatterjee, Krishnendu, and Laurent Doyen. “Perfect-Information Stochastic Games with Generalized Mean-Payoff Objectives,” 05-08-July-2016:247–56. IEEE, 2016. <a href="https://doi.org/10.1145/2933575.2934513">https://doi.org/10.1145/2933575.2934513</a>. Chatterjee K, Doyen L. 2016. Perfect-information stochastic games with generalized mean-payoff objectives. LICS: Logic in Computer Science, Proceedings Symposium on Logic in Computer Science, vol. 05-08-July-2016, 247–256. Chatterjee, Krishnendu, and Laurent Doyen. <i>Perfect-Information Stochastic Games with Generalized Mean-Payoff Objectives</i>. Vol. 05-08-July-2016, IEEE, 2016, pp. 247–56, doi:<a href="https://doi.org/10.1145/2933575.2934513">10.1145/2933575.2934513</a>. 4802018-12-11T11:46:42Z2025-09-22T14:22:08Z