The complexity of pure equilibria in mix-weighted congestion games on parallel links

DOI10.1016/J.IPL.2015.07.012zbMath1338.68114OpenAlexW934731919MaRDI QIDQ495670

Marios Mavronicolas, Burkhard Monien

Publication date: 15 September 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2015.07.012

zbMATH Keywords

algorithmsNP-completenesscongestion games on parallel linkspure equilibria

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Worst-case equilibria
• The structure and complexity of Nash equilibria for a selfish routing game
• Congestion games with player-specific payoff functions
• A class of games possessing pure-strategy Nash equilibria
• Selfish unsplittable flows
• On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games
• Routing (un-) splittable flow in games with player-specific affine latency functions
• On the impact of combinatorial structure on congestion games
• Complexity of Pure Nash Equilibria in Player-Specific Network Congestion Games
• The complexity of pure Nash equilibria
• Bounds for Certain Multiprocessing Anomalies
• Atomic resource sharing in noncooperative networks

This page was built for publication: The complexity of pure equilibria in mix-weighted congestion games on parallel links