Efficient methods for selfish network design

DOI10.1016/j.tcs.2012.04.033zbMath1243.68029OpenAlexW2035766543WikidataQ59818405 ScholiaQ59818405MaRDI QIDQ442104

Dimitris Fotakis, Alexis C. Kaporis, Paul G. Spirakis

Publication date: 9 August 2012

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

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

zbMATH Keywords

Nash equilibriumpolynomial-time algorithmBraess's paradoxequilibrium flow delayslinear latencyparadox-ridden networkreal-world networksselfish flows

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Applications of game theory (91A80)

Related Items (5)

A Glimpse at Paul G. Spirakis ⋮ A Selective Tour Through Congestion Games ⋮ Resolving Braess's paradox in random networks ⋮ Paradoxes in social networks with multiple products ⋮ Escaping Braess's paradox through approximate Caratheodory's theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Worst-case equilibria
• Selfish splittable flows and NP-completeness
• A polynomial algorithm for minimum quadratic cost flow problems
• Network topology and the efficiency of equilibrium
• The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions
• Stackelberg strategies for selfish routing in general multicommodity networks
• Uniqueness of solution in linear programming
• On sparse approximations to randomized strategies and convex combinations
• How much can taxes help selfish routing?
• On the severity of Braess's paradox: designing networks for selfish users is hard
• Simple strategies for large zero-sum games with applications to complexity theory
• How bad is selfish routing?
• Stackelberg Strategies for Atomic Congestion Games
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Stackelberg Scheduling Strategies
• Probability Inequalities for Sums of Bounded Random Variables
• Taxes for Linear Atomic Congestion Games
• Über ein Paradoxon aus der Verkehrsplanung
• Selfish Routing in Capacitated Networks
• Automata, Languages and Programming
• Convex separable optimization is not much harder than linear optimization
• Approximation and Online Algorithms
• The price of anarchy is independent of the network topology

This page was built for publication: Efficient methods for selfish network design