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 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