Complexity of pure Nash equilibria in player-specific network congestion games

DOI10.1080/15427951.2008.10129170zbMATH Open1194.91055OpenAlexW2147218196MaRDI QIDQ3574299FDOQ3574299

Authors Heiner Ackermann, Alexander Skopalik

Publication date 9 July 2010

Published in Internet Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/15427951.2008.10129170

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Games involving graphs (91A43)

Recommendations

• On the complexity of pure-strategy Nash equilibria in congestion and local-effect games
• The complexity of pure Nash equilibria
• Computing Nash equilibria for two-player restricted network congestion games is \(\mathcal{PLS}\)-complete
• Congestion games with player-specific costs revisited
• Pure Nash equilibria in player-specific and weighted congestion games

Cited in

(21)

• The complexity of pure equilibria in mix-weighted congestion games on parallel links
• \(\mathcal{NP}\)-hardness of pure Nash equilibrium in scheduling and network design games
• The complexity of pure Nash equilibria
• Computing pure Nash and strong equilibria in bottleneck congestion games
• Congestion network problems and related games
• Nonlinear game models for large-scale network bandwidth management
• Computing Approximate Nash Equilibria in Network Congestion Games with Polynomially Decreasing Cost Functions
• On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games
• Computing equilibrium in network utility-sharing and discrete election games
• Congestion games with player-specific costs revisited
• Representation of finite games as network congestion games
• Congestion games with complementarities
• How hard is it to find extreme Nash equilibria in network congestion games?
• Congestion Games with Mixed Objectives
• On the impact of player capability on congestion games
• How to find Nash equilibria with extreme total latency in network congestion games?
• Computing Nash equilibria for two-player restricted network congestion games is \(\mathcal{PLS}\)-complete
• Congestion games with mixed objectives
• On the complexity of pure-strategy Nash equilibria in congestion and local-effect games
• Pure Nash equilibria in player-specific and weighted congestion games
• Pure Nash equilibria in a generalization of congestion games allowing resource failures

This page was built for publication: Complexity of pure Nash equilibria in player-specific network congestion games

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