Price of anarchy on heterogeneous traffic-flow networks

A. Rose, R. O'Dea, and K. I. Hopcraft
Phys. Rev. E 94, 032315 – Published 21 September 2016

Abstract

The efficiency of routing traffic through a network, comprising nodes connected by links whose cost of traversal is either fixed or varies in proportion to volume of usage, can be measured by the “price of anarchy.” This is the ratio of the cost incurred by agents who act to minimize their individual expenditure to the optimal cost borne by the entire system. As the total traffic load and the network variability—parameterized by the proportion of variable-cost links in the network—changes, the behaviors that the system presents can be understood with the introduction of a network of simpler structure. This is constructed from classes of nonoverlapping paths connecting source to destination nodes that are characterized by the number of variable-cost edges they contain. It is shown that localized peaks in the price of anarchy occur at critical traffic volumes at which it becomes beneficial to exploit ostensibly more expensive paths as the network becomes more congested. Simulation results verifying these findings are presented for the variation of the price of anarchy with the network's size, aspect ratio, variability, and traffic load.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
1 More
  • Received 20 May 2016
  • Revised 3 August 2016

DOI:https://doi.org/10.1103/PhysRevE.94.032315

©2016 American Physical Society

Physics Subject Headings (PhySH)

NetworksInterdisciplinary Physics

Authors & Affiliations

A. Rose, R. O'Dea, and K. I. Hopcraft

  • School of Mathematical Sciences, University of Nottingham, Nottingham NG7 2RD, United Kingdom

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 94, Iss. 3 — September 2016

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×