Tight Bounds for Worst-Case Equilibria

We study the problem of traffic routing in noncooperative networks. In such networks, users may follow selfish strategies to optimize their own performance measure and therefore, their behavior does not have to lead to optimal performance of the entire network. In this article we investigate the worst-case coordination ratio, which is a game-theoretic measure aiming to reflect the price of selfish routing. Following a line of previous work, we focus on the most basic networks consisting of parallel links with linear latency functions. Our main result is that the worst-case coordination ratio on m parallel links of possibly different speeds is Theta(log m/ log log log m). In fact, we are able to give an exact description of the worst-case coordination ratio, depending on the number of links and ratio of speed of the fastest link over the speed of the slowest link. For example, for the special case in which all m parallel links have the same speed, we can prove that the worst-case coordination ratio is Gamma((-1))(m) + Theta(1), with Gamma denoting the Gamma (factorial) function. Our bounds entirely resolve an open problem posed recently by Koutsoupias and Papadimitriou [1999].