Stability vs. optimality in selfish ring routing

DOI10.1007/S10114-014-3055-1MaRDI QIDQ2453835zbMATH OpenOpenAlexFDO

Authors Bo Chen, Jie Hu, Xujin Chen

Publication date 11 June 2014

Published in Acta Mathematica Sinica, English Series (Search for Journal in Brave)

Full work available at URL http://wrap.warwick.ac.uk/2535/1/WRAP_Chen_9471193-wbs-060110-submitted_version.pdf

zbMATH Keywords

minimum maximum linear latencyprice of stabilityselfish routing

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Games involving graphs (91A43)

Recommendations

• The price of atomic selfish ring routing
• Reducing the maximum latency of selfish ring routing via pairwise cooperations
• Pairwise cooperations in selfish ring routing for minimax linear latency
• Tradeoffs and average-case equilibria in selfish routing
• The price of selfish routing

Cites work

• A class of games possessing pure-strategy Nash equilibria
• Algorithms – ESA 2004
• Atomic Routing Games on Maximum Congestion
• Automata, Languages and Programming
• Congestion Games with Linearly Independent Paths: Convergence Time and Price of Anarchy
• Convergence time to Nash equilibrium in load balancing
• Fast, Fair, and Efficient Flows in Networks
• How bad is selfish routing?
• scientific article; zbMATH DE number 1830730 (Why is no real title available?)
• Improved Approximation Algorithms for the Demand Routing and Slotting Problem with Unit Demands on Rings
• Linear time algorithms for the ring loading problem with demand splitting
• Multicuts and integral multiflows in rings
• On the impact of combinatorial structure on congestion games
• Potential games
• Selfish unsplittable flows
• Stronger bounds on Braess's paradox and the maximum latency of selfish routing
• The complexity of pure Nash equilibria
• The price of anarchy for polynomial social cost
• The price of anarchy is independent of the network topology
• The price of anarchy of finite congestion games
• The price of atomic selfish ring routing
• The price of routing unsplittable flow
• The Price of Stability for Network Design with Fair Cost Allocation
• The Ring Loading Problem
• Worst-case equilibria

Cited in

(4)

• Reducing the maximum latency of selfish ring routing via pairwise cooperations
• Pairwise cooperations in selfish ring routing for minimax linear latency
• On the complexity of greedy routing in ring-based peer-to-peer networks
• The price of atomic selfish ring routing

This page was built for publication: Stability vs. optimality in selfish ring routing

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