On the Complexity of Nash Equilibria and Other Fixed Points

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10) 2-person games (91A05) Fixed-point theorems (47H10)

Cited In (78)

Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
Fixed points, Nash games and their organizations
Understanding science through the computational lens
On the Complexity of Equilibrium Computation in First-Price Auctions
The Hairy Ball Problem is PPAD-Complete.
Approximating maxmin strategies in imperfect recall games using A-loss recall property
Title not available (Why is that?)
Incentive Stackelberg Mean-Payoff Games
The complexity of computing a (quasi-)perfect equilibrium for an \(n\)-player extensive form game
On the complexity of constrained Nash equilibria in graphical games
Belief and truth in hypothesised behaviours
Nash equilibria: complexity, symmetries, and approximation
The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
Asymmetric Distances for Approximate Differential Privacy
Discrete versions of the KKM lemma and their PPAD-completeness
On the structure and complexity of worst-case equilibria
The Complexity of Nash Equilibria in Limit-Average Games
Consensus Halving for Sets of Items
The Exact Computational Complexity of Evolutionarily Stable Strategies
Computational complexity of computing a quasi-proper equilibrium
Unique End of Potential Line
Title not available (Why is that?)
On oblivious PTAS's for nash equilibrium
Recursive stochastic games with positive rewards
A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium
Title not available (Why is that?)
The complexity of optimal multidimensional pricing for a unit-demand buyer
Query Complexity of Approximate Equilibria in Anonymous Games
On perfect Nash equilibria of polymatrix games
Equilibria, fixed points, and complexity classes
Computing approximate Nash equilibria in polymatrix games
2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties
Unique end of potential line
Recursive Markov decision processes and recursive stochastic games
Query complexity of approximate equilibria in anonymous games
On the entropy of couplings
Graph Games and Reactive Synthesis
On the computational complexity of decision problems about multi-player Nash equilibria
Ratio and Weight Quantiles
Inapproximability of NP-Complete Variants of Nash Equilibrium
A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities
Complexity of rational and irrational Nash equilibria
The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
New algorithms for approximate Nash equilibria in bimatrix games
Bounding the sum of square roots via lattice reduction
The Complexity of Computing a Bisimilarity Pseudometric on Probabilistic Automata
Lipschitz continuity and approximate equilibria
Nash Equilibrium Points for Generalized Matrix Game Model with Interval Payoffs
Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm
On Nash-Equilibria of Approximation-Stable Games
Finding a Nash equilibrium in spatial games is an NP-complete problem
Contiguous Cake Cutting: Hardness Results and Approximation Algorithms
The real computational complexity of minmax value and equilibrium refinements in multi-player games
ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria
Computing equilibria: a computational complexity perspective
On Stackelberg mixed strategies
Fixed points, Nash equilibria, and the existential theory of the reals
The Hairy Ball problem is PPAD-complete
Two's company, three's a crowd: consensus-halving for a constant number of agents
The complexity of computational problems about Nash equilibria in symmetric win-lose games
Uniqueness of stationary equilibrium payoffs in coalitional bargaining
Tight inapproximability of Nash equilibria in public goods games
Title not available (Why is that?)
Title not available (Why is that?)
The complexity of gradient descent: CLS = PPAD \(\cap\) pls
A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes
Financial networks with singleton liability priorities
On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
Fast Algorithms for Rank-1 Bimatrix Games
The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
Consensus-Halving: Does It Ever Get Easier?
Identity testing for radical expressions
Constant Rank Two-Player Games are PPAD-hard
Computational tameness of classical non-causal models
Financial networks with singleton liability priorities
Title not available (Why is that?)
Computational complexity of decision problems about Nash equilibria in win-lose multi-player games

Recommendations

This page was built for publication: On the Complexity of Nash Equilibria and Other Fixed Points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3068643)