–
March 3, 2017
(joint work with R. Colini-Baldeschi, R. Cominetti and M. Scarsini)
====================================================================
ABSTRACT: The price of anarchy is a well-known concept which measures how the efficiency of a system (in our case, a traffic network) degrades due to the selfish behavior of its agents. In this talk, we will examine the asymptotic behavior of the price of anarchy in highly congested networks with multiple origin-destination pairs and general cost functions (not necessarily affine). On the one hand, we will discuss some simple (but otherwise carefully contrived) network examples where the price of anarchy may remain bounded away from 1 for all values of the traffic inflow. On the other hand, empirical studies have shown that the price of anarchy is close to 1 in highly congested real-world networks, so the question remains: under what assumptions can this behavior be justified analytically? To answer this, we will discuss a general result showing that for a large class of cost functions (defined in terms of regular variation and including all polynomials), the price of anarchy converges to 1 in the high congestion limit. In particular, specializing to networks with polynomial costs, we show that this convergence follows a power law whose degree and proportionality constant can be estimated explicitly.
