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.
This paper develops a general framework for analyzing multi-agent systems with feedback loops between agents actions and collective observations. The framework is built on two fundamental agent-level variables: power, which measures agent influence on collective outcomes, and response functions, which determine how agents react to observations. We derive how macroscopic properties, including total power, useful power, entropy, order, fragility, and mobility, emerge from these two variables of heterogeneous agents. To study the trade off between growth and resilience, we introduce a system-level utility function parameterized by a risk-appetite coefficient and derive an optimal degree of order that balances productivity, stability, and adaptability. The analysis suggests that stronger synchronization can increase collective output but may also increase systemic fragility and reduce mobility. We further argue that order, entropy, information, and useful energy are task-dependent and system-relative concepts whose meanings depend on the objectives of the system. By measuring and designing agent power distributions and response functions, it may be possible to better understand, predict, and optimize collective behavior and identify the conditions under which collective intelligence and optimal order emerge.
Jake J. Xia
Harvard Management Company · Research Affiliate at Massachusetts Institute of Technology
Large language model (LLM)-based multi-agent systems are increasingly applied across diverse domains, yet different applications require different forms of agent organization. Existing studies typically adopt predefined organizations, such as Star, Chain, and Tree, or learn communication graphs to improve performance on specific tasks. However, these methods are largely designed and evaluated within a limited set of application domains, providing little understanding of whether an organization effective in one domain remains suitable for others with different collaboration requirements. We present OpenDGO, a controlled benchmark and analysis framework covering six real-world domains and three collaboration settings: Sequential Dependency, Parallel Decomposition, and Information Integration. Under matched tasks, agents, tools, and resource limits, OpenDGO compares fixed and learned organizations while separately examining communication graphs, role assignments, input assignments, resource budgets, and component failures. Our results show that there is no ``one-organization-for-all'' solution: preferred organizations vary across applications, and even the same communication graph can yield different outcomes under different role and input assignments. These findings highlight the need for application-dependent organization design, aiming to understand which organization is suitable for a given application, under what conditions, and why.
Open systems, where agents arrive and depart over time, are growing in digital platforms. Existing work on online learning in such systems, however, often relies on structural assumptions that may be restrictive in practice. In particular, heterogeneous rewards and general agent patterns create three new challenges: arrivals induce endogenous non-stationarity, agent patterns govern the rate of information accumulation, and uncertainty brought by new agents accumulates over time and scales regret. To this end, we formulate a learning problem for open systems that accommodates both forms of generality. We introduce new concepts to capture the inherent complexities: the pre-training degree of new agents quantifies how much information an agent carries upon entry, stability measures the impact of population changes on the global optimum, and global dynamic regret compares the cumulative expected reward with that of the varying optimal arms. We also study a manifold representation of agents and introduce a dynamic population embedding that directly encodes the population functional for each arm. We develop two UCB-based methods. The first combines entry information with online observations through agent-wise confidence bounds and aggregates the estimates and uncertainties for arm selection. The second pools agent-level observations through kernel regression on the manifold and constructs UCBs by projecting the confidence sets onto the current population embedding. Entry uncertainty enters the regret linearly through the pre-training error, while in stable regimes, regret is governed by the time needed to identify the stable optimal arm. With the manifold as a handle, regret is governed by the information gained from agent representations. These bounds all depend on population dynamics, but in different ways.
Mengfan Xu
Mechanical and Industrial Engineering, University of Massachusetts Amherst