How bad is selfish routing?

DOI10.1145/506147.506153zbMATH Open1323.90011OpenAlexW2112269231WikidataQ56386816 ScholiaQ56386816MaRDI QIDQ3196642FDOQ3196642

Authors: Tim Roughgarden, Éva Tardos 

Publication date: 30 October 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.147.1081

Recommendations

• Selfish routing
• When is selfish routing bad? The price of anarchy in light and heavy traffic
• The price of selfish routing
• The price of selfish routing
• SOFSEM 2006: Theory and Practice of Computer Science
• How much can taxes help selfish routing?
• scientific article; zbMATH DE number 2119661
• Algorithms – ESA 2004
• Selfish Routing with Oblivious Users
• Selfish routing in public services

zbMATH Keywords

network flowNash equilibriaselfish routingBraess's paradox

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Applications of game theory (91A80) Noncooperative games (91A10)

Cited In (only showing first 100 items - show all)

• Introduction to the special issue -- Algorithmic game theory -- STOC/FOCS/SODA 2011
• On the price of anarchy of two-stage machine scheduling games
• Recursively modeling other agents for decision making: a research perspective
• Equilibria for networks with malicious users
• Continuum equilibria and global optimization for routing in dense static ad hoc networks
• Optimal routing of vehicles with communication capabilities in disasters
• The impact of local policies on the quality of packet routing in paths, trees, and rings
• Agent-based randomized broadcasting in large networks
• Potential games, path independence and Poisson's binomial distribution
• Toll caps in privatized road networks
• The inefficiency of Nash and subgame perfect equilibria for network routing
• Braess' paradox: A cooperative game‐theoretic point of view
• A game-theoretic analysis of deep neural networks
• Game-theoretic analysis of Internet switching with selfish users
• An abstraction-refinement methodology for reasoning about network games
• A note on a parameter relating traffic equilibria and system optimal routing
• On the (in)efficiency of MFG equilibria
• Achieving target equilibria in network routing games without knowing the latency functions
• Two-terminal routing games with unknown active players
• Competitive online multicommodity routing
• Agent incentives of a proportional sharing mechanism in resource sharing
• Dynamic resource allocation games
• Title not available (Why is that?)
• Timed network games
• Scheduling to Maximize Participation
• Edge pricing of multicommodity networks for selfish users with elastic demands
• Collusion in atomic splittable routing games
• Linear tolls suffice: new bounds and algorithms for tolls in single source networks
• Transfer implementation in congestion games
• Sensitivity of Wardrop Equilibria
• Online learning of Nash equilibria in congestion games
• Equilibria of greedy combinatorial auctions
• Management of Variable Data Streams in Networks
• A paradox in optimal flow control of \(M/M/n\) queues
• Strategic pricing in next-hop routing with elastic demands
• On cost sharing in the provision of a binary and excludable public good
• A mathematical model for the TCP tragedy of the commons
• Sensitivity of Wardrop equilibria
• Capacitated network design games
• A network pricing game for selfish traffic
• The Price of Stochastic Anarchy
• Topological price of anarchy bounds for clustering games on networks
• Bottleneck links, variable demand, and the tragedy of the commons
• Competitive contagion in networks
• The price of stability of weighted congestion games
• The price of stability of weighted congestion games
• A bin packing game with cardinality constraints under the best cost rule
• Scheduling to maximize participation
• Sensitivity of wardrop equilibria: revisited
• Optimal cost-sharing in general resource selection games
• The price of anarchy of affine congestion games with similar strategies
• Recent studies of agent incentives in internet resource allocation and pricing
• The no-wait flow-shop paradox
• Resilience of routing in parallel link networks
• The uniqueness property for networks with several origin-destination pairs
• On the Braess paradox with nonlinear dynamics and control theory
• Parametric packing of selfish items and the subset sum algorithm
• The price of anarchy for non-atomic congestion games with symmetric cost maps and elastic demands.
• Selfish bin packing
• Some anomalies of farsighted strategic behavior
• Online bottleneck matching
• Bounding the inefficiency of equilibria in nonatomic congestion games
• Decompositions and potentials for normal form games
• Action-graph games
• Strong price of anarchy
• The price of selfish routing
• On the existence of pure Nash equilibria in weighted congestion games
• Two-group knapsack game
• Robust perfect equilibrium in large games
• Graphical congestion games
• Tight bounds for selfish and greedy load balancing
• Almost budget-balanced VCG mechanisms to assign multiple objects
• Tight bounds for cost-sharing in weighted congestion games
• The toll effect on price of anarchy when costs are nonlinear and asymmetric
• An efficient and almost budget balanced cost sharing method
• How much can taxes help selfish routing?
• Measuring the power of soft correlated equilibrium in 2-facility simple non-increasing linear congestion games
• A geometric approach to the price of anarchy in nonatomic congestion games
• A survey on networking games in telecommunications
• Adaptive routing with stale information
• Design of price mechanisms for network resource allocation via price of anarchy
• ``Beat-your-rival routing games
• The Price of Anarchy on Uniformly Related Machines Revisited
• Computational social choice for coordination in agent networks
• Stackelberg thresholds in network routing games or the value of altruism
• Strong equilibrium in cost sharing connection games
• A generalization of correlated equilibrium: a new protocol
• On the performance of approximate equilibria in congestion games
• Computing approximate Nash equilibria in network congestion games
• The price of anarchy of serial, average and incremental cost sharing
• Atomic routing games on maximum congestion
• Strategic decentralization in binary choice composite congestion games
• Choice of routes in congested traffic networks: Experimental tests of the Braess paradox
• Stackelberg strategies for selfish routing in general multicommodity networks
• Congestion games with linearly independent paths: convergence time and price of anarchy
• On the severity of Braess's paradox: designing networks for selfish users is hard
• A note on a selfish bin packing problem
• Demand allocation with latency cost functions
• Computing Approximate Nash Equilibria in Network Congestion Games
• Stackelberg strategies and collusion in network games with splittable flow

This page was built for publication: How bad is selfish routing?

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