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
• Malicious Bayesian Congestion Games
• Fighting for routes: resource allocation among competing planners in transportation networks
• Nash equilibria in two-resource congestion games with player-specific payoff functions
• Title not available (Why is that?)
• Combinatorial auctions with endowment effect
• Timed network games with clocks
• The complexity of gradient descent: CLS = PPAD \(\cap\) pls
• Timed network games
• Self-organizing flows in social networks
• Computation and efficiency of potential function minimizers of combinatorial congestion games
• Enforcing efficient equilibria in network design games via subsidies
• Self-organizing flows in social networks
• Settling the complexity of local max-cut (almost) completely
• Leadership in singleton congestion games: what is hard and what is easy
• The classes PPA-\(k\): existence from arguments modulo \(k\)
• Computing Approximate Nash Equilibria in Network Congestion Games with Polynomially Decreasing Cost Functions
• Equilibrium computation in resource allocation games
• Optimization of multi-criteria facility-based systems via vector potential approach
• Unique End of Potential Line
• Asynchronous congestion games
• Many-one reductions and the category of multivalued functions
• The complexity of the parity argument with potential
• Unique end of potential line
• On the convergence of multicast games in directed networks

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)