hGMM: Capturing the Pulse of Multiagent Dynamics through History-Dependent Graphs

TL;DR

In dynamic multiagent systems, assuming agents act independently given history is often a fallacy of incomplete observation. This paper introduces History-Dependent Graphical Multiagent Models (hGMMs), which model the joint behavior of agents using local graphical structures. By conditioning on a truncated history, hGMMs capture the hidden correlations that individual models miss, outperforming standard baselines in predicting complex network consensus.

The "Independence" Fallacy in Multiagent Modeling

How do we predict what a group of agents will do next? Most researchers use Individual Behavior Multiagent Models (IBMMs). These assume that if we know the past (the history $H$), Agent A and Agent B make their next moves independently.

However, in the real world, we rarely have the full history. We use abstractions, truncated timelines, or local views. When the history is incomplete, the "independent" choices of agents suddenly appear highly correlated. hGMMs recognize this reality by modeling the joint probability $P(a^t|H^t)$ directly, rather than as a product of individual probabilities.

Methodology: Bridging Graphs and History

The core innovation lies in extending the static Graphical Multiagent Model into the temporal domain.

1. Neighborhood Potentials

The model defines a graph where edges represent local interactions. For each agent $i$, a potential function ${\pi }_i$ is computed based on its neighborhood $N_i$: ${\pi }_i(a_{N_i}^t|H^t)=\exp ({\beta }_i{r}_i(a_{N_i})f(a_{N_i},H)+{\alpha }_{i,a_i})$ This formula balances:

• $r_i$: The expected reward (preference).
• $f$: The historical frequency of specific joint configurations.
• $\alpha ,\beta$: Learned parameters that weight social influence versus individual preference.

2. Scalable Inference

By treating the system as a Markov Random Field, the joint distribution is factored. To stay computationally lean, the authors employ Belief Propagation to estimate the normalization factor $Z$, allowing the model to scale to larger networks where exact calculation would be impossible.

(The conceptual interaction graph used in the voting consensus experiments)

Experiments: Voting for a Winner

The authors tested hGMMs on a Voting Consensus Game. Agents on a network must agree on a vote (0 or 1) to get rewards, but they only see their neighbors' votes.

Key Findings:

• Short History Superiority: When the history horizon is short (e.g., $h=1$), hGMMs significantly outperform IBMMs (see Figure 2). This proves that the joint potential captures correlations that individual rules cannot see.
• Robust to Asynchrony: In the real world, agents don't move in lockstep. In asynchronous tests, hGMMs maintained a predictive edge, as they naturally account for the "cause-and-effect" ripples that get squashed during time discretization.
• The "Focus" of Approximation: Surprisingly, approximate inference (Belief Propagation) often yielded better predictions than exact inference, as it effectively penalized infrequent, "noisy" outcomes.

(Figure 2: Ratio of log-likelihoods showing hGMM's superior predictive power across different history lengths.)

Critical Insight: Why This Matters

The shift from "Individual + History" to "Joint + History" is a subtle but profound change in how we view Multi-Agent Systems (MAS). This paper demonstrates that locality is the key to complexity. By focusing on local cliques (neighborhoods), we can model global system shifts (like consensus) without needing a "god-view" of the entire system state.

Limitations & Future Work

• Structure Learning: Currently, the graph topology must be known. A future leap would be learning the interaction graph simultaneously with the behavior parameters.
• Backward Reasoning: The current hGMM is forward-looking. Extending this to "hidden state" reconstruction (backward inference) would make it a powerful tool for forensic MAS analysis.

Conclusion

hGMMs offer a mathematically rigorous yet computationally feasible way to predict how agents influence one another over time. For anyone building AI for markets, social networks, or distributed robotics, this work serves as a reminder: the group is often more than the sum of its independent parts.