On Some Fundamental Problems for Multi-Agent Systems Over Multilayer Networks
Daniel J. Rosenkrantz, Madhav V. Marathe, Zirou Qiu, S. S. Ravi, Richard E. Stearns · 2025
Read On Some Fundamental Problems for Multi-Agent Systems Over Multilayer Networks by Daniel J. Rosenkrantz, Madhav V. Marathe, Zirou Qiu, S. S. Ravi, Richard E. Stearns (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-12684.txt.
Introduction
Daniel Rosenkrantz, Madhav Marathe, Zirou Qiu, S. Ravi, and Richard Stearns studied the basic theory of agent systems spread over layered networks in a 2025 paper. Real connections between agents carry unlike meanings, family, friend, colleague, so multilayer networks model spread more honestly than single-layer ones. The authors analyze multilayer synchronous dynamical systems, where each agent updates by a local rule applied across layers. Chart the model's fundamental traits and phase spaces.
Sharp changes from the single-layer theory appear. Deciding whether two such systems are inequivalent is computationally hard in general, NP-complete even when the systems differ at one node in one layer. Restricted cases, bounded-threshold or even local rules, fixed layer counts, admit fast methods. Forecast problems for the model are also investigated. The results map where multilayer analysis stays tractable.
Catalog record
| CREATOR | Daniel J. Rosenkrantz, Madhav V. Marathe, Zirou Qiu, S. S. Ravi, Richard E. Stearns |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-12684
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Some Fundamental Problems for Multi-Agent Systems Over Multilayer Networks Daniel J. Rosenkrantz, Madhav V. Marathe, Zirou Qiu, S. S. Ravi, Richard E. Stearns Abstract . Many researchers have considered multi-agent systems over single-layer networks as models for studying diffusion phenomena. Since real-world networks involve connections between agents with different semantics (e.g., family member, friend, colleague), the study of multi-agent systems over multilayer networks has assumed importance. Our focus is on one class of multi-agent system models over multilayer networks, namely multilayer synchronous dynamical systems (MSyDSs). We study several fundamental problems for this model. We establish properties of the phase spaces of MSyDSs and bring out interesting differences between single-layer and multilayer dynamical systems. We show that, in general, the problem of determining whether two given MSyDSs are inequivalent is NP -complete. This hardness result holds even when the only difference between the two systems is the local function at just one node in one layer. We also present efficient algorithms for the equivalence problem for restricted versions of MSyDSs (e.g., systems where each local function is a bounded-threshold function, systems where the number of layers is fixed and each local function is symmetric). In addition, we investigate the expressive power of MSyDSs based on the number of layers. In particular, we examine conditions under which a system with k ≥ 2 k\geq 2 layers has an equivalent system with k − 1 k-1 or fewer layers. A. El Fallah Seghrouchni, Y. Vorobeychik, S. Das, A. Nowe (eds.) Conference: This is a complete version of the paper (with the same title) that will appear in Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025); May 19 – 23, 2025; Detroit, Michigan, USA 1153 1. Introduction 1.1. Background and Motivation Motivated by the spread of epidemics, information and social behavior in populations, the topic of contagion propagation over networks has been studied extensively in the literature (see e.g., ( Easley and Kleinberg, 2010 ; Granovetter, 1978 ; Watts, 2002 ; Wasserman et al., 1994 ; Newman, 2018 ) ). When the contagion represents information about a product produced by an organization, the propagation models enable the organization to develop strategies for maximizing the spread of the information (see e.g., ( Kempe et al., 2003 ) ). When the contagion is an epidemic, the propagation models enable public health officials to take appropriate actions to contain the spread of the epidemic (see e.g., ( Adiga et al., 2022 ; Lefévre et al., 2022 ) ). Such studies typically use networked dynamical systems models, where nodes represent individuals and edges represent relationships that enable a contagion to spread in the underlying network (see e.g., ( Adiga et al., 2019a ; Adiga et al., 2019b ; Barrett et al., 2011 ) ). Each node has an active or inactive state which indicates whether or not the node has acquired the contagion. The configuration of the system at any time is the vector of state values of nodes at that time. The interaction between a node and its neighbors is based on an appropriate local function, and this interaction may change the state of the node. Throughout this paper, we will assume that nodes compute and update their states synchronously . The time evolution of the system is represented by a sequence of successive configurations. The global behavior of a dynamical system is captured by its phase space , which is a directed graph in which each node is a configuration and each directed edge indicates a single step transition from one configuration to another. This work has generally assumed that the underlying network consists of a single layer; that is, there is only one type of relationship between entities for contagion propagation. A number of fundamental questions have been studied over the years for synchronous dynamical systems over single-layer networks. Following the literature (see e.g., ( Adiga et al., 2019a ) ), we refer to these single-layer systems as SyDSs. Papers on SyDSs have addressed questions concerning reachability of configurations (i.e., does a given SyDS starting from a configuration \mathcal{C} reach a configuration \mathcal{C}^{\prime} ?), equivalence (i.e., are two given SyDSs equivalent in terms of their phase space?), existence of fixed points (i.e., configurations in which none of the nodes changes its state), etc.; see e.g., ( Adiga et al., 2019b ; Ogihara and Uchizawa, 2017 ; Chistikov et al., 2020 ; Rosenkrantz et al., 2015 ; Rosenkrantz et al., 2018 ) and the references cited therein. A number of papers have pointed out that single-layer networks are inadequate to capture complex real-world contagion phenomena. The reason is that single-layer networks model just one type of relationship among individuals. Instead, one needs to consider multilayer 1 1 1 In much of the literature, the word “multilayer” is not hyphenated. We follow the same practice here. networks (also known as multiplex networks ( Zhang et al., 2016 ; Kivelä et al., 2014 ; Porter, 2018 ) ) that capture multi-relational structures (e.g., family member, friend, colleague, contact in a social network) among individuals to effectively model contagion propagation ( Kivelä et al., 2014 ; Hammoud and Kramer, 2020 ; Newman, 2018 ) . As a simple example, information that an individual obtains through a social network such as Facebook or Twitter may play a role in deciding whether the individual decides to wear a mask or get vaccinated. Thus, it is important to study dynamical systems where the underlying graph has multiple layers. In standard models of multilayer networks, there is just one set of nodes; each layer may have a different set of edges modeling different types of relationships (see, e.g., ( De Domenico et al., 2013 ; De Domenico et al., 2016 ; Porter, 2018 ; Del Vicario et al., 2016 ; Newman, 2018 ) ). The model for a dynamical system over a multilayer network is a simple extension of the corresponding model over a single-layer network. In such a system, each node has a single state value but a possibly different interaction function for each layer. At each time instant, after computing the value of the interaction function of the node in each layer, a master function uses these values to compute the next state of that node. As mentioned earlier, we focus on the synchronous update scheme where all the nodes compute their next states and update their states simultaneously. For consistency with previous work ( Qiu et al., 2024 ) , we refer to this model as a multilayer synchronous dynamical system (MSyDS). The notions of configuration and phase space for a MSyDS are the same as those for a dynamical system over a single-layer network. Algorithmic work on multilayer networks has centered around defining and computing appropriate centrality measures (see e.g., ( De Domenico et al., 2013 ; Porter, 2018 ; Newman, 2018 ) ). There has also been some work on estimating the sizes of cascades under certain contagion models (e.g., susceptible-infected-recovered or SIR model) through analysis and simulation in multilayer networks (see e.g., ( Del Vicario et al., 2016 ; Newman, 2018 ) and the references cited therein). Additional discussion regarding work on multilayer systems appears in Section 1.4 . For