Fabio Fagnani

Martina Vanelli, Laura Arditti, Giacomo Como et al.

We study binary-action pairwise-separable graphical games that encompass both coordination and anti-coordination network games. Our model is grounded in an underlying directed signed graph, where each link is associated with a signed weight that describes both nature and the strength of the strategic pairwise interaction. Specifically, positive link weight corresponds to a strategic complement type interaction, whereas negative link weight corresponds to strategic substitute type interaction. The utility for each player is then an aggregation of pairwise terms determined by the weights of the signed graph in addition to an individual bias term. We consider a scenario that assumes the presence of a prominent cohesive subset of players, who are either connected exclusively by positive weights, or form a structurally balanced subset that can be bipartitioned into two adversarial subcommunities with positive intra-community and negative inter-community edges. Under suitable properties of the game restricted to the remaining players, our results guarantee the existence of Nash equilibria characterized by either consensus or polarization within the first group, as well as their stability under best response transitions. Our results can be interpreted as robustness results, building on the super-modular properties of network coordination games and on a novel use of the concept of graph cohesiveness.

Daron Acemoglu, Giacomo Como, Fabio Fagnani et al.

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: regular agents, who update their beliefs according to information that they receive from their social neighbors; and stubborn agents, who never update their opinions. 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 non-degenerate random vector. The structure of the network and the location of the stubborn agents within it shape the opinion dynamics. The expected belief vector evolves according to an ordinary differential equation coinciding with the Kolmogorov backward equation of a continuous-time Markov chain with absorbing states corresponding to the stubborn agents and converges 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'. Expected cross-products of the agents' beliefs allow for a similar characterization in terms of coupled Markov chains on the 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 \emph{homogeneous influence} emerges, whereby the stationary beliefs' marginal distributions of most of the regular agents have approximately equal first and second moments.

Francesco Bullo, Fabio Fagnani, Barbara Franci

Recent contributions have studied how an influence system may affect the wisdom of crowd phenomenon. In the so-called naive learning setting, a crowd of individuals holds opinions that are statistically independent estimates of an unknown parameter; the crowd is wise when the average opinion converges to the true parameter in the limit of infinitely many individuals. Unfortunately, even starting from wise initial opinions, a crowd subject to certain influence systems may lose its wisdom. It is of great interest to characterize when an influence system preserves the crowd wisdom effect. In this paper we introduce and characterize numerous wisdom preservation properties of the basic French-DeGroot influence system model. Instead of requiring complete convergence to consensus as in the previous naive learning model by Golub and Jackson, we study finite-time executions of the French-DeGroot influence process and establish in this novel context the notion of prominent families (as a group of individuals with outsize influence). Surprisingly, finite-time wisdom preservation of the influence system is strictly distinct from its infinite-time version. We provide a comprehensive treatment of various finite-time wisdom preservation notions, counterexamples to meaningful conjectures, and a complete characterization of equal-neighbor influence systems.

Giacomo Como, Wilbert Samuel Rossi, Fabio Fagnani

The spread of new beliefs, behaviors, conventions, norms, and technologies in social and economic networks are often driven by cascading mechanisms, and so are contagion dynamics in financial networks. Global behaviors generally emerge from the interplay between the structure of the interconnection topology and the local agents' interactions. We focus on the Linear Threshold Model (LTM) of cascades first introduced by Granovetter (1978). This can be interpreted as the best response dynamics in a network game whereby agents choose strategically between two actions and their payoff is an increasing function of the number of their neighbors choosing the same action. Each agent is equipped with an individual threshold representing the number of her neighbors who must have adopted a certain action for that to become the agent's best response. We analyze the LTM dynamics on large-scale networks with heterogeneous agents. Through a local mean-field approach, we obtain a nonlinear, one-dimensional, recursive equation that approximates the evolution of the LTM dynamics on most of the networks of a given size and distribution of degrees and thresholds. Specifically, we prove that, on all but a fraction of networks with given degree and threshold statistics that is vanishing as the network size grows large, the actual fraction of adopters of a given action in the LTM dynamics is arbitrarily close to the output of the aforementioned recursion. We then analyze the dynamic behavior of this recursion and its bifurcations from a dynamical systems viewpoint. Applications of our findings to some real network testbeds show good adherence of the theoretical predictions to numerical simulations.

Giacomo Como, Fabio Fagnani

