NP-hardness of pure Nash equilibrium in scheduling and network design games

DOI10.1016/J.TCS.2012.10.051MaRDI QIDQ390917zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• $\mathcal{NP}$ -Hardness of Pure Nash Equilibrium in Scheduling and Connection Games
• Complexity of pure Nash equilibria in player-specific network congestion games
• Complexity and approximability of optimal resource allocation and Nash equilibrium over networks
• On approximate Nash equilibria in network design
• Inapproximability of NP-complete variants of Nash equilibrium
• Inapproximability of NP-Complete Variants of Nash Equilibrium
• Computing Nash equilibria for two-player restricted network congestion games is \(\mathcal{PLS}\)-complete
• On the hardness of network design for bottleneck routing games

Cites work

• scientific article; zbMATH DE number 5485547 (Why is no real title available?)
• scientific article; zbMATH DE number 5764807 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A class of games possessing pure-strategy Nash equilibria
• Algorithmic Game Theory
• Convergence time to Nash equilibrium in load balancing
• Coordination mechanisms for selfish scheduling
• Designing network protocols for good equilibria
• Inner product spaces for minsum coordination mechanisms
• Nash Equilibria in Voronoi Games on Graphs
• Near-optimal network design with selfish agents
• Network design with weighted players
• Non-clairvoyant scheduling games
• Non-cooperative games
• On the complexity of Pareto-optimal Nash and strong equilibria
• On the complexity of pure-strategy Nash equilibria in congestion and local-effect games
• Potential games
• The Price of Stability for Network Design with Fair Cost Allocation
• The complexity of pure Nash equilibria

Cited in

(1)

• $\mathcal{NP}$ -Hardness of Pure Nash Equilibrium in Scheduling and Connection Games

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

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