arXiv:2609.23879 · v3

Finding a Positive Index Nash Equilibrium is PPADS-Complete

首次提交 2026-09-21 05:29

版本更新 2026-10-26 18:59

雷达观测 2026-10-29 00:36

摘要

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. The nondegeneracy promise can be removed if nonregular equilibria are also accepted: finding either a regular Nash equilibrium of index +1 or a nonregular Nash equilibrium in an arbitrary rational bimatrix game is also PPADS-complete. 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 [2019].

作者备注：This version simplifies Section 4 using a two-dimensional embedding based on the construction of Chen and Deng (2009)