Evolution of Descriptors in Open Multi-Agent Systems for Gossip Interactions and Beyond
Authors: Charles Monnoyer de Galland, Samuel Martin, Balázs Gerencsér, Julien M. Hendrickx
Organizations: ICTEAM institute, UCLouvain, Louvain-la-Neuve, Belgium · Université de Lorraine and CNRS, CRAN, UMR 7039, 2 Avenue de la Forêt et de Haye, 54518 Vandoeuvre-lès-Nancy, France
We consider open multi-agent systems, which are systems subject to frequent arrivals and departures of agents while the studied process takes place. We study the behavior of all-to-all pairwise gossip interactions in such open systems. Arrivals and departures of agents imply that the composition and size of the system evolve with time, and in particular prevent convergence. We describe the expected behavior of the system by showing that the evolution of scale-independent quantities can be characterized exactly by fixed-size linear dynamical systems that correspond to Markov processes with states of potentially unbounded dimension. For this purpose we develop a general methodology that could be applicable to larger classes of models. We apply this approach to characterize the evolution of the two first moments (and thus also of a variance-like measure of disagreement) for open systems of fixed and variable size.
Figures & tables
Figure 1: Example of dynamics of an open multi-agent system of 4 agents subject to random pairwise average gossips [ 4 ] and agent replacements, the latter happening once every nine gossip steps on average (see Section 4.1 for a precise description of the system). Each line corresponds to the value held by an agent, and each red circle highlights a replacement. The repeated replacements prevent convergence to consensus.
Figure 2: Behavior of an open system of 50 agents subject to random replacements and gossips with rates λr=1 and λg=19 , so that λr+λg=20 . (a) depicts the evolution of one realization of the system, where each line is the estimate of an agent. (b), (c) and (d) respectively depict the evolution of the expected mean of squares x2 , squared mean xˉ2 and disagreement Δ(x) simulated over 10000 realizations in plain blue line. Those are compared with the theoretical results as obtained in Theorem 2 in dashed red line (the disagreement is deduced from Δ(x)=x2−xˉ2 ). The expected fixed points from equations ( 13 ) and ( 14 ) are also depicted in yellow dotted line.
Figure 3: Continuous-time Markov Chain representing the evolution of the system size as a birth-death process where the birth and death rates are respectively given by λa and jλd when the system size is n(t)=j .
Figure 4: Evolution with γ=λg/λd . of the expected asymptotic disagreement in the setting of Section 4.2 , for λd=1 and λa=20 and thus a characteristic number of 20 agents. Each point for the simulation (in blue) corresponds to the average over 1000 trials, with the situation at t=50 being taken as “asymptotic value". It is compared with the theoretical result ( 16 ) from Corollary 2 , and a similar function that appears numerically more accurate.