  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
epsilon-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.
