Atomic routing games on maximum congestion

DOI10.1016/j.tcs.2009.04.015zbMath1168.91328OpenAlexW2059997911MaRDI QIDQ838146

Malik Magdon-Ismail, Costas Busch

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.2009.04.015

zbMATH Keywords

Nash equilibriumprice of anarchyalgorithmic game theorycongestion gamerouting game

Mathematics Subject Classification ID

Applications of graph theory (05C90) Games involving graphs (91A43) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (11)

Bottleneck Congestion Games with Logarithmic Price of Anarchy ⋮ On the Inefficiency of Equilibria in Linear Bottleneck Congestion Games ⋮ Computation of equilibria and the price of anarchy in bottleneck congestion games ⋮ Bottleneck Routing with Elastic Demands ⋮ Computing pure Nash and strong equilibria in bottleneck congestion games ⋮ On the hardness of network design for bottleneck routing games ⋮ Bottleneck routing with elastic demands ⋮ The strong price of anarchy of linear bottleneck congestion games ⋮ “Beat-Your-Rival” Routing Games ⋮ Balancing Load via Small Coalitions in Selfish Ring Routing Games ⋮ Bottleneck links, variable demand, and the tragedy of the commons

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The price of anarchy for polynomial social cost
• Selfish load balancing and atomic congestion games
• A new model for selfish routing
• Nash equilibria in discrete routing games with convex latency functions
• The price of selfish routing
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• Approximate equilibria and ball fusion
• Potential games
• Bounding the inefficiency of equilibria in nonatomic congestion games
• Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
• A class of games possessing pure-strategy Nash equilibria
• Selfish unsplittable flows
• How bad is selfish routing?
• The Price of Stability for Network Design with Fair Cost Allocation
• Selfish traffic allocation for server farms
• Near-optimal network design with selfish agents
• The price of anarchy of finite congestion games
• Algorithms, games, and the internet
• Approximating Congestion + Dilation in Networks via "Quality of Routing” Games
• The Influence of Link Restrictions on (Random) Selfish Routing
• Automata, Languages and Programming
• Integer Programming and Combinatorial Optimization
• Approximation and Online Algorithms
• Tradeoffs and Average-Case Equilibria in Selfish Routing
• Computing Nash equilibria for scheduling on restricted parallel links
• Optimal oblivious routing in polynomial time
• The Price of Routing Unsplittable Flow
• Atomic resource sharing in noncooperative networks

This page was built for publication: Atomic routing games on maximum congestion