On the Complexity of Nash Equilibria and Other Fixed Points

DOI10.1137/080720826MaRDI QIDQ3068643zbMATH OpenOpenAlexFDO

Authors Kousha Etessami, Mihalis Yannakakis

Publication date 17 January 2011

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://www.pure.ed.ac.uk/ws/files/14011363/nash_focs07_full_j_spec_issue_sub.pdf

zbMATH Keywords

computational complexityNash equilibriumfixed pointsgamesmarket equilibria

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of approximating a Nash equilibrium
• scientific article; zbMATH DE number 6783488
• The complexity of pure Nash equilibria
• The complexity of finding Nash equilibria
• The complexity of computing a Nash equilibrium
• The complexity of computing a Nash equilibrium
• Nash equilibria: complexity, symmetries, and approximation
• Complexity of rational and irrational Nash equilibria
• Complexity of rational and irrational Nash equilibria
• On the computational complexity of decision problems about multi-player Nash equilibria

Cited in

(87)

• The complexity of computing a bisimilarity pseudometric on probabilistic automata
• The complexity of computational problems about Nash equilibria in symmetric win-lose games
• Uniqueness of stationary equilibrium payoffs in coalitional bargaining
• On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering
• Fixed points, Nash games and their organizations
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• Settling the complexity of computing two-player Nash equilibria
• Tight inapproximability of Nash equilibria in public goods games
• scientific article; zbMATH DE number 5722763 (Why is no real title available?)
• Understanding science through the computational lens
• Approximating maxmin strategies in imperfect recall games using A-loss recall property
• scientific article; zbMATH DE number 7559118 (Why is no real title available?)
• The Hairy Ball Problem is PPAD-Complete.
• On the Complexity of Equilibrium Computation in First-Price Auctions
• The complexity of computing a (quasi-)perfect equilibrium for an \(n\)-player extensive form game
• scientific article; zbMATH DE number 6866347 (Why is no real title available?)
• The complexity of gradient descent: CLS = PPAD \(\cap\) pls
• Equilibria, fixed points, and complexity classes
• On the complexity of constrained Nash equilibria in graphical games
• Belief and truth in hypothesised behaviours
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• A direct reduction from \(k\)-player to 2-player approximate Nash equilibrium
• Nash equilibria: complexity, symmetries, and approximation
• 2-player Nash and nonsymmetric bargaining games: algorithms and structural properties
• Constant rank two-player games are PPAD-hard
• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• On the structure and complexity of worst-case equilibria
• Discrete versions of the KKM lemma and their PPAD-completeness
• Substitution with satiation: a new class of utility functions and a complementary pivot algorithm
• Computational aspects of equilibria
• Asymmetric Distances for Approximate Differential Privacy
• Nash equilibrium points for generalized matrix game model with interval payoffs
• Contiguous cake cutting: hardness results and approximation algorithms
• The Complexity of Nash Equilibria in Limit-Average Games
• A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities
• Query complexity of approximate equilibria in anonymous games
• Financial networks with singleton liability priorities
• Fast Algorithms for Rank-1 Bimatrix Games
• On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
• Consensus Halving for Sets of Items
• Ratio and weight quantiles
• Computational complexity of computing a quasi-proper equilibrium
• The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
• Consensus-Halving: Does It Ever Get Easier?
• Unique End of Potential Line
• Recursive stochastic games with positive rewards
• scientific article; zbMATH DE number 6783488 (Why is no real title available?)
• On oblivious PTAS's for nash equilibrium
• The complexity of optimal multidimensional pricing for a unit-demand buyer
• A polynomial time algorithm for computing extinction probabilities of multitype branching processes
• scientific article; zbMATH DE number 7559416 (Why is no real title available?)
• On perfect Nash equilibria of polymatrix games
• Equilibria, fixed points, and complexity classes
• Recent development in computational complexity characterization of Nash equilibrium
• Computing approximate Nash equilibria in polymatrix games
• Unique end of potential line
• Recursive Markov decision processes and recursive stochastic games
• Query complexity of approximate equilibria in anonymous games
• On Nash-equilibria of approximation-stable games
• On the entropy of couplings
• ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
• Incentive Stackelberg mean-payoff games
• The complexity of equilibria: Hardness results for economies via a correspondence with games
• Graph Games and Reactive Synthesis
• Alternating minima and maxima, Nash equilibria and bounded arithmetic
• Inapproximability of NP-Complete Variants of Nash Equilibrium
• On the computational complexity of decision problems about multi-player Nash equilibria
• Complexity of rational and irrational Nash equilibria
• New algorithms for approximate Nash equilibria in bimatrix games
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Bounding the sum of square roots via lattice reduction
• Equilibria, fixed points, and computational complexity -- Nevanlinna prize lecture
• Lipschitz continuity and approximate equilibria
• Identity testing for radical expressions
• Computational tameness of classical non-causal models
• The complexity of the homotopy method, equilibrium selection and Lemke-Howson solutions
• Financial networks with singleton liability priorities
• scientific article; zbMATH DE number 7662165 (Why is no real title available?)
• Finding a Nash equilibrium in spatial games is an NP-complete problem
• The real computational complexity of minmax value and equilibrium refinements in multi-player games
• 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
• Computational complexity of decision problems about Nash equilibria in win-lose multi-player games
• Reducibility among fractional stability problems

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)