Distributed averaging is one of the simplest and most studied network dynamics. Its applications range from cooperative inference in sensor networks, to robot formation, to opinion dynamics. A number of fundamental results and examples scattered through the literature are gathered here and originally presented, emphasizing the deep interplay between the network interconnection structure and the emergent global behavior.

Fabio Fagnani, Sophie M. Fosson, Chiara Ravazzi

In this paper, we address the problem of simultaneous classification and estimation of hidden parameters in a sensor network with communications constraints. In particular, we consider a network of noisy sensors which measure a common scalar unknown parameter. We assume that a fraction of the nodes represent faulty sensors, whose measurements are poorly reliable. The goal for each node is to simultaneously identify its class (faulty or non-faulty) and estimate the common parameter. We propose a novel cooperative iterative algorithm which copes with the communication constraints imposed by the network and shows remarkable performance. Our main result is a rigorous proof of the convergence of the algorithm and a characterization of the limit behavior. We also show that, in the limit when the number of sensors goes to infinity, the common unknown parameter is estimated with arbitrary small error, while the classification error converges to that of the optimal centralized maximum likelihood estimator. We also show numerical results that validate the theoretical analysis and support their possible generalization. We compare our strategy with the Expectation-Maximization algorithm and we discuss trade-offs in terms of robustness, speed of convergence and implementation simplicity.

Wilbert Samuel Rossi, Paolo Frasca, Fabio Fagnani

Important applications in robotic and sensor networks require distributed algorithms to solve the so-called relative localization problem: a node-indexed vector has to be reconstructed from measurements of differences between neighbor nodes. In a recent note, we have studied the estimation error of a popular gradient descent algorithm showing that the mean square error has a minimum at a finite time, after which the performance worsens. This paper proposes a suitable modification of this algorithm incorporating more realistic "a priori" information on the position. The new algorithm presents a performance monotonically decreasing to the optimal one. Furthermore, we show that the optimal performance is approximated, up to a 1 + \eps factor, within a time which is independent of the graph and of the number of nodes. This convergence time is very much related to the minimum exhibited by the previous algorithm and both lead to the following conclusion: in the presence of noisy data, cooperation is only useful till a certain limit.

Paolo Frasca, Fabio Fagnani

In this paper we study two related iterative randomized algorithms for distributed computation of averages. The first one is the recently proposed Broadcast Gossip Algorithm, in which at each iteration one randomly selected node broadcasts its own state to its neighbors. The second algorithm is a novel de-synchronized version of the previous one, in which at each iteration every node is allowed to broadcast, with a given probability: hence this algorithm is affected by interference among messages. Both algorithms are proved to converge, and their performance is evaluated in terms of rate of convergence and asymptotical error: focusing on the behavior for large networks, we highlight the role of topology and design parameters on the performance. Namely, we show that on fully-connected graphs the rate is bounded away from one, whereas the asymptotical error is bounded away from zero. On the contrary, on a wide class of locally-connected graphs, the rate goes to one and the asymptotical error goes to zero, as the size of the network grows larger.

Fabio Fagnani, Jean-Charles Delvenne

In linear models of consensus dynamics, the state of the various agents converges to a value which is a convex combination of the agents' initial states. We call it democratic if in the large scale limit (number of agents going to infinity) the vector of convex weights converges to 0 uniformly. Democracy is a relevant property which naturally shows up when we deal with opinion dynamic models and cooperative algorithms such as consensus over a network: it says that each agent's measure/opinion is going to play a negligeable role in the asymptotic behavior of the global system. It can be seen as a relaxation of average consensus, where all agents have exactly the same weight in the final value, which becomes negligible for a large number of agents.

Lorenzo Zino, Giacomo Como, Fabio Fagnani

We consider a broad class of stochastic imitation dynamics over networks, encompassing several well known learning models such as the replicator dynamics. In the considered models, players have no global information about the game structure: they only know their own current utility and the one of neighbor players contacted through pairwise interactions in a network. In response to this information, players update their state according to some stochastic rules. For potential population games and complete interaction networks, we prove convergence and long-lasting permanence close to the evolutionary stable strategies of the game. These results refine and extend the ones known for deterministic imitation dynamics as they account for new emerging behaviors including meta-stability of the equilibria. Finally, we discuss extensions of our results beyond the fully mixed case, studying imitation dynamics where agents interact on complex communication networks.

