On the severity of Braess's paradox: designing networks for selfish users is hard
From MaRDI portal
Publication:2496322
DOI10.1016/j.jcss.2005.05.009zbMath1094.68122OpenAlexW1969954905MaRDI QIDQ2496322
Publication date: 12 July 2006
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2005.05.009
Noncooperative games (91A10) Deterministic network models in operations research (90B10) Traffic problems in operations research (90B20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Stackelberg thresholds in network routing games or the value of altruism ⋮ Coincident cost improvement vs. Degradation by adding connections to noncooperative networks and distributed systems ⋮ Excluding Braess’s Paradox in Nonatomic Selfish Routing ⋮ Efficient coordination mechanisms for unrelated machine scheduling ⋮ Allocation of flows in closed bipartite queueing networks ⋮ A Selective Tour Through Congestion Games ⋮ Network design to anticipate selfish evacuation routing ⋮ Collusion in atomic splittable routing games ⋮ Braess's paradox for flows over time ⋮ Resolving Braess's paradox in random networks ⋮ Negative prices in network pricing games ⋮ On the hardness of network design for bottleneck routing games ⋮ Inefficiencies in network models: a graph-theoretic perspective ⋮ Complexity and Approximation of the Continuous Network Design Problem ⋮ Modifying link capacity to avoid Braess paradox considering elastic demand ⋮ Braess' paradox: A cooperative game‐theoretic point of view ⋮ Depletable channels: dynamics, behaviour, and efficiency in network design ⋮ Efficient methods for selfish network design ⋮ Degrading network capacity may improve performance: private versus public monitoring in the Braess paradox ⋮ Network congestion control with Markovian multipath routing ⋮ Selfish splittable flows and NP-completeness ⋮ The impact of worst-case deviations in non-atomic network routing games ⋮ Optimal routing for multiclass networks ⋮ A polynomial-time algorithm for detecting the possibility of Braess paradox in directed graphs ⋮ Inefficiency in stochastic queueing systems with strategic customers ⋮ Network characterizations for excluding Braess's paradox ⋮ Quantum games: a review of the history, current state, and interpretation ⋮ Detecting Braess paradox based on stable dynamics in general congested transportation networks ⋮ Sensitivity of Wardrop equilibria ⋮ Locating inefficient links in a large-scale transportation network ⋮ Achieving target equilibria in network routing games without knowing the latency functions ⋮ Braess's Paradox in large random graphs ⋮ Sensitivity of Wardrop Equilibria ⋮ Dynamic Atomic Congestion Games with Seasonal Flows ⋮ Risk-Averse Selfish Routing ⋮ Informational Braess’ Paradox: The Effect of Information on Traffic Congestion ⋮ Stackelberg strategies for selfish routing in general multicommodity networks ⋮ The Impact of Worst-Case Deviations in Non-Atomic Network Routing Games ⋮ Polynomial recognition of vulnerable multi-commodities ⋮ Escaping Braess's paradox through approximate Caratheodory's theorem ⋮ Braess's paradox in expanders ⋮ On the Braess paradox with nonlinear dynamics and control theory ⋮ Network Pricing: How to Induce Optimal Flows Under Strategic Link Operators
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The directed subgraph homeomorphism problem
- Counterexamples for comparisons of queues with finite waiting rooms
- Geometric algorithms and combinatorial optimization
- The price of anarchy for non-atomic congestion games with symmetric cost maps and elastic demands.
- Avoiding paradoxes in multi-agent competitive routing.
- Bounding the inefficiency of equilibria in nonatomic congestion games
- Network economics: a variational inequality approach
- How much can taxes help selfish routing?
- Braess-like paradoxes in distributed computer systems
- Queue Spillovers in Transportation Networks with a Route Choice
- On a network creation game
- Capacity allocation under noncooperative routing
- Proof verification and the hardness of approximation problems
- How bad is selfish routing?
- Technical Note—Traffic Equilibrium Paradoxes
- Selfish traffic allocation for server farms
- Near-optimal network design with selfish agents
- Pricing network edges for heterogeneous selfish users
- Inefficiency of Nash Equilibria
- The Prevalence of Paradoxes in Transportation Equilibrium Problems
- Probabilistic checking of proofs
- The Braess paradox
- BRAESS' PARADOX IN A TWO-TERMINAL TRANSPORTATION NETWORK
- Network routing
- Exact and approximate algorithms for optimal network design
- Avoiding the Braess paradox in non-cooperative networks
- Braess's paradox and power-law nonlinearities in networks
- Properties of Dynamic Traffic Equilibrium Involving Bottlenecks, Including a Paradox and Metering
- Braess's paradox in a queueing network with state-dependent routing
- Braess's paradox in a loss network
- Interactive proofs and the hardness of approximating cliques
- Stackelberg Scheduling Strategies
- The price of selfish routing
- Algorithms, games, and the internet
- The Downs-Thomson Effect in a Markov Process
- Traffic assignment problem for a general network
- A Computational Approach to the Selection of an Optimal Network
- Selfish Routing in Capacitated Networks
- Integer Programming and Combinatorial Optimization
- Automata, Languages and Programming
- A paradox of congestion in a queuing network
- The price of anarchy is independent of the network topology
