PPAD-complete approximate pure Nash equilibria in Lipschitz games
From MaRDI portal
Publication:6069844
DOI10.1016/j.tcs.2023.114218MaRDI QIDQ6069844
Matthew J. Katzman, Paul W. Goldberg
Publication date: 17 November 2023
Published in: Theoretical Computer Science (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Propositional proofs and reductions between NP search problems
- Computing approximate Nash equilibria in polymatrix games
- On total functions, existence theorems and computational complexity
- Stability in large Bayesian games with heterogeneous players
- How easy is local search?
- On the complexity of the parity argument and other inefficient proofs of existence
- Logarithmic query complexity for approximate Nash computation in large games
- Fault tolerance in large games
- Approximate Nash equilibria in anonymous games
- Query complexity of approximate equilibria in anonymous games
- Best-reply dynamics in large binary-choice anonymous games
- Non-cooperative games
- Lower bounds for the query complexity of equilibria in Lipschitz games
- The Computational Complexity of Nash Equilibria in Concisely Represented Games
- Settling the complexity of computing two-player Nash equilibria
- Privacy and Truthful Equilibrium Selection for Aggregative Games
- Inapproximability of Nash Equilibrium
- Pseudo-deterministic Proofs
- Lipschitz Games
- Computational Complexity
- The complexity of gradient descent: CLS = PPAD ∩ PLS
This page was built for publication: PPAD-complete approximate pure Nash equilibria in Lipschitz games
