if player 1 has k possible actions and player 2 has l possible actions, there are k l joint actions in the game. Without loss of generality, we assume that the payoff of a player in a game is taken from the interval of real numbers P = [0, Rmax].

A common-interest game is a game in which the rewards obtained by all agents are identical. A coordination game is a common-interest game in whi all agents have the same set A of actions, and, in addition, for every i, the reward all agents receive for selecting the joint action (i, i) is greater than the reward they receive for selecting (i, j) for any j = i.

In a repeated game the players play a given game G repeatedly. We can view a repeated game, with respect to a game G , as consisting of an infinite number of iterations, for each of which the players have to select an action of the game G. After playing each iteration, the players receive the appropriate payoffs, as dictated by that game's matrix, and move to the next iteration.

A stochastic game is a game in which the players play a possibly infinite sequence of one-shot, strategic form games from some given set of games, which we shall take to be finite. After playing each game, the players receive the appropriate payoff, as dictated by that game's matrix, and move to a new game. The identity of this new game depends, stochastically, on the previous game and on the players' actions in that previous game. Formally:
Definition 1 A two player, stochastic-game  M on states S = {1,...,N}, and actions A = {a1,...,ak}, consists of:
- Stage Games: each state s E S is associated with a two-player game in strategic form, where the action set of each player is A.

- Probabilistic Transition Function: tr(s, t, a, a') is the probability of a transition from state s to state t given that the first player plays a and the second player plays a'.
A stochastic game is similar to a Markov decision process (MDP). In both models actions lead to transitions between states of the world. The main difference is that in an MDP the transition depends on the action of a single player whereas in a stochastic game the transition depends on the joint action of both players. In addition, in a stoastic game, the reward obtained by the player for performing an action depends on its action and the action of the other player. To model this, we associate a game with every state. Therefore, we often use the terms state, stage game, and game interchangeably.

Much like in regular one-shot games, we can restrict our attention to special classes of stochastic and repeated games. In particular, in this paper we are interested in commoninterest stochastic games (CISGs), i.e., stochastic games in whi ea stage-game is a common-interest game. CISGs can be viewed as a special extension of MDPs. They correspond to an MDP in which the agent is actually a distributed system. That is, it has different components, all of which influence the choice of action, but all of which work toward a common goal. Thus, for every CISG, we define its induced MDP to be the MDP
obtained from the CISG when we assume the existence of a single agent that controls all the agents in the CISG. That is, a single agent whose set of actions corresponds to the joint-actions of the CISG agents. Because the payoffs for all agents are identical, this is a wll-defined concept.