Title: Braess's Paradox in Expanders
Abstract:
Expander graphs are known to facilitate effective routing and most real-world networks have expansion properties. At the other extreme, it has been shown that in some special graphs, removing certain edges can lead to more efficient routing. This phenomenon is known as Braess¹s paradox and is usually regarded as a rare event. In contrast to what one might expect, we show that Braess¹s paradox is ubiquitous in expander graphs. Specifically, we prove that Braess¹s paradox occurs in a large class of expander graphs with continuous convex latency functions. Our results extend previous work which held only when the graph was both denser and random and for random linear latency functions. We identify deterministic sufficient conditions for a graph with as few as a linear number of edges, such that Braess¹s Paradox almost always occurs, with respect to a general family of random latency functions. (Joint work with Fan Chung and Wenbo Zhao.)
