Date Added: Oct 2012
In this paper, the authors show that when the players' current interest is a subset of the states only and they are willing to accept small inaccuracies in the game solutions; many Markov game states can be pruned. They present a pruning algorithm in which a threshold parameter is used to control qualitatively the tradeoff between computation time and solution accuracy. The algorithm is iterative with decoupled state values in each iteration and they parallelize the state estimations to reduce the overall computation time. They illustrate with examples that the pruning algorithm reduces the computation time greatly without losing much precision in the game solutions, and that parallelization further reduces the computation time.