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)

• \(\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
• Congestion games with linearly independent paths: convergence time and price of anarchy
• Weighted congestion games with separable preferences
• Computing Approximate Nash Equilibria in Network Congestion Games
• Generalized mirror descents in congestion games
• Network-formation games with regular objectives
• Convergence of best-response dynamics in games with conflicting congestion effects
• Selfish unsplittable flows
• Resource buying games
• Designing fast converging cost sharing methods for multicast transmissions
• $\mathcal{NP}$ -Hardness of Pure Nash Equilibrium in Scheduling and Connection Games
• On the performance of mildly greedy players in cut games
• Convergence and approximation in potential games
• The complexity of pure equilibria in mix-weighted congestion games on parallel links
• Dynamics of Profit-Sharing Games
• Pairwise-interaction games
• Convergence to equilibria in distributed, selfish reallocation processes with weighted tasks
• On the Complexity of Nash Equilibria and Other Fixed Points
• Performance of one-round walks in linear congestion games
• Metastability of asymptotically well-behaved potential games
• Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game
• On the complexity of Pareto-optimal Nash and strong equilibria
• On the complexity of Pareto-optimal Nash and strong equilibria
• Greediness and equilibrium in congestion games
• Stability vs. optimality in selfish ring routing
• On the uniqueness of equilibrium in atomic splittable routing games
• Symmetries and the Complexity of Pure Nash Equilibrium
• Strong equilibria in games with the lexicographical improvement property
• Network movement games
• Approximate Nash equilibria in anonymous games
• Network topology and equilibrium existence in weighted network congestion games
• Dynamics in network interaction games
• On the impact of combinatorial structure on congestion games
• Strategic multiway cut and multicut games
• 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

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)