Price of anarchy on heterogeneous traffic-flow networks

Rose, Alex M.; O'Dea, Reuben D.; Hopcraft, Keith I.

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 minimise their individual expenditure to the optimal cost borne by the entire system. As the total traffic load and the network variability - parameterised by the proportion of variable-cost links in the network - changes, the behaviours that the system presents can be understood with the introduction of a network of simpler structure. This is constructed from classes of non-overlapping paths connecting source to destination nodes that are characterised by the number of variable-cost edges they contain. It is shown that localised 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.

Citation

Rose, A. M., O'Dea, R. D., & Hopcraft, K. I. (2016). Price of anarchy on heterogeneous traffic-flow networks. Physical Review E, 94(3), Article 032315. https://doi.org/10.1103/PhysRevE.94.032315

• Journal Article Type: Article
• Acceptance Date: Aug 25, 2016
• Publication Date: Sep 21, 2016
• Deposit Date: Sep 23, 2016
• Publicly Available Date: Sep 23, 2016
• Journal: Physical Review E
• Print ISSN: 2470-0045
• Electronic ISSN: 2470-0053
• Publisher: American Physical Society
• Peer Reviewed: Peer Reviewed
• Volume: 94
• Issue: 3
• Article Number: 032315
• DOI: https://doi.org/10.1103/PhysRevE.94.032315
• Public URL: https://nottingham-repository.worktribe.com/output/810059
• Publisher URL: http://journals.aps.org/pre/abstract/10.1103/PhysRevE.94.032315
• Related Public URLs: https://journals.aps.org/pre/abstract/10.1103/PhysRevE.94.032315
• Contract Date: Sep 23, 2016