1 February 2013 in Mathematics of Operations Research
We study a tractable opinion dynamics model that generates long-run disagreements and persistent opinion fluctuations. Our model involves an inhomogeneous stochastic gossip process of continuous opinion dynamics in a society consisting of two types of agents: (1) regular agents who update their beliefs according to information that they receive from their social neighbors and (2) stubborn agents who never update their opinions and might represent leaders, political parties, or media sources attempting to influence the beliefs in the rest of the society. When the society contains stubborn agents with different opinions, the belief dynamics never lead to a consensus (among the regular agents). Instead, beliefs in the society fail to converge almost surely, the belief profile keeps on fluctuating in an ergodic fashion, and it converges in law to a nondegenerate random vector. The structure of the graph describing the social network and the location of the stubborn agents within it shape the opinion dynamics. The expected belief vector is proved to evolve according to an ordinary differential equation coinciding with the Kolmogorov backward equation of a continuous-time Markov chain on the graph with absorbing states corresponding to the stubborn agents, and hence to converge to a harmonic vector, with every regular agent's value being the weighted average of its neighbors' values, and boundary conditions corresponding to the stubborn agents' beliefs. Expected cross products of the agents' beliefs allow for a similar characterization in terms of coupled Markov chains on the graph describing the social network. We prove that, in large-scale societies, which are highly fluid, meaning that the product of the mixing time of the Markov chain on the graph describing the social network and the relative size of the linkages to stubborn agents vanishes as the population size grows large, a condition of homogeneous influence emerges, whereby the stationary beliefs' marginal distributions of most of the regular agents have approximately equal first and second moments.
23 July 2012 in IEEE Transactions on Automatic Control
Robustness of distributed routing policies is studied for dynamical networks, with respect to adversarial disturbances that reduce the link flow capacities. A dynamical network is modeled as a system of ordinary differential equations derived from mass conservation laws on a directed acyclic graph with a single origin-destination pair and a constant total outflow at the origin. Routing policies regulate the way the total outflow at each nondestination node gets split among its outgoing links as a function of the current particle density, while the outflow of a link is modeled to depend on the current particle density on that link through a flow function. The dynamical network is called partially transferring if the total inflow at the destination node is asymptotically bounded away from zero, and its weak resilience is measured as the minimum sum of the link-wise magnitude of disturbances that make it not partially transferring. The weak resilience of a dynamical network with arbitrary routing policy is shown to be upper bounded by the network's min-cut capacity and, hence, is independent of the initial flow conditions. Moreover, a class of distributed routing policies that rely exclusively on local information on the particle densities, and are locally responsive to that, is shown to yield such maximal weak resilience. These results imply that locality constraints on the information available to the routing policies do not cause loss of weak resilience. Fundamental properties of dynamical networks driven by locally responsive distributed routing policies are analyzed in detail, including global convergence to a unique limit flow. The derivation of these properties exploits the cooperative nature of these dynamical systems, together with an additional stability property implied by the assumption of monotonicity of the flow as a function of the density on each link.
24 July 2012 in IEEE Transactions on Automatic Control
Strong resilience properties of dynamical networks are analyzed for distributed routing policies. The latter are characterized by the property that the way the outflow at a non-destination node gets split among its outgoing links is allowed to depend only on local information about the current particle densities on the outgoing links. The strong resilience of the network is defined as the infimum sum of link-wise flow capacity reductions making the asymptotic total inflow to the destination node strictly less than the total outflow at the origin. A class of distributed routing policies that are responsive to local information is shown to yield the maximum possible strong resilience under such local information constraints for an acyclic dynamical network with a single origin-destination pair. The maximal achievable strong resilience is shown to be equal to the minimum node residual capacity of the network. The latter depends on the limit flow of the unperturbed network and is defined as the minimum, among all the non-destination nodes, of the sum, over all the links outgoing from the node, of the differences between the maximum flow capacity and the limit flow of the unperturbed network. We propose a simple convex optimization problem to solve for equilibrium flows of the unperturbed network that minimize average delay subject to strong resilience guarantees, and discuss the use of tolls to induce such an equilibrium flow in traffic networks. Finally, we present illustrative simulations to discuss the connection between cascaded failures and the resilience properties of the network.
12 November 2014 in IEEE Transactions on Control of Network Systems
This paper investigates the throughput behavior of single-commodity dynamical flow networks governed by monotone distributed routing policies. The networks are modeled as systems of ordinary differential equations based on mass conversation laws on directed graphs with limited flow capacities on the links and constant external inflows at certain origin nodes. Under monotonicity assumptions on the routing policies, it is proven that, if the external inflow at the origin nodes does not violate any cut capacity constraints, then there exists a globally asymptotically stable equilibrium, and the network achieves maximal throughput. On the contrary, should such a constraint be violated, the network overload behavior is characterized. In particular, it is established that there exists a cut with respect to which the flow densities on every link grow linearly over time (respectively, reach their respective limits simultaneously) in the case where the buffer capacities are infinite (respectively, finite).
1 August 2011 in The Annals of Applied Probability
Scaling limits are analyzed for stochastic continuous opinion dynamics systems, also known as gossip models. In such models, agents update their vector-valued opinion to a convex combination (possibly agent- and opinion-dependent) of their current value and that of another observed agent. It is shown that, in the limit of large agent population size, the empirical opinion density concentrates, at an exponential probability rate, around the solution of a probability-measure-valued ordinary differential equation describing the system’s mean-field dynamics. Properties of the associated initial value problem are studied. The asymptotic behavior of the solution is analyzed for bounded-confidence opinion dynamics, and in the presence of an heterogeneous influential environment.
1 January 2013 in SIAM Journal on Control and Optimization
Stability of Wardrop equilibria is analyzed for dynamical transportation networks in which the drivers' route choices are influenced by information at multiple temporal and spatial scales. The considered model involves a continuum of nonatomic indistinguishable drivers commuting between a common origin-destination pair in an acyclic transportation network. The drivers' route choices are affected by their relatively infrequent perturbed best responses to global information about the current network congestion levels, as well as their instantaneous local observation of the immediate surroundings as they transit through the network. A novel model is proposed for driver route choice behavior, exhibiting local consistency with their preference toward globally less congested paths as well as myopic decisions in favor of locally less congested paths. The simultaneous evolution of the traffic congestion on the network and of the aggregate path preference is modeled by a system of coupled ordinary differential equations. The main result shows that if the frequency of updates of path preferences is sufficiently small as compared to the frequency of the traffic flow dynamics, then the state of the transportation network ultimately approaches a neighborhood of the Wardrop equilibrium. The presented results may be read as further evidence in support of Wardrop's postulate of equilibrium, showing robustness of it with respect to nonpersistent perturbations. The proposed analysis combines techniques from singular perturbation theory, evolutionary game theory, and cooperative dynamical systems.