Giacomo Como, Fabio Fagnani, Leonardo Massai et al.

We study a networked economic system composed of $n$ producers supplying a single homogeneous good to a number of geographically separated markets and of a centralized authority, called the market maker. Producers compete à la Cournot, by choosing the quantities of good to supply to each market they have access to in order to maximize their profit. Every market is characterized by its inverse demand functions returning the unit price of the considered good as a function of the total available quantity. Markets are interconnected by a dispatch network through which quantities of the considered good can flow within finite capacity constraints and possibly satisfying additional linear physical constraints. Such flows are determined by the action of a system operator, who aims at maximizing a designated welfare function. We model such competition as a strategic game with $n+1$ players: the producers and the system operator. For this game, we first establish the existence of pure-strategy Nash equilibria under standard concavity assumptions. We then identify sufficient conditions for the game to be exact potential with an essentially unique Nash equilibrium. Next, we present a general result that connects the optimal action of the system operator with the capacity constraints imposed on the network. For the commonly used Walrasian welfare, our finding proves a connection between capacity bottlenecks in the market network and the emergence of price differences between markets separated by saturated lines. This phenomenon is frequently observed in real-world scenarios, for instance in power networks. Finally, we validate the model with data from the Italian day-ahead electricity market.

Paolo Frasca, Fabio Fagnani

In problems of estimation and control which involve a network, efficient distributed computation of averages is a key issue. This paper presents theoretical and simulation results about the accumulation of errors during the computation of averages by means of iterative "broadcast gossip" algorithms. Using martingale theory, we prove that the expectation of the accumulated error can be bounded from above by a quantity which only depends on the mixing parameter of the algorithm and on few properties of the network: its size, its maximum degree and its spectral gap. Both analytical results and computer simulations show that in several network topologies of applicative interest the accumulated error goes to zero as the size of the network grows large.

Wilbert Samuel Rossi, Paolo Frasca, Fabio Fagnani

In our recent paper W.S. Rossi, P. Frasca and F. Fagnani, "Average resistance of toroidal graphs", SIAM Journal on Control and Optimization, 53(4):2541--2557, 2015, we studied how the average resistances of $d$-dimensional toroidal grids depend on the graph topology and on the dimension of the graph. Our results were based on the connection between resistance and Laplacian eigenvalues. In this note, we contextualize our work in the body of literature about random walks on graphs. Indeed, the average effective resistance of the $d$-dimensional toroidal grid is proportional to the mean hitting time of the simple random walk on that grid. If $d\geq3 $, then the average resistance can be bounded uniformly in the number of nodes and its value is of order $1/d$ for large $d$.

Leonardo Cianfanelli, Sebastiano Messina, Giacomo Como et al.

We study an optimal intervention problem on the linear threshold model (LTM) in which a social planner aims to design minimal-cost interventions that modify the agents' thresholds, under the constraint that at least a predefined fraction of agents reaches a given state after a finite number of iterations. While this problem is known to be NP-hard and its exact solution requires full knowledge of the network structure, we focus on approximate solutions for large-scale networks and assume that the planner has only statistical knowledge of the network. In particular, we build on a local mean-field approximation of the LTM that is known to hold true on large-scale random networks, and reformulate the optimal intervention problem as a linear program with an infinite set of constraints. We then show how to approximate the solutions of the latter problem by standard linear programs with finitely many constraints. Finally, our approach is validated through numerical experiments on real-world networks and compared both with optimal seeding and state-of-the-art algorithms for the least-cost influence.

Giacomo Como, Fabio Fagnani, Anton Proskurnikov

The wisdom of crowds is an umbrella term for phenomena suggesting that the collective judgment or decision of a large group can be more accurate than the individual judgments or decisions of the group members. A well-known example illustrating this concept is the competition at a country fair described by Galton, where the median value of the individual guesses about the weight of an ox resulted in an astonishingly accurate estimate of the actual weight. This phenomenon resembles classical results in probability theory and relies on independent decision-making. The accuracy of the group's final decision can be significantly reduced if the final agents' opinions are driven by a few influential agents. In this paper, we consider a group of agents who initially possess uncorrelated and unbiased noisy measurements of a common state of the world. Assume these agents iteratively update their estimates according to a simple non-Bayesian learning rule, commonly known in mathematical sociology as the French-DeGroot dynamics or iterative opinion pooling. As a result of this iterative distributed averaging process, each agent arrives at an asymptotic estimate of the state of the world, with the variance of this estimate determined by the matrix of weights the agents assign to each other. Every agent aims at minimizing the variance of her asymptotic estimate of the state of the world; however, such variance is also influenced by the weights allocated by other agents. To achieve the best possible estimate, the agents must then solve a game-theoretic, multi-objective optimization problem defined by the available sets of influence weights. We characterize both the Pareto frontier and the set of Nash equilibria in the resulting game. Additionally, we examine asynchronous best-response dynamics for the group of agents and prove their convergence to the set of strict Nash equilibria.

Lorenzo Zino, Giacomo Como, Fabio Fagnani

Imitation dynamics for population games are studied and their asymptotic properties analyzed. In the considered class of imitation dynamics - that encompass the replicator equation as well as other models previously considered in evolutionary biology - players have no global information about the game structure, and all they know is their own current utility and the one of fellow players contacted through pairwise interactions. For potential population games, global asymptotic stability of the set of Nash equilibria of the sub-game restricted to the support of the initial population configuration is proved. These results strengthen (from local to global asymptotic stability) existing ones and generalize them to a broader class of dynamics. The developed techniques highlight a certain structure of the problem and suggest possible generalizations from the fully mixed population case to imitation dynamics whereby agents interact on complex communication networks.

Sara Bernardini, Fabio Fagnani, David E. Smith

We present a technique for automatically extracting mutual exclusion invariants from temporal planning instances. It first identifies a set of invariant templates by inspecting the lifted representation of the domain and then checks these templates against properties that assure invariance. Our technique builds on other approaches to invariant synthesis presented in the literature, but departs from their limited focus on instantaneous actions by addressing temporal domains. To deal with time, we formulate invariance conditions that account for the entire structure of the actions and the possible concurrent interactions between them. As a result, we construct a significantly more comprehensive technique than previous methods, which is able to find not only invariants for temporal domains, but also a broader set of invariants for non-temporal domains. The experimental results reported in this paper provide evidence that identifying a broader set of invariants results in the generation of fewer multi-valued state variables with larger domains. We show that, in turn, this reduction in the number of variables reflects positively on the performance of a number of temporal planners that use a variable/value representation by significantly reducing their running time.

Wilbert Samuel Rossi, Paolo Frasca, Fabio Fagnani

The average effective resistance of a graph is a relevant performance index in many applications, including distributed estimation and control of network systems. In this paper, we study how the average resistance depends on the graph topology and specifically on the dimension of the graph. We concentrate on $d$-dimensional toroidal grids and we exploit the connection between resistance and Laplacian eigenvalues. Our analysis provides tight estimates of the average resistance, which are key to study its asymptotic behavior when the number of nodes grows to infinity. In dimension two, the average resistance diverges: in this case, we are able to capture its rate of growth when the sides of the grid grow at different rates. In higher dimensions, the average resistance is bounded uniformly in the number of nodes: in this case, we conjecture that its value is of order $1/d$ for large $d$. We prove this fact for hypercubes and when the side lengths go to infinity.

Giacomo Como, Fabio Fagnani

Upper bounds are derived on the total variation distance between the invariant distributions of two stochastic matrices differing on a subset W of rows. Such bounds depend on three parameters: the mixing time and the minimal expected hitting time on W for the Markov chain associated to one of the matrices; and the escape time from W for the Markov chain associated to the other matrix. These results, obtained through coupling techniques, prove particularly useful in scenarios where W is a small subset of the state space, even if the difference between the two matrices is not small in any norm. Several applications to large-scale network problems are discussed, including robustness of Google's PageRank algorithm, distributed averaging and consensus algorithms, and interacting particle systems.

Ruggero Carli, Fabio Fagnani, Paolo Frasca et al.

This paper considers the average consensus problem on a network of digital links, and proposes a set of algorithms based on pairwise ''gossip'' communications and updates. We study the convergence properties of such algorithms with the goal of answering two design questions, arising from the literature: whether the agents should encode their communication by a deterministic or a randomized quantizer, and whether they should use, and how, exact information regarding their own states in the update.

Ruggero Carli, Fabio Fagnani, Paolo Frasca et al.

This paper presents an algorithm which solves exponentially fast the average consensus problem on strongly connected network of digital links. The algorithm is based on an efficient zooming-in/zooming-out quantization scheme.