each joint-sequence of length t, an |S|-vector containing the values of the jointsequence when the initial belief state is one of the states in S. We then *prune*, for each agent, sequences of length t that are dominated over belief space formed by the cross-product of S and the set of joint-sequences of length t. By starting out with the set S
1 i
(which is in fact just the set Ai) for each agent i, we can incrementally build the set S
κ i
. Note that a backup of the set S
t i creates |Ai||Ωi||St i | new sequences; i.e., the growth is linear. In contrast, the backing-up of a set of policies represents an exponential growth. The merit of this procedure is that we may be able to compute an optimal joint-policy for a slightly longer horizon. But more importantly, due to the linear growth of sequences in each iteration, it may be possible to solve for the infinite-horizon by iterating until some stability or convergence in the values of joint-sequences in realized. Pompds: Finally, the approach consisting of the use of the sequence-form and mathematical programming could be applied to Pomdps. We have already shown in this paper how a finite-horizon Pomdp can be solved. In conjunction with the dynamic programming approach analogous to the one described above, it may be possible to compute the infinite-horizon discounted value function of a Pomdp.

## Acknowledgements

We are grateful to the anonymous reviewers for providing us with valuable comments on this work and suggestions for improving the paper.

## References

[1] Bernstein, D.; Givan, R.; Immerman, N.; and Zilberstein, S. 2002. The complexity of decentralized control of markov decision processes. Mathematics of Operations Research 27(4):819–840.

[2] Blair, J. R.; Mutchler, D.; and van Lent, M. 1996. Perfect recall and pruning in games with imperfect information. *Computational Intelligence* 12:131–154.

[3] Emery-Montemerlo, R.; Gordon, G.; Schneider, J.; and Thrun, S. 2004. Approximate solutions for partially observable stochastic games with common payoffs. In Proceedings of the Third International Joint Conference on *Autonomous Agents and* Multi-Agent Systems (AAMAS).

[4] Hansen, E.; Bernstein, D.; and Zilberstein, S. 2004. Dynamic programming for partially observable stochastic games. *Proceedings of the 19th National Conference* on Artificial Intelligence 709–715.

[5] Koller, D., and Megiddo, N. 1992. The complexity of zero-sum games in extensive form. *Games and Economic Behavior* 4(4):528–552.