10 papers · 1 filter
Projected Exploitability Descent for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
Sam Ganzfried
Many important games have more than two players and imperfect information. Existing approaches for computing Nash equilibrium, the central game-theoretic solution concept, in such…
Computing Evolutionarily Stable Strategies in Imperfect-Information Games
Sam Ganzfried
We present an algorithm for computing evolutionarily stable strategies (ESSs) in symmetric perfect-recall extensive-form games of imperfect information. Our main algorithm is for t…
Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
Sam Ganzfried
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 Nas…
Consistent Opponent Modeling in Imperfect-Information Games
Sam Ganzfried
The goal of agents in multi-agent environments is to maximize total reward against the opposing agents that are encountered. Following a game-theoretic solution concept, such as Na…
Dominated Actions in Imperfect-Information Games
Sam Ganzfried
Dominance is a fundamental concept in game theory. In normal-form games dominated strategies can be identified in polynomial time. As a consequence, iterative removal of dominated…
Computing Nash Equilibria in Multiplayer DAG-Structured Stochastic Games with Persistent Imperfect Information
Sam Ganzfried
Many important real-world settings contain multiple players interacting over an unknown duration with probabilistic state transitions, and are naturally modeled as stochastic games…