Decomposing Complex Interactions into Pairwise Components

26 concepts17 papers1 proposal

When modeling systems with multiple interacting parts—whether they are reinforcement learning agents coordinating a strategy, items on a menu influencing a consumer's choice, or players cooperating on a sports team—we invariably run into the curse of dimensionality.

If a system contains $N$ components that each have $A$ possible states or actions, the space of joint configurations scales exponentially as $A^N$. Attempting to learn, optimize, or evaluate functions over this complete joint space quickly becomes computationally impossible. Historically, researchers faced an unappealing choice: treat every component as completely independent (ignoring coordination entirely) or model the full joint space (limiting scalability to just a few components).

Pairwise interaction modeling provides a elegant middle ground. The core insight is that the vast majority of complex, high-dimensional group dynamics can be accurately reconstructed by summing up individual contributions and pairwise (second-order) relationships. By ignoring third-order and higher interactions, we can compress an exponential problem space into a manageable quadratic ($O(N^2)$) one without sacrificing the fidelity needed for complex coordination.


The Power of Second-Order Approximations

Why is a second-order approximation so effective? In most real-world systems, higher-order interactions exhibit rapidly diminishing returns. The synergy of a whole group is rarely a completely unique, irreducible phenomenon; instead, it is built out of localized, dual-agent dependencies.

Mathematically, we can approximate a global joint function $F(x_1, \dots, x_N)$ by decomposing it into unary (individual) and binary (pairwise) terms:

$$F(x_1, \dots, x_N) \approx \sum_{i=1}^N f_i(x_i) + \sum_{i < j} f_{ij}(x_i, x_j)$$

Christian Kroer et al. demonstrated this principle in Evaluating and Rewarding Teamwork Using Cooperative Game Abstractions. By using cooperative game abstractions that limit interactions to pairwise synergies, the authors showed they could predict team performance and compute fair individual rewards (Shapley values) in linear time rather than exponential time, noting that higher-order interactions added negligible predictive value.

This structural simplification applies far beyond game theory:


Pairwise Factorization in Multi-Agent Reinforcement Learning

In cooperative Multi-Agent Reinforcement Learning (MARL), the challenge is to learn a joint action-value function $Q(s, \mathbf{a})$ that dictates how a team should act. Pairwise value decomposition breaks this global function down into localized coordination graphs.

[Agent 1] <---> [Agent 2]
   ^               ^
   |               |
   v               v
[Agent 4] <---> [Agent 3]

Instead of a single black-box network computing values for all actions simultaneously, the network is structured as a graph where nodes represent individual agent utilities and edges represent pairwise payoff matrices.

Ming Zhou et al. leveraged this in Factorized Q-learning for large-scale multi-agent systems, combining pairwise relationships with Factorization Machines to scale coordination to hundreds of agents. To understand why this works so well, Jacopo Castellini et al. systematically investigated The Representational Capacity of Action-Value Networks for Multi-Agent Reinforcement Learning. The authors proved that complete pairwise factorization can accurately reconstruct complex coordination patterns even in tasks that are not naturally decomposable, easily outperforming independent learners.

This graph-based factorization makes optimization tractable because agents only need to maximize actions relative to their immediate neighbors. For instance, Filippos Christianos et al. used this decomposition in Pareto Actor-Critic for Equilibrium Selection in Multi-Agent Reinforcement Learning to help agents escape coordination traps and safely select optimal joint strategies. Even in environments requiring strict temporal synchronization, such as those studied by Rolando Fernandez et al. in Multi-Agent Synchronization Tasks, decomposing global rewards into pairwise components provides the structural guidance necessary for agents to align their behaviors.


Compressing Interaction Matrices via Low-Rank Approximations

While reducing an exponential space to a quadratic one ($O(N^2)$) is a massive improvement, a fully dense pairwise interaction matrix can still become a bottleneck if the individual action spaces are large. To solve this, researchers exploit another key insight: interaction structures are often low-rank.

If two agents influence each other, they rarely do so across every single dimension of their action spaces. Their mutual dependencies can typically be compressed into a few critical interaction axes.

Dense Payoff Matrix (A x A)          Low-Rank Decomposition
     [ . . . . ]                         [ . ]
     [ . . . . ]             ======>     [ . ]  x  [ . . . . ]
     [ . . . . ]                         [ . ]
     [ . . . . ]                         [ . ]

Marek Petrik et al. formalized this approach in Anytime Coordination Using Separable Bilinear Programs and A Successive Approximation Algorithm for Coordination Problems. By applying Singular Value Decomposition (SVD) or eigen-decomposition to the agent interaction matrix, the authors isolated and retained only the most significant dimensions of interaction. Discarding dimensions with negligible eigenvalues allowed them to solve large-scale coordination problems with strict mathematical bounds on the resulting loss in accuracy.

Further work by Martin Allen et al. in Interaction Structure and Dimensionality Reduction in Decentralized MDPs proved that the fundamental complexity of multi-agent coordination is dictated by the mathematical rank of the shared reward structure rather than the raw size of the state space. Pruning these redundant dimensions uncovers scenarios where an agent's optimal strategy is entirely invariant to the actions of others.

In deep learning applications, this low-rank principle keeps models lightweight. Wendelin Boehmer et al. implemented this in Deep Coordination Graphs by representing high-dimensional payoff matrices as the product of smaller, low-rank matrices (including Rank-1 decompositions). This drastically reduced parameter counts and computational overhead, enabling deep coordination graphs to scale successfully to complex environments like StarCraft II.


Real-World Evidence and Interpretability

Does the pairwise assumption hold up outside of synthetic benchmarks? Empirical data from human teams suggests that it does.

In sports analytics, Ryan Beal et al. looked at team formation in Learning the Value of Teamwork to Form Efficient Teams. They discovered that modeling a team as a network of directed pairwise interactions (such as passing combinations) predicted overall team performance with significantly higher accuracy than models focusing on aggregated individual player statistics. Similarly, in a large-scale study of 96 million matches of the MOBA game Honor of Kings, Ziqiang Cheng et al. found in What Makes a Good Team? A Large-scale Study on the Effect of Team Composition in Honor of Kings that calculating metrics for two-role combinations captured the vast majority of the predictive power needed to forecast match outcomes.

Beyond performance, restricting models to individual and pairwise terms yields a vital benefit: inherent human interpretability.

Fully joint neural networks operate as uninterpretable black boxes. However, by constraining value decomposition strictly to unary and binary terms, researchers can peer inside the model's decision logic. Zichuan Liu et al. developed this concept in N$\text{A}^\text{2}$Q: Neural Attention Additive Model for Interpretable Multi-Agent Q-Learning. Because the architecture isolates pairwise relationships, it can use attention mechanisms to provide clear, human-readable visualizations of agent coalitions and credit assignment in real time, proving that second-order dependencies capture the necessary cooperative tactics without sacrificing performance.

Key Foundational Work

Anytime Coordination Using Separable Bilinear Programs (2007) — contributed 2 concept elements to this direction.
Bi-capacities - II: the Choquet integral (2005) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_pairwise_interaction_modeling_a728184a,
  title = {pairwise interaction modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/pairwise-interaction-modeling/rdr_a728184a303a44d2998bd655ec29fe7b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_pairwise_interaction_modeling_a728184a_v1,
  title = {pairwise interaction modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/pairwise-interaction-modeling/rdr_a728184a303a44d2998bd655ec29fe7b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake