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

DOI10.1016/J.TCS.2012.10.051zbMATH Open1291.91012OpenAlexW83365193MaRDI QIDQ390917FDOQ390917

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

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

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)

Cites Work

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

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)