Linde Institute/Social and Information Sciences Laboratory (SISL) Seminar
Stability and Robustness of Dynamical Network Flows
Network flow provides a compelling framework to model a variety of infrastructure networks including transportation. In this talk, we first present a dynamical framework for single-commodity transportation networks with dynamic local route choice decisions by drivers. Such local decisions, when augmented with classical (global) best response, give rise to a multiscale congestion game framework. We identify a class of local decision rules that guarantee stability of Wardrop equilibrium in this new formulation.
We then analyze stability and robustness of general dynamical network flows, where local decision rules are interpreted as distributed routing policies. The evolution of this dynamical model under capacity constraints exhibits forward and backward cascading effects that are qualitatively different than standard percolation models. We relate stability to network throughput and provide necessary and sufficient conditions for maximal stability. These conditions could be interpreted as a dynamical counterpart to the celebrated max-flow min-cut theorem for static networks. Robustness is studied with respect to adversarial disturbances that reduce link-wise flow capacities, and robust stability margin is defined as the minimum among all such disturbances that make the network become unstable. We present exact computation of this margin under several scenarios.
Contact: Jenny Niese at Ext. 6010 firstname.lastname@example.org