Network Topology That Excludes Braess's Paradox and Maintains Monotonicity in Flows Over Time

Source abstract

In the game of \emph{flow over time}, infinitesimal flow particles aim to travel from a source to a sink in a network as quickly as possible. Under the Vickrey bottleneck model, the congestion effects on network edges are captured through FIFO queues, which arise when the inflow into an edge exceeds its capacity. This work addresses two open conjectures about the game: 1) the characterization of networks that are immune to Braess's paradox, and 2) the monotonicity relationship between the network inflow rate and the overall flow makespan. We show that a single class of network topologies, called \emph{chains of bipolar pseudo-arborescences} (\emph{BPAs}), fully resolves the first conjecture and yields partial progress on the second. Chains of BPAs constitute precisely the cases left open by Macko et al.~(2013) in their study of Braess's paradox for flow over time. By structurally characterizing the dynamic evolution of Nash flows over time on such networks, we prove that removing edges from these networks never decreases the maximum equilibrium latency. Combined with the results of Macko et al., this establishes a necessary and sufficient condition: \emph{a network does not admit Braess's paradox for flow over time if and only if it is a chain of BPAs}, thereby resolving their conjecture. Furthermore, we confirm the monotonicity conjecture of Correa et al.~(2021) for all chains of BPAs. This result strictly generalizes the previously known monotonicity for chains of parallel paths under uniform inflows.