The structure and complexity of Nash equilibria for a selfish routing game

DOI10.1016/j.tcs.2008.01.004zbMath1168.91331OpenAlexW2018136046WikidataQ59818493 ScholiaQ59818493MaRDI QIDQ838143

Marios Mavronicolas, Elias Koutsoupias, Dimitris Fotakis, Paul G. Spirakis, Spyros C. Kontogiannis

Publication date: 21 August 2009

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

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

zbMATH Keywords

Nash equilibriumalgorithmic game theoryselfish routing

Mathematics Subject Classification ID

Applications of graph theory (05C90) Games involving graphs (91A43) Deterministic network models in operations research (90B10)

Related Items (25)

Mechanisms for (mis)allocating scientific credit ⋮ A Glimpse at Paul G. Spirakis ⋮ A Selective Tour Through Congestion Games ⋮ Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions ⋮ Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy ⋮ Inefficiency of Nash equilibrium for scheduling games with constrained jobs: a parametric analysis ⋮ Maximizing the minimum load: the cost of selfishness ⋮ Selfish bin coloring ⋮ Temporal flows in temporal networks ⋮ Inefficiency of equilibria for scheduling game with machine activation costs ⋮ The price of anarchy on uniformly related machines revisited ⋮ Scheduling games with rank-based utilities ⋮ Congestion games with capacitated resources ⋮ Tight bounds for selfish and greedy load balancing ⋮ Approximate strong equilibria in job scheduling games with two uniformly related machines ⋮ Convergence of best-response dynamics in games with conflicting congestion effects ⋮ Single Parameter FPT-Algorithms for Non-trivial Games ⋮ The complexity of pure equilibria in mix-weighted congestion games on parallel links ⋮ The cost of selfishness for maximizing the minimum load on uniformly related machines ⋮ Window-games between TCP flows ⋮ Competitive routing over time ⋮ Selfish load balancing for jobs with favorite machines ⋮ The Price of Stability of Weighted Congestion Games ⋮ The Price of Stability of Weighted Congestion Games ⋮ A unifying approximate potential for weighted congestion games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• On total functions, existence theorems and computational complexity
• The price of anarchy for polynomial social cost
• On the structure and complexity of worst-case equilibria
• The price of selfish routing
• Nash and correlated equilibria: Some complexity considerations
• On the complexity of the parity argument and other inefficient proofs of existence
• Approximate equilibria and ball fusion
• Potential games
• Structure and complexity of extreme Nash equilibria
• Selfish unsplittable flows
• Non-cooperative games
• Tight bounds for worst-case equilibria
• The complexity of pure Nash equilibria
• Atomic Congestion Games Among Coalitions
• Monte-Carlo approximation algorithms for enumeration problems
• Allocating Bandwidth for Bursty Connections
• Balls and bins: A study in negative dependence
• STACS 2004
• Mathematical Foundations of Computer Science 2003
• Automata, Languages and Programming
• Bounds on Multiprocessing Timing Anomalies
• Automata, Languages and Programming
• Theoretical Computer Science
• Approximation and Online Algorithms
• Computing Nash equilibria for scheduling on restricted parallel links

This page was built for publication: The structure and complexity of Nash equilibria for a selfish routing game