Fast Complete Algorithm for Multiplayer Nash Equilibrium
This addresses the computational bottleneck in game theory for researchers and practitioners, though it appears incremental as it builds on existing formulations.
The authors tackled the problem of computing Nash equilibrium in multiplayer general-sum games by developing a new complete algorithm based on a quadratically-constrained feasibility program. The result is a significantly faster algorithm that outperforms prior complete methods and even incomplete algorithms on several game classes.
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 significantly faster than the prior fastest complete algorithm on several game classes previously studied and that its runtimes even outperform the best incomplete algorithms.