Finding a Positive Index Nash Equilibrium is PPADS-Complete
En palabras de los autores
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].
Resultado principalEl resumen no menciona limitaciones.
Apareció: martes, 22 de septiembre. arXiv. Preprint, todavía sin revisión por pares.