\(\mathcal{NP}\)-hardness of pure Nash equilibrium in scheduling and network design games

DOI10.1016/J.TCS.2012.10.051zbMath1291.91012OpenAlexW83365193MaRDI QIDQ390917

Nguyen Kim Thang

Publication date: 9 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.10.051

zbMATH Keywords

\(\mathcal{NP}\)-hardnessnetwork design gamespure Nash equilibriascheduling games

Mathematics Subject Classification ID

Noncooperative games (91A10) Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non-clairvoyant scheduling games
• Network design with weighted players
• Coordination mechanisms for selfish scheduling
• Potential games
• A class of games possessing pure-strategy Nash equilibria
• Non-cooperative games
• Designing Network Protocols for Good Equilibria
• On the Complexity of Pareto-optimal Nash and Strong Equilibria
• On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games
• The Price of Stability for Network Design with Fair Cost Allocation
• Nash Equilibria in Voronoi Games on Graphs
• Convergence time to Nash equilibrium in load balancing
• The complexity of pure Nash equilibria
• Inner product spaces for MinSum coordination mechanisms
• Algorithmic Game Theory

This page was built for publication: \(\mathcal{NP}\)-hardness of pure Nash equilibrium in scheduling and network design games