On the Complexity of Pareto-optimal Nash and Strong Equilibria

DOI10.1007/978-3-642-16170-4_27zbMath1310.91043OpenAlexW3138627403MaRDI QIDQ3162529

Alexander Skopalik, Martin Hoefer

Publication date: 19 October 2010

Published in: Algorithmic Game Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16170-4_27

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

Computing the strong Nash equilibrium for Markov chains games ⋮ On the complexity of Pareto-optimal Nash and strong equilibria ⋮ Computing pure Nash and strong equilibria in bottleneck congestion games ⋮ \(\mathcal{NP}\)-hardness of pure Nash equilibrium in scheduling and network design games ⋮ Resource buying games ⋮ Competitive routing over time ⋮ Computing the strong \(L_p\)-Nash equilibrium for Markov chains games: convergence and uniqueness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Symmetries and the complexity of pure Nash equilibrium
• Strong price of anarchy
• Anonymous games with binary actions
• Equilibria in a model with partial rivalry
• Strong equilibrium in congestion games
• Characterization of pure strategy equilibria infinite anonymous games
• Congestion games with player-specific payoff functions
• A class of games possessing pure-strategy Nash equilibria
• On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games
• On the impact of combinatorial structure on congestion games
• The complexity of pure Nash equilibria
• Computing Pure Nash and Strong Equilibria in Bottleneck Congestion Games
• Strong and Pareto Price of Anarchy in Congestion Games

This page was built for publication: On the Complexity of Pareto-optimal Nash and Strong Equilibria