The complexity of finding Nash equilibria

MaRDI QIDQ3524711zbMATH OpenFDO

Authors Christos Papadimitriou

Publication date 12 September 2008

Mathematics Subject Classification ID

Games involving graphs (91A43) Combinatorial games (91A46)

Recommendations

• Algorithms for Scheduling Independent Tasks
• Sequencing with restrictions in processing times
• Optimal Scheduling of Tasks on Identical Parallel Processors
• Task allocation in distributed processing systems
• Minimizing mean flow time with parallel processors and resource constraints

Cited in

(39)

• Uncomputability and undecidability in economic theory
• On the difficulty of approximately maximizing agreements.
• On the NP-completeness of finding an optimal strategy in games with common payoffs
• Finding a Nash equilibrium in spatial games is an NP-complete problem
• Computing solutions of the paintshop-necklace problem
• On the optimization of multitasking process with multiplayer
• Equilibria and efficiency loss in games on networks
• Uniqueness of stationary equilibrium payoffs in coalitional bargaining
• Computational aspects of uncertainty profiles and angel-daemon games
• Equilibrium computation of the Hart and Mas-Colell bargaining model
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• The complexity of computing a Nash equilibrium
• On the Complexity of Nash Equilibria and Other Fixed Points
• The Complexity of Nash Equilibria in Limit-Average Games
• The computational complexity of iterated elimination of dominated strategies
• scientific article; zbMATH DE number 5722763 (Why is no real title available?)
• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• Model Checking Strategic Equilibria
• Constant rank two-player games are PPAD-hard
• Nash equilibria: complexity, symmetries, and approximation
• On the complexity of stable fractional hypergraph matching
• Stochastic games
• Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
• Nash equilibria in symmetric graph games with partial observation
• scientific article; zbMATH DE number 6783488 (Why is no real title available?)
• The complexity of contracts
• Complexity of stability in trading networks
• Inverse optimization of integer programming games for parameter estimation arising from competitive retail location selection
• Existence of Solutions for Deterministic Bilevel Games under a General Bayesian Approach
• Temporal team semantics revisited
• From Leiden to pleasure island: the constant Potts model for community detection as a hedonic game
• Nash meets Łukasiewicz: computing equilibria through logic
• Approximating principal-agent problem under Bayesian
• Linear programming for computing equilibria under truncation selection and designing defensive strategies against malicious opponents
• Critical infrastructure protection using secrecy -- a discrete simultaneous game
• The complexity of symmetric bimatrix games with common payoffs
• Evolution of quantitative traits: exploring the ecological, social and genetic bases of adaptive polymorphism
• Ranking games
• Imitation games and computation

This page was built for publication: The complexity of finding Nash equilibria

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