Dynamic Stochastic Games with Sequential State-to-State Transitions

Discrete-time stochastic games with a finite number of states have been widely applied to study the strategic interactions among forward-looking players in dynamic environments. The model as written down by Ericson & Pakes (1995), Pakes & McGuire (1994, 2001) (hereafter, EP, PM1, and PM2), the subsequent literature (e.g., Gowrisankaran 1999, Fershtman & Pakes 2000, Benkard 2004), and in standard textbook treatments of stochastic games (e.g., Filar & Vrieze 1997, Basar & Olsder 1999) assumes that the states of all players change at exactly the same point in each period (say at the end of the period). That is, the transitions from this period's state to next period's state are simultaneous. As PM2 and Doraszelski & Judd (2004) (hereafter, DJ) point out, these games with simultaneous state-to-state transitions suffer from a "curse of dimensionality" since the cost of computing players' expectations over all possible future states increases exponentially in the number of state variables. However, there are many other ways to formulate dynamic stochastic games, and some of them may be computationally more tractable than others. In particular, we show that there are games with sequential state-to-state transitions that do not su®er from the curse of dimensionality in the expectation over successor states.