Best Response Computation in Multiplayer Imperfect-Information Stochastic Games

Abstract

Computing a best response is a fundamental task in game theory. One of its uses is to compute the degree of approximation error of an approximation of Nash equilibrium strategies. In many game classes best responses can be computed in polynomial time, but in imperfect-information stochastic games it is equivalent to solving a POMDP and is PSPACE-complete. Prior work has developed an algorithm for computing an approximation of Nash equilibrium strategies in a 4-player imperfect-information naval strategic planning problem which is modeled as a stochastic game. A heuristic approach was developed for computing best responses to determine the approximation error of these strategies, which was shown to have limited scalability. In this paper we present approaches that utilize parallelism to significantly speed up this computation allowing us to compute best responses in significantly larger games.