Resolving Braess's Paradox in Random Networks

Fotakis, D, Kaporis, A, Lianeas, T and Spirakis, PG
(2017) Resolving Braess's Paradox in Random Networks. Algorithmica, 78 (03). 788 - 818.

[img] Text
fkls-algo-10-2-2016.pdf - Accepted Version

Download (1MB)


Braess’s paradox states that removing a part of a network may improve the players’ latency at equilibrium. In this work, we study the approximability of the best subnetwork problem for the class of random Gn,p instances proven prone to Braess’s paradox by Valiant and Roughgarden RSA ’10 (Random Struct Algorithms 37(4):495–515, 2010), Chung and Young WINE ’10 (LNCS 6484:194–208, 2010) and Chung et al. RSA ’12 (Random Struct Algorithms 41(4):451–468, 2012). Our main contribution 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 neighbors of source s and destination t are directly connected by 0 latency edges. Building on this, we consider two cases, either when the total rate r is sufficiently low, or, when r is sufficiently high. In the first case of low r=O(n+), here n+ is the maximum degree of {s,t}, we obtain an approximation scheme that for any constant ε>0 and with high probability, computes a subnetwork and an ε-Nash flow with maximum latency at most (1+ε)L∗+ε, where L∗ is the equilibrium latency of the best subnetwork. Our approximation scheme runs in polynomial time if the random network has average degree O(poly(lnn)) and the traffic rate is O(poly(lnlnn)), and in quasipolynomial time for average degrees up to o(n) and traffic rates of O(poly(lnn)). Finally, in the second case of high r=Ω(n+), we compute in strongly polynomial time a subnetwork and an ε-Nash flow with maximum latency at most (1+2ε+o(1))L∗.

Item Type: Article
Uncontrolled Keywords: Algorithmic game theory, Braess’s paradox, Seflish routing, Wardrop equilibrium, Random graphs
Depositing User: Symplectic Admin
Date Deposited: 09 Jun 2016 09:22
Last Modified: 08 Aug 2021 20:10
DOI: 10.1007/s00453-016-0175-2
Related URLs: