On the Complexity of Nash Equilibria and Other Fixed Points
From MaRDI portal
Publication:3068643
DOI10.1137/080720826zbMath1204.91003OpenAlexW1991624978MaRDI QIDQ3068643
Mihalis Yannakakis, Kousha Etessami
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
Noncooperative games (91A10) 2-person games (91A05) Fixed-point theorems (47H10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Belief and truth in hypothesised behaviours ⋮ On the Complexity of Equilibrium Computation in First-Price Auctions ⋮ Nash Equilibrium Points for Generalized Matrix Game Model with Interval Payoffs ⋮ On Nash-Equilibria of Approximation-Stable Games ⋮ A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium ⋮ 2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties ⋮ Consensus-Halving: Does It Ever Get Easier? ⋮ On the complexity of constrained Nash equilibria in graphical games ⋮ ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria ⋮ Computational complexity of computing a quasi-proper equilibrium ⋮ Graph Games and Reactive Synthesis ⋮ Computing equilibria: a computational complexity perspective ⋮ A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities ⋮ Query Complexity of Approximate Equilibria in Anonymous Games ⋮ Constant Rank Two-Player Games are PPAD-hard ⋮ The complexity of optimal multidimensional pricing for a unit-demand buyer ⋮ Computational tameness of classical non-causal models ⋮ Incentive Stackelberg Mean-Payoff Games ⋮ Query complexity of approximate equilibria in anonymous games ⋮ The complexity of computational problems about Nash equilibria in symmetric win-lose games ⋮ The Exact Computational Complexity of Evolutionarily Stable Strategies ⋮ Complexity of rational and irrational Nash equilibria ⋮ Ratio and Weight Quantiles ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ Recursive stochastic games with positive rewards ⋮ Financial networks with singleton liability priorities ⋮ Unique end of potential line ⋮ Financial networks with singleton liability priorities ⋮ The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete ⋮ A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes ⋮ Unnamed Item ⋮ Uniqueness of stationary equilibrium payoffs in coalitional bargaining ⋮ Understanding science through the computational lens ⋮ Contiguous Cake Cutting: Hardness Results and Approximation Algorithms ⋮ On perfect Nash equilibria of polymatrix games ⋮ Equilibria, fixed points, and complexity classes ⋮ Nash equilibria: complexity, symmetries, and approximation ⋮ Computing exact solutions of consensus halving and the Borsuk-Ulam theorem ⋮ Approximating maxmin strategies in imperfect recall games using A-loss recall property ⋮ The Hairy Ball problem is PPAD-complete ⋮ Asymmetric Distances for Approximate Differential Privacy ⋮ Computing approximate Nash equilibria in polymatrix games ⋮ On Stackelberg mixed strategies ⋮ Fixed points, Nash equilibria, and the existential theory of the reals ⋮ The complexity of computing a (quasi-)perfect equilibrium for an \(n\)-player extensive form game ⋮ The real computational complexity of minmax value and equilibrium refinements in multi-player games ⋮ The Complexity of Computing a Bisimilarity Pseudometric on Probabilistic Automata ⋮ Lipschitz continuity and approximate equilibria ⋮ Bounding the sum of square roots via lattice reduction ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Recursive Markov Decision Processes and Recursive Stochastic Games ⋮ On the computational complexity of decision problems about multi-player Nash equilibria ⋮ Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm ⋮ The Complexity of Nash Equilibria in Limit-Average Games ⋮ Unique End of Potential Line ⋮ The Hairy Ball Problem is PPAD-Complete. ⋮ Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Fast Algorithms for Rank-1 Bimatrix Games ⋮ New algorithms for approximate Nash equilibria in bimatrix games ⋮ Two's company, three's a crowd: consensus-halving for a constant number of agents ⋮ Discrete versions of the KKM lemma and their PPAD-completeness ⋮ Unnamed Item ⋮ On the entropy of couplings ⋮ Consensus Halving for Sets of Items
