The Price of Anarchy in Transportation Networks: Efficiency and Optimality Control

Abstract

Uncoordinated individuals in human society pursuing their personally optimal strategies do not always achieve the social optimum, the most beneficial state to the society as a whole. Instead, strategies form Nash equilibria which are often socially suboptimal. Society, therefore, has to pay a price of anarchy for the lack of coordination among its members. Here we assess this price of anarchy by analyzing the travel times in road networks of several major cities. Our simulation shows that uncoordinated drivers possibly waste a considerable amount of their travel time. Counterintuitively,simply blocking certain streets can partially improve the traffic conditions. We analyze various complex networks and discuss the possibility of similar paradoxes in physics.

major revisions with multicommodity; Phys. Rev. Lett., accepted

References in corpus (1)

• Optimal design of spatial distribution networks

Cited by in corpus (58)

• Understanding Road Usage Patterns in Urban Areas
• From the betweenness centrality in street networks to structural invariants in random planar graphs
• Designing optimal transport networks
• Morphology of travel routes and the organization of cities
• Braess's Paradox in Epidemic Game: Better Condition Results in Less Payoff
• The price of anarchy in basketball
• Nonlocal failures in complex supply networks by single link additions
• Flow Smoothing and Denoising: Graph Signal Processing in the Edge-Space
• A model to identify urban traffic congestion hotspots in complex networks
• Structure of complex networks: Quantifying edge-to-edge relations by failure-induced flow redistribution
• Transport inefficiency in branched-out mesoscopic networks: An analog of the Braess paradox
• Large cities are less efficient for sustainable transport: The ABC of mobility
• Braess's paradox and programmable behaviour in microfluidic networks
• Realizing Wardrop Equilbria with Real-Time Traffic Information
• Simplicial Convolutional Filters
• Exploring Maps with Greedy Navigators
• Dissolution of traffic jam via additional local interactions
• Antagonistic Phenomena in Network Dynamics
• Optimizing transport efficiency on scale-free networks through assortative or dissortative topology
• The Braess Paradox in a network of totally asymmetric exclusion processes
• The Price of Anarchy in Routing Games as a Function of the Demand
• Personalized Pareto-Improving Pricing-and-Routing Schemes for Near-Optimum Freight Routing: An Alternative Approach to Congestion Pricing
• Narrow peaks of full transmission in simple quantum graphs
• The Effect of Modern Traffic Information on Braess' Paradox
• A greedy-navigator approach to navigable city plans
• Universal Braess paradox in open quantum dots
• On the Price of Anarchy of Highly Congested Nonatomic Network Games
• A new transport phenomenon in nanostructures: A mesoscopic analog of the Braess paradox encountered in road networks
• Fair sharing of resources in a supply network with constraints
• Imitation dynamics in a game of traffic
• On the Braess Paradox with Nonlinear Dynamics and Control Theory
• Scalable Multiagent Driving Policies For Reducing Traffic Congestion
• The Price of Anarchy in Transportation Networks: Data-Driven Evaluation and Reduction Strategies
• A convergence analysis of the price of anarchy in atomic congestion games
• Bilevel Optimization for Traffic Mitigation in Optimal Transport Networks
• GAEA: Graph Augmentation for Equitable Access via Reinforcement Learning
• Traffic flow splitting from crowdsourced digital route choice support
• The price of anarchy is maximized at the percolation threshold
• Coordinating Dynamical Routes with Statistical Physics on Space-time Networks
• A link model approach to identify congestion hotspots
• When Big Data Fails! Relative success of adaptive agents using coarse-grained information to compete for limited resources
• Pathlength scaling in graphs with incomplete navigational information
• The global benefit of randomness in individual routing on transportation networks
• Phase Transitions of the Price-of-Anarchy Function in Multi-Commodity Routing Games
• Geometric properties of graph layouts optimized for greedy navigation
• Antifragility of stochastic transport on networks with damage
• Regulating Highly Automated Robot Ecologies: Insights from Three User Studies
• Antifragility and response to damage in the synchronization of oscillators on networks
• Network Reconstruction Problem for an Epidemic Reaction-Diffusion
• Bridging the user equilibrium and the system optimum in static traffic assignment: how the cooperation among drivers can solve the congestion problem in city networks
• A Dynamic Routing Framework for Shared Mobility Services
• Fast solver for diffusive transport times on dynamic intracellular networks
• Optimizing hospital distribution across districts for reducing tuberculosis fatalities
• Using Ensemble Analysis to study the effects of Network Topology on Performance in Urban Road Networks
• The Price of Governance: A Middle Ground Solution to Coordination in Organizational Control
• Identification and prioritization of urban traffic bottlenecks
• Equilibrium Inverse Reinforcement Learning for Ride-hailing Vehicle Network
• Linearly-Solvable Mean-Field Approximation for Multi-Team Road Traffic Games