On the Complexity of Nash Equilibria and Other Fixed Points

DOI10.1137/080720826zbMATH Open1204.91003OpenAlexW1991624978MaRDI QIDQ3068643FDOQ3068643

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

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

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)

Cited In (87)

• Settling the complexity of computing two-player Nash equilibria
• On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• Fixed points, Nash games and their organizations
• 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?)
• The complexity of computing a (quasi-)perfect equilibrium for an \(n\)-player extensive form game
• Equilibria, fixed points, and complexity classes
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• On the complexity of constrained Nash equilibria in graphical games
• A direct reduction from \(k\)-player to 2-player approximate Nash equilibrium
• Belief and truth in hypothesised behaviours
• Nash equilibria: complexity, symmetries, and approximation
• 2-player Nash and nonsymmetric bargaining games: algorithms and structural properties
• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• Substitution with satiation: a new class of utility functions and a complementary pivot algorithm
• Asymmetric Distances for Approximate Differential Privacy
• Computational aspects of equilibria
• Discrete versions of the KKM lemma and their PPAD-completeness
• On the structure and complexity of worst-case equilibria
• 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
• Consensus Halving for Sets of Items
• Ratio and weight quantiles
• 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
• Title not available (Why is that?)
• The complexity of optimal multidimensional pricing for a unit-demand buyer
• 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
• On Nash-equilibria of approximation-stable games
• Query complexity of approximate equilibria in anonymous games
• ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
• On the entropy of couplings
• Incentive Stackelberg mean-payoff games
• Graph Games and Reactive Synthesis
• On the computational complexity of decision problems about multi-player Nash equilibria
• The complexity of equilibria: Hardness results for economies via a correspondence with games
• Inapproximability of NP-Complete Variants of Nash Equilibrium
• Alternating minima and maxima, Nash equilibria and bounded arithmetic
• Complexity of rational and irrational Nash equilibria
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• New algorithms for approximate Nash equilibria in bimatrix games
• Bounding the sum of square roots via lattice reduction
• Lipschitz continuity and approximate equilibria
• The complexity of the homotopy method, equilibrium selection and Lemke-Howson solutions
• 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
• Reducibility among fractional stability problems
• The complexity of computing a bisimilarity pseudometric on probabilistic automata
• 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?)
• Understanding science through the computational lens
• The complexity of gradient descent: CLS = PPAD \(\cap\) pls
• Constant rank two-player games are PPAD-hard
• Nash equilibrium points for generalized matrix game model with interval payoffs
• 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?
• A polynomial time algorithm for computing extinction probabilities of multitype branching processes
• Equilibria, fixed points, and computational complexity -- Nevanlinna prize lecture
• Identity testing for radical expressions
• 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

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)