The price of selfish routing

DOI10.1145/380752.380846zbMath1323.91006OpenAlexW2030914480MaRDI QIDQ5176009

Marios Mavronicolas, Paul G. Spirakis

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380846

Mathematics Subject Classification ID

Noncooperative games (91A10) Games involving graphs (91A43) Deterministic network models in operations research (90B10) Traffic problems in operations research (90B20)

Related Items (32)

On the complexity of constrained Nash equilibria in graphical games ⋮ On the convergence of multicast games in directed networks ⋮ The price of anarchy for polynomial social cost ⋮ A note on a selfish bin packing problem ⋮ On a generalized Cournot oligopolistic competition game ⋮ Utilitarian resource assignment ⋮ Nonpreemptive coordination mechanisms for identical machines ⋮ On the structure and complexity of worst-case equilibria ⋮ Non-preemptive Coordination Mechanisms for Identical Machine Scheduling Games ⋮ Game-theoretic static load balancing for distributed systems ⋮ Selfish Bin Packing ⋮ Load balancing without regret in the bulletin board model ⋮ Scheduling to maximize participation ⋮ Selfish routing with incomplete information ⋮ Selfish bin packing ⋮ Mixed Nash equilibria in selfish routing problems with dynamic constraints ⋮ How to find Nash equilibria with extreme total latency in network congestion games? ⋮ Evolutionary equilibrium in Bayesian routing games: specialization and niche formation ⋮ On the severity of Braess's paradox: designing networks for selfish users is hard ⋮ Window-games between TCP flows ⋮ Equilibria for networks with malicious users ⋮ Tradeoffs in worst-case equilibria ⋮ Scheduling to Maximize Participation ⋮ The price of anarchy is independent of the network topology ⋮ Selfish Routing and Path Coloring in All-Optical Networks ⋮ The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions ⋮ The Price of Anarchy on Uniformly Related Machines Revisited ⋮ How hard is it to find extreme Nash equilibria in network congestion games? ⋮ Two-terminal routing games with unknown active players ⋮ Structure and complexity of extreme Nash equilibria ⋮ Selfish unsplittable flows ⋮ On the sequential price of anarchy of isolation games

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: The price of selfish routing