Abstract: 
We consider concurrent games played by two players on a finitestate 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 the most fundamental objective for concurrent games, namely, meanpayoff or limitaverage objective, where a reward is associated to each transition, and the goal of player 1 is to maximize the longrun average of the rewards, and the objective of player 2 is strictly the opposite (i.e., the games are zerosum). The path constraint for player 1 could be qualitative, i.e., the meanpayoff 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 almostsure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Almostsure winning with qualitative constraint exactly corresponds to the question of whether there exists a strategy to ensure that the payoff is the maximal reward of the game. 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 almostsure (resp. positive) winning against all player2 strategies, or player 2 has a spoiling strategy to falsify almostsure (resp. positive) winning against all player1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almostsure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almostsure and the positive winning sets, matching the best known bound of the algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almostsure or the positive winning set would imply a solution to a longstanding open problem (of solving the value problem of turnbased deterministic meanpayoff games) that is not known to be solvable in polynomial time.
