Arrow Research search

Author name cluster

Richard E. Stearns

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers
1 author row

Possible papers

13

AAMAS Conference 2025 Conference Paper

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

Many researchers have considered multi-agent systems over singlelayer 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 increased 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, and 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 π‘˜ β‰₯ 2 layers has an equivalent system with π‘˜ βˆ’ 1 or fewer layers.

PDF

AAAI Conference 2024 Conference Paper

Learning the Topology and Behavior of Discrete Dynamical Systems

  • Zirou Qiu
  • Abhijin Adiga
  • Madhav V. Marathe
  • S. S. Ravi
  • Daniel J. Rosenkrantz
  • Richard E. Stearns
  • Anil Vullikanti

Discrete dynamical systems are commonly used to model the spread of contagions on real-world networks. Under the PAC framework, existing research has studied the problem of learning the behavior of a system, assuming that the underlying network is known. In this work, we focus on a more challenging setting: to learn both the behavior and the underlying topology of a black-box system. We show that, in general, this learning problem is computationally intractable. On the positive side, we present efficient learning methods under the PAC model when the underlying graph of the dynamical system belongs to certain classes. Further, we examine a relaxed setting where the topology of an unknown system is partially observed. For this case, we develop an efficient PAC learner to infer the system and establish the sample complexity. Lastly, we present a formal analysis of the expressive power of the hypothesis class of dynamical systems where both the topology and behavior are unknown, using the well-known Natarajan dimension formalism. Our results provide a theoretical foundation for learning both the topology and behavior of discrete dynamical systems.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Assigning Agents to Increase Network-Based Neighborhood Diversity

  • Zirou Qiu
  • Andrew Yuan
  • Chen Chen
  • Madhav V. Marathe
  • S. S. Ravi
  • Daniel J. Rosenkrantz
  • Richard E. Stearns
  • Anil Vullikanti

Motivated by real-world applications such as the allocation of public housing, we examine the problem of assigning a group of agents to vertices (e. g. , spatial locations) of a network so that the diversity level is maximized. Specifically, agents are of two types (characterized by features), and we measure diversity by the number of agents who have at least one neighbor of a different type. This problem is known to be NP-hard, and we focus on developing approximation algorithms with provable performance guarantees. We first present a local-improvement algorithm for general graphs that provides an approximation factor of 1⇑2. For the special case where the sizes of agent subgroups are similar, we present a randomized approach based on semidefinite programming that yields an approximation factor better than 1⇑2. Further, we show that the problem can be solved efficiently when the underlying graph is treewidth-bounded and obtain a polynomial time approximation scheme (PTAS) for the problem on planar graphs. Lastly, we conduct experiments to evaluate the performance of the proposed algorithms on synthetic and real-world networks.

PDF

AAAI Conference 2023 Conference Paper

Networked Anti-coordination Games Meet Graphical Dynamical Systems: Equilibria and Convergence

  • Zirou Qiu
  • Chen Chen
  • Madhav V. Marathe
  • S. S. Ravi
  • Daniel J. Rosenkrantz
  • Richard E. Stearns
  • Anil Vullikanti

Evolutionary anti-coordination games on networks capture real-world strategic situations such as traffic routing and market competition. Two key problems concerning evolutionary games are the existence of a pure Nash equilibrium (NE) and the convergence time. In this work, we study these two problems for anti-coordination games under sequential and synchronous update schemes. For each update scheme, we examine two decision modes based on whether an agent considers its own previous action (self essential) or not (self non-essential) in choosing its next action. Using a relationship between games and dynamical systems, we show that for both update schemes, finding an NE can be done efficiently under the self non-essential mode but is computationally intractable under the self essential mode. We then identify special cases for which an NE can be obtained efficiently. For convergence time, we show that the dynamics converges in a polynomial number of steps under the synchronous scheme; for the sequential scheme, the convergence time is polynomial only under the self non-essential mode. Through experiments, we empirically examine the convergence time and the equilibria for both synthetic and real-world networks.

PDF Details DOI

JMLR Journal 2022 Journal Article

Using Active Queries to Infer Symmetric Node Functions of Graph Dynamical Systems

  • Abhijin Adiga
  • Chris J. Kuhlman
  • Madhav V. Marathe
  • S. S. Ravi
  • Daniel J. Rosenkrantz
  • Richard E. Stearns

Developing techniques to infer the behavior of networked social systems has attracted a lot of attention in the literature. Using a discrete dynamical system to model a networked social system, the problem of inferring the behavior of the system can be formulated as the problem of learning the local functions of the dynamical system. We investigate the problem assuming an active form of interaction with the system through queries. We consider two classes of local functions (namely, symmetric and threshold functions) and two interaction modes, namely batch (where all the queries must be submitted together) and adaptive (where the set of queries submitted at a stage may rely on the answers to previous queries). We establish bounds on the number of queries under both batch and adaptive query modes using vertex coloring and probabilistic methods. Our results show that a small number of appropriately chosen queries are provably sufficient to correctly learn all the local functions. We develop complexity results which suggest that, in general, the problem of generating query sets of minimum size is computationally intractable. We present efficient heuristics that produce query sets under both batch and adaptive query modes. Also, we present a query compaction algorithm that identifies and removes redundant queries from a given query set. Our algorithms were evaluated through experiments on over 20 well-known networks. [abs] [ pdf ][ bib ] &copy JMLR 2022. ( edit, beta )

PDF Details

AAAI Conference 2021 Conference Paper

Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms

  • Daniel J. Rosenkrantz
  • Madhav Marathe
  • S. S. Ravi
  • Richard E. Stearns

Discrete dynamical systems serve as useful formal models to study diffusion phenomena in social networks. Motivated by applications in systems biology, several recent papers have studied algorithmic and complexity aspects of diffusion problems for dynamical systems whose underlying graphs are directed, and may contain directed cycles. Such problems can be regarded as reachability problems in the phase space of the corresponding dynamical system. We show that computational intractability results for reachability problems hold even for dynamical systems on directed acyclic graphs (dags). We also show that for dynamical systems on dags where each local function is monotone, the reachability problem can be solved efficiently.

PDF Details

AAMAS Conference 2018 Conference Paper

Testing Phase Space Properties of Synchronous Dynamical Systems with Nested Canalyzing Local Functions

  • Daniel J. Rosenkrantz
  • Madhav V. Marathe
  • S. S. Ravi
  • Richard E. Stearns

Discrete graphical dynamical systems serve as effective formal models for simulations of agent-based models, propagation of contagions in social networks and study of biological phenomena. A class of Boolean functions, called nested canalyzing functions (NCFs), has been used as a good model of certain biological phenomena. Motivated by these biological applications, we study a variety of analysis problems for synchronous graphical dynamical systems (SyDSs) over the Boolean domain, where each local function is an NCF. We present intractability results for some properties as well as efficient algorithms for others. In several cases, our results clearly delineate intractable and efficiently solvable versions of problems.

PDF