Finding specific Nash equilibria in games is computationally hard
Finding a Positive Index Nash Equilibrium is PPADS-Complete
Computational ComplexityComputer Science and Game Theory
Summary
The paper shows that finding a special type of stable outcome called a Nash equilibrium with a positive index in certain two-player games is computationally difficult. Every such game has equilibria whose indices sum to one, but identifying exactly one with index +1 is proven to be hard. The authors’ result settles a previously open question by proving this problem is complete for a complexity class known as PPADS. This means that solving these games in this precise way is as hard as the hardest problems in that class.
What this means in practice
- •For game theory software developers: Recognize that algorithms to find Nash equilibria with positive index in explicit two-player games face fundamental computational limits.
- •For optimization algorithm designers: Account for the hardness of identifying certain equilibria when designing equilibrium-finding tools in economics and strategic modeling.
A theory result. No direct application yet.
Authors
Andreas Kontogiannis, Ioannis Panageas, Vasilis Pollatos, Jingming Yan
Abstract
Every nondegenerate bimatrix game has a Nash equilibrium of Shapley index +1, since all equilibria are isolated, have index +1 or -1, and their indices sum to +1. We prove that the following promise search problem is PPADS-complete: given a rational bimatrix game promised to be nondegenerate, find an exact Nash equilibrium of index +1. To our knowledge, this is the first PPADS-complete equilibrium search problem whose instances are explicit rational normal form payoff matrices, rather than succinct circuits or Turing machines, and thereby addresses an open question posed by Daskalakis [Daskalakis, 2019].