Scaling Multi-Agent Systems via Aggregate Count Representations

This direction is split into other directions: agent anonymity. Its last version stays readable and citable here.

Version 1 of 174 papers119 conceptsfrozen 2026-10-04

In traditional multi-agent systems, the complexity of decision-making grows exponentially with the number of participants. If you have $N$ agents, each with $S$ possible states, the global state space is $S^N$. This "curse of dimensionality" makes it computationally impossible to coordinate thousands of entities—like a city’s taxi fleet or a swarm of drones—using standard reinforcement learning or planning algorithms.

However, a growing body of research suggests that for large populations, tracking individual identities is often unnecessary. By exploiting agent anonymity and exchangeability, researchers have shown that we can represent the global state as a distribution of counts rather than a list of unique trajectories. This shift collapses the state space from exponential to polynomial, enabling coordination at scales previously thought unreachable.

The Intuition of Anonymity

The core insight, as explored by Philipp Robbel, Frans A. Oliehoek, and Mykel J. Kochenderfer in Exploiting Anonymity in Approximate Linear Programming: Scaling to Large Multiagent MDPs, is that in many systems, an agent’s utility or transition probability depends on how many neighbors are in a certain state, not which specific neighbors they are.

Imagine a ride-hailing driver in a congested city. To decide where to move next, the driver doesn't need to know the license plate numbers of the 500 other taxis nearby. They only need to know the density of taxis in the surrounding zones. When agents are functionally identical, their identities are redundant. By treating agents as "interchangeable tokens" in a shared state space—a concept also utilized in multi-robot Petri Nets by Bruno Lacerda and Federico Pecora in Multi-Robot Planning Under Uncertain Travel Times and Safety Constraints—the system can reason about the collective "mass" of the population.

From Exponential to Polynomial Complexity

The mathematical mechanism for this scaling is the transformation of the state representation into a histogram of counts.

  1. Individual Representation: A state is a vector $(s_1, s_2, ..., s_N)$, where $s_i$ is the state of agent $i$.
  2. Count-Based Representation: A state is a vector $(n_1, n_2, ..., n_S)$, where $n_j$ is the number of agents currently in state $j$.

As Akshat Kumar, Duc Thien Nguyen, and Hoong Chuin Lau demonstrate in Collective Multiagent Sequential Decision Making Under Uncertainty, this "Collective Decentralized MDP" (CDec-MDP) framework allows for the coordination of thousands of agents because the complexity now scales with the number of states rather than the number of agents.

This approach is further formalized through lifting. Tanya Braun and Marcel Gehrke in Lifting in multi-agent systems under uncertainty prove that if agents are indistinguishable, probabilistic inference can be performed in time polynomial to the swarm size. By "lifting" the problem, we solve for a representative agent and generalize the solution to the entire group.

Action Anonymity and Joint Decision Making

The same logic applies to actions. In Many Agent Reinforcement Learning Under Partial Observability, Prashant Doshi and Bikramjit Banerjee introduce action anonymity. Instead of a joint action space where every agent's specific choice is tracked, the system tracks "configurations"—the count of agents performing each possible action. This collapses the joint action space, which is typically the most significant bottleneck in multi-agent reinforcement learning (MARL).

This is particularly effective in "open" systems where agents may join or leave dynamically. Adam Eck and Maulik Shah show in Scalable Decision-Theoretic Planning in Open and Typed Multiagent Systems that by focusing on "frame-action anonymity," an agent can plan effectively by modeling the distribution of behaviors in the population rather than trying to predict the specific moves of every individual peer.

Applications in High-Density Environments

This research direction has moved from theoretical proofs to practical applications in complex, high-density domains:

Why It Works: The Power of Sufficient Statistics

The reason aggregate counts work so well is that they often serve as a sufficient statistic for the global state. In a system of identical agents, the exact permutation of who is where doesn't change the transition probabilities or the rewards. By discarding the "who" and keeping only the "how many," we remove massive amounts of redundant information without losing the data necessary for optimal control. This allows researchers to bridge the gap between small-scale laboratory multi-agent experiments and the massive, anonymous swarms found in the real world.

Papers in this version

Showing 60 of 74 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scaling_multi_agent_systems_via_aggregat_4f15b7d9,
  title = {Scaling Multi-Agent Systems via Aggregate Count Representations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-multi-agent-systems-via-aggregate-count-representations/rdr_4f15b7d91cda42f2ad13abf18e4ffcf7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_scaling_multi_agent_systems_via_aggregat_4f15b7d9_v1,
  title = {Scaling Multi-Agent Systems via Aggregate Count Representations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-multi-agent-systems-via-aggregate-count-representations/rdr_4f15b7d91cda42f2ad13abf18e4ffcf7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}