The complexity of pure Nash equilibria

DOI10.1145/1007352.1007445zbMATH Open1192.91042OpenAlexW2145297839MaRDI QIDQ3580952FDOQ3580952

Authors: Alex Fabrikant, Kunal Talwar, Christos Papadimitriou 

Publication date: 15 August 2010

Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1007352.1007445

Recommendations

• Complexity of pure-strategy Nash equilibria in non-cooperative games
• Complexity of pure Nash equilibria in player-specific network congestion games
• scientific article; zbMATH DE number 2243403
• Symmetries and the Complexity of Pure Nash Equilibrium
• Mathematical Foundations of Computer Science 2005

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) (n)-person games, (n>2) (91A06) Games involving graphs (91A43)

Cited In (only showing first 100 items - show all)

• Some results of Maria Serna on strategic games: complexity of equilibria and models
• Title not available (Why is that?)
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• On the Complexity of Equilibrium Computation in First-Price Auctions
• Computing equilibria of Cournot oligopoly models with mixed-integer quantities
• Synthesis from component libraries with costs
• On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games
• Computing solutions of the multiclass network equilibrium problem with affine cost functions
• How to find Nash equilibria with extreme total latency in network congestion games?
• The impact of social ignorance on weighted congestion games
• On the complexity of constrained Nash equilibria in graphical games
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• On the impact of singleton strategies in congestion games
• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• The inefficiency of Nash and subgame perfect equilibria for network routing
• An abstraction-refinement methodology for reasoning about network games
• Undecidability of the existence of pure Nash equilibria
• Complexity of pure-strategy Nash equilibria in non-cooperative games
• Metastability of logit dynamics for coordination games
• Pure-strategy equilibrium in Bayesian potential games with absolutely continuous information
• Computational aspects of uncertainty profiles and angel-daemon games
• Timed network games
• Fast convergence of best-reply dynamics in aggregative games
• A metaheuristic approach to compute pure Nash equilibria
• Computing pure Nash equilibria in network revenue management games
• Convergence of incentive-driven dynamics in Fisher markets
• Complexity and optimality of the best response algorithm in random potential games
• Management of Variable Data Streams in Networks
• Selfish versus unselfish optimization of network creation
• Computing all solutions of Nash equilibrium problems with discrete strategy sets
• Automata, Languages and Programming
• Alternating minima and maxima, Nash equilibria and bounded arithmetic
• Capacitated network design games
• The Price of Stochastic Anarchy
• A selective tour through congestion games
• Congestion games with complementarities
• Atomic Congestion Games: Fast, Myopic and Concurrent
• Coordination games on weighted directed graphs
• Nash equilibria in all-optical networks
• Computational aspects of the colorful Carathéodory theorem
• Characterizing the existence of potential functions in weighted congestion games
• Competitive routing over time
• Incentive-based search for efficient equilibria of the public goods game
• The price of stability of weighted congestion games
• The price of stability of weighted congestion games
• Equilibria problems on games: complexity versus succinctness
• Mathematical Foundations of Computer Science 2005
• Equilibria in Multiclass and Multidimensional Atomic Congestion Games
• Computing equilibria: a computational complexity perspective
• Sharing non-anonymous costs of multiple resources optimally
• Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games
• Precise complexity of the core in dichotomous and additive hedonic games
• A logarithmic approximation for polymatroid congestion games
• Computing approximate equilibria in weighted congestion games via best-responses
• Convergence method, properties and computational complexity for Lyapunov games
• Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions
• Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games
• \(\mathcal{NP}\)-hardness of pure Nash equilibrium in scheduling and network design games
• Nash equilibria with minimum potential in undirected broadcast games
• On influence, stable behavior, and the most influential individuals in networks: a game-theoretic approach
• The structure and complexity of Nash equilibria for a selfish routing game
• Coordination mechanisms
• Title not available (Why is that?)
• On the complexity of pure-strategy Nash equilibria in congestion and local-effect games
• Nash equilibria: complexity, symmetries, and approximation
• Complexity of pure Nash equilibria in player-specific network congestion games
• Weighted Boolean formula games
• On spectrum sharing games
• The complexity of computing a Nash equilibrium
• How hard is it to find extreme Nash equilibria in network congestion games?
• The Complexity of Nash Equilibria in Limit-Average Games
• The maximal generic number of pure Nash equilibria
• Concurrent imitation dynamics in congestion games
• Efficient coordination mechanisms for unrelated machine scheduling
• The complexity of welfare maximization in congestion games
• Graphical congestion games
• The complexity of uniform Nash equilibria and related regular subgraph problems
• Symmetries and the complexity of pure Nash equilibrium
• Computing Nash equilibria for two-player restricted network congestion games is \(\mathcal{PLS}\)-complete
• Complexity and approximability of optimal resource allocation and Nash equilibrium over networks
• Convergence to approximate Nash equilibria in congestion games
• Tight bounds for selfish and greedy load balancing
• Minimizing expectation plus variance
• On best response dynamics in weighted congestion games with polynomial delays
• Computation of equilibria and the price of anarchy in bottleneck congestion games
• Selfish splittable flows and NP-completeness
• Computing pure Nash and strong equilibria in bottleneck congestion games
• Rational generating functions and integer programming games
• Congestion Games with Linearly Independent Paths: Convergence Time and Price of Anarchy
• Title not available (Why is that?)
• Atomic congestion games: fast, myopic and concurrent
• On oblivious PTAS's for nash equilibrium
• Selfish routing with incomplete information
• Decentralized dynamics for finite opinion games
• On the performance of approximate equilibria in congestion games
• Computing approximate Nash equilibria in network congestion games
• Congestion games with capacitated resources
• Pure Nash equilibria in player-specific and weighted congestion games
• Equilibria, fixed points, and complexity classes
• The price of atomic selfish ring routing

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

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