Undergraduate Individual Project

Under the context of traffic routing, selfish decision is often inefficient. As a driver, we would choose the route which shortens the travel time for self-interest, but it might not yield the shortest travel time overall from the perspective of a system. This scenario interests researchers: Can we design a network to minimise the inefficiency caused by selfish routing?

The loss from changing centralised optimal routing to distributed selfish routing, also known as the ”Price of Anarchy” (PoA), has been defined and quantified by Papadimitriou in 2001. A network with PoA close to 1 would mean that the network is efficient in the sense that the total cost from selfish routing is similar to that from optimal routing.

Formally, PoA is defined by the ratio of cost induced by Nash Equilibrium Flow and by Optimal Flow. Here the cost is a measure of loss when an agent travels through a road segment, for example travel time or gas consumed. The Nash Equilibrium Flow is achieved when each agents choose their travel routes based on their self-interest, whereas the Optimal Flow is achieved when each agents choose the travel routes which minimises the total cost imposed to the whole system.

Researchers such as Roughgarden and Terdos have shown upper bounds for PoA, which is also the worst-case analysis, for certain configurations of traffic networks. Once we know the PoA from a certain traffic network, we could decrease PoA, which is the loss due to selfish routing, by rerouting the network or to change the cost travelling on some path by marginal cost taxes, or tolls.

However, recent studies involving real-world data show a huge discrepancy between data-driven PoA and the theoretical upper bound as suggested. In particular, a study on traffic network in Singapore shows that the actual PoA would be 1.34, compared to the upper bound of 2.151. This discrepancy would translate into a loss 4 of over 730,000 hours per day for commuting in Singapore. Another study focused on real-world traffic network in Eastern Massachusetts concludes that the average PoA in a specific day’s afternoon would be 1.5522, compared to the upper bound of 3.299.

In practice, most of the real-world and synthetic data assumes that the traffic flow follows the Bureau of Public Roads functions which has a cost of the form $a + bx^4$, therefore the theories developed in this report also assumes traffic routing with this particular configuration.

Since PoA calculated from real-world data represents an average case, where the PoA from theory gives the worst-case upper bound, a natural question would arise: What are the fundamental differences between theory and data? In other words, would it be possible to lower the upper bound of theoretical PoA in order to reduce the discrepancy between theoretical and exact PoA? This project aims to answer these questions.

The project report can be found at here.