Braess' Paradox in Uniform Affine Grid Networks

Abstract

Braess' Paradox is the phenomenon in which adding an edge to a congestion network increases total travel time. We study the paradox in directed rectangular grids where every edge shares the latency function $\ell (x)=ax+b$ and an added chord has latency ${\ell }_{\ast }(x)=cx+d$, where $a>0$ and $b,c,d\ge 0$. Using an analogy with electrical networks, we bound the change in total travel time. We then give a necessary and sufficient condition for a chord to induce the paradox for some choice of nonnegative coefficients and compute the exact proportion of such chords in all grids with dimensions at most $100$. Such chords are scarce, and the fraction is maximized near an aspect ratio of $2:1$. We then improve the established $4/3$ upper bound on the Braess Ratio to one depending only on the grid dimensions, approaching $1.207$ on squares and $4/3$ on thin grids. Finally, we prove any ratio-maximizing chord must have zero latency.