Corelab Seminar

Panayotis Mertikopoulos
Traffic Routing: Efficiency, Equilibrium and Dynamics

Traffic routing in congested networks is a notoriously difficult problem, usually leading to droves of disgruntled commuters. The most widely used measure of inefficiency for such problems is the so-called price of anarchy, i.e. the ratio between the aggregate latency at equilibrium (that is, when each individual traffic element is unilaterally satisfied with its choice of path) and the least possible aggregate latency. Depending on the structure of the network and its delay functions, different worst-case bounds have been established for the price of anarchy, perhaps the most famous of which is the 4/3 bound of Roughgarden and Tardos (2002) for networks with affine costs. In practice however, the price of anarchy tends to be significantly lower than these worst-case bounds would suggest, and several empirical studies in real-world networks show that it becomes negligible in both light and heavy traffic. This talk will focus on whether this disconnect between theory and practice can be justified theoretically, and what kind of algorithmic schemes can be used to steer a traffic network to equilibrium in an efficient manner.