Parallel Algorithm for Approximating Nash Equilibrium in Multiplayer Stochastic Games with Application to Naval Strategic Planning
Many real-world domains contain multiple agents behaving strategically with probabilistic transitions and uncertain (potentially infinite) duration. Such settings can be modeled as stochastic games. While algorithms have been developed for solving (i.e., computing a game-theoretic solution concept such as Nash equilibrium) two-player zero-sum stochastic games, research on algorithms for non-zero-sum and multiplayer stochastic games is limited. We present a new algorithm for these settings, which constitutes the first parallel algorithm for multiplayer stochastic games. We present experimental results on a 4-player stochastic game motivated by a naval strategic planning scenario, showing that our algorithm is able to quickly compute strategies constituting Nash equilibrium up to a very small degree of approximation error.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Computing Nash Equilibria in Multiplayer DAG-Structured Stochastic Games with Persistent Imperfect Information
Many important real-world settings contain multiple players interacting over an unknown duration with probabilistic state transitions, and are naturally modeled as stochastic games. Prior research on algorithms for stoch…
Successful Nash Equilibrium Agent for a 3-Player Imperfect-Information Game
Creating strong agents for games with more than two players is a major open problem in AI. Common approaches are based on approximating game-theoretic solution concepts such as Nash equilibrium, which have strong theoret…
Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
There has been significant recent progress in algorithms for approximation of Nash equilibrium in large two-player zero-sum imperfect-information games and exact computation of Nash equilibrium in multiplayer strategic-f…
Algorithm for Computing Approximate Nash Equilibrium in Continuous Games with Application to Continuous Blotto
Successful algorithms have been developed for computing Nash equilibrium in a variety of finite game classes. However, solving continuous games -- in which the pure strategy space is (potentially uncountably) infinite --…
Fast Complete Algorithm for Multiplayer Nash Equilibrium
We describe a new complete algorithm for computing Nash equilibrium in multiplayer general-sum games, based on a quadratically-constrained feasibility program formulation. We demonstrate that the algorithm runs significa…