The price of anarchy is independent of the network topology

DOI10.1016/S0022-0000(03)00044-8zbMath1072.68025OpenAlexW3000411098MaRDI QIDQ5917582

Publication date: 18 November 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(03)00044-8

zbMATH Keywords

network performance

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Traffic problems in operations research (90B20)

Related Items (66)

On the Existence of Optimal Taxes for Network Congestion Games with Heterogeneous Users ⋮ Worst-case analysis of non-cooperative load balancing ⋮ Adaptive routing with stale information ⋮ The Price of Matching with Metric Preferences ⋮ Allocation of flows in closed bipartite queueing networks ⋮ On a generalized Cournot oligopolistic competition game ⋮ Network topology and the efficiency of equilibrium ⋮ Optimal externalities in a parallel transportation network ⋮ Routing-proofness in congestion-prone networks ⋮ A convergence analysis of the price of anarchy in atomic congestion games ⋮ Complexity and Approximation of the Continuous Network Design Problem ⋮ The Value of Information in Selfish Routing ⋮ The price of anarchy in loss systems ⋮ Price of anarchy for parallel link networks with generalized mean objective ⋮ Inefficiency of pure Nash equilibria in series-parallel network congestion games ⋮ On poisoned Wardrop equilibrium in congestion games ⋮ The price of anarchy in series-parallel network congestion games ⋮ Transportation network with externalities ⋮ Exact price of anarchy for weighted congestion games with two players ⋮ The price of anarchy in routing games as a function of the demand ⋮ Price of Anarchy in Networks with Heterogeneous Latency Functions ⋮ Pairwise cooperations in selfish ring routing for minimax linear latency ⋮ Unnamed Item ⋮ When is Selfish Routing Bad? The Price of Anarchy in Light and Heavy Traffic ⋮ Stability vs. optimality in selfish ring routing ⋮ Non-atomic one-round walks in congestion games ⋮ The price of anarchy in an exponential multi-server ⋮ Price of anarchy for highly congested routing games in parallel networks ⋮ Toll caps in privatized road networks ⋮ The worst absolute surplus loss in the problem of commons: random priority versus average cost ⋮ Computation and efficiency of potential function minimizers of combinatorial congestion games ⋮ Inefficiency in stochastic queueing systems with strategic customers ⋮ Bounding the inefficiency of Nash equilibria in games with finitely many players ⋮ Fragile networks: identifying vulnerabilities and synergies in an uncertain age ⋮ Extending the notion of rationality of selfish agents: second order Nash equilibria ⋮ Stackelberg strategies and collusion in network games with splittable flow ⋮ Optimal routing of vehicles with communication capabilities in disasters ⋮ A selfish routing based network improvement problem ⋮ The price of atomic selfish ring routing ⋮ How much can taxes help selfish routing? ⋮ On the severity of Braess's paradox: designing networks for selfish users is hard ⋮ Computer science and decision theory ⋮ Equilibria for networks with malicious users ⋮ Stackelberg strategies for atomic congestion games ⋮ Congestion games with linearly independent paths: convergence time and price of anarchy ⋮ Tradeoffs in worst-case equilibria ⋮ Stackelberg Strategies and Collusion in Network Games with Splittable Flow ⋮ A note on a parameter relating traffic equilibria and system optimal routing ⋮ Achieving target equilibria in network routing games without knowing the latency functions ⋮ The price of anarchy of affine congestion games with similar strategies ⋮ On the efficiency of equilibria in mean-field oscillator games ⋮ Optimal deterministic auctions with correlated priors ⋮ Nonadaptive Selfish Routing with Online Demands ⋮ Congestion Games with Linearly Independent Paths: Convergence Time and Price of Anarchy ⋮ Selfish routing in public services ⋮ A geometric approach to the price of anarchy in nonatomic congestion games ⋮ Risk-Averse Selfish Routing ⋮ Stackelberg strategies for selfish routing in general multicommodity networks ⋮ Efficiency of Equilibria in Uniform Matroid Congestion Games ⋮ On the Price of Anarchy of Highly Congested Nonatomic Network Games ⋮ Management of Variable Data Streams in Networks ⋮ Efficiency of atomic splittable selfish routing with polynomial cost functions ⋮ Bounding the inefficiency of logit-based stochastic user equilibrium ⋮ Selfishness Need Not Be Bad ⋮ A Mean-Risk Model for the Traffic Assignment Problem with Stochastic Travel Times ⋮ Bottleneck links, variable demand, and the tragedy of the commons

Cites Work

This page was built for publication: The price of anarchy is independent of the network topology