Price of anarchy on heterogeneous traffic-flow networks
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 indi...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Published: |
American Physical Society
2016
|
| Online Access: | https://eprints.nottingham.ac.uk/37094/ |
| _version_ | 1848795391125880832 |
|---|---|
| author | Rose, Alex M. O'Dea, Reuben D. Hopcraft, Keith I. |
| author_facet | Rose, Alex M. O'Dea, Reuben D. Hopcraft, Keith I. |
| author_sort | Rose, Alex M. |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T19:31:20Z |
| format | Article |
| id | nottingham-37094 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:31:20Z |
| publishDate | 2016 |
| publisher | American Physical Society |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-370942020-05-04T18:10:20Z https://eprints.nottingham.ac.uk/37094/ Price of anarchy on heterogeneous traffic-flow networks Rose, Alex M. O'Dea, Reuben D. Hopcraft, Keith I. 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. American Physical Society 2016-09-21 Article PeerReviewed Rose, Alex M., O'Dea, Reuben D. and Hopcraft, Keith I. (2016) Price of anarchy on heterogeneous traffic-flow networks. Physical Review E, 94 (3). 032315/1-032315/12. ISSN 1550-2376 http://journals.aps.org/pre/abstract/10.1103/PhysRevE.94.032315 doi:10.1103/PhysRevE.94.032315 doi:10.1103/PhysRevE.94.032315 |
| spellingShingle | Rose, Alex M. O'Dea, Reuben D. Hopcraft, Keith I. Price of anarchy on heterogeneous traffic-flow networks |
| title | Price of anarchy on heterogeneous traffic-flow networks |
| title_full | Price of anarchy on heterogeneous traffic-flow networks |
| title_fullStr | Price of anarchy on heterogeneous traffic-flow networks |
| title_full_unstemmed | Price of anarchy on heterogeneous traffic-flow networks |
| title_short | Price of anarchy on heterogeneous traffic-flow networks |
| title_sort | price of anarchy on heterogeneous traffic-flow networks |
| url | https://eprints.nottingham.ac.uk/37094/ https://eprints.nottingham.ac.uk/37094/ https://eprints.nottingham.ac.uk/37094/ |