Resolving the Paradox of Braess in Random Networks

The paradox of Braess states that removing a part of a network may improve the latency of (selfish) travellers at equilibrium! Here, we address the approximability of the best subnetwork problem (the subnet with the minimum equilibrium latency) for the class of Gn,p instances, proven prone to the Paradox in recent works. Our main result is a polynomial time approximation-preserving reduction of the best subnetwork problem for such instances to the corresponding problem in a simplified network, where all neighbours of s and t are directly connected by zero latency edges. We build on this and obtain an efficient scheme that computes a subnetwork and an epsilon-Nah flow with maximum latency at most (1+epsilon) L + epsilon, where L is the equilibrium latency of the best subnetwork. This is joint work with D. Fotakis, A. Kaporis and Th. Lianeas, and will be also presented in WINE 2013.