Tree-Based Formalization of Multi-Agent Complementa... | AI Research

Tree-Based Formalization of Multi-Agent Complementarity in Human-AI Interactions
This research addresses a fundamental gap in how we understand "complementarity"—the phenomenon where a team of humans and AI systems performs better than any single member could on their own. While this concept is central to human-AI interaction (HAI), existing frameworks have largely been limited to simple two-agent scenarios. This paper introduces a new mathematical framework that models complex, multi-agent workflows as tree-based structures, allowing researchers to analyze how different interaction protocols and sequences of collaboration affect the final performance of a team.

Modeling Interactions as Trees

To move beyond simple two-agent models, the author represents multi-agent workflows using rooted planar binary trees. In this framework, the leaves of the tree represent the individual prediction vectors of various human and AI agents. As you move up the tree, internal nodes represent "local composition rules"—the specific ways in which two predictions are combined into a single, intermediate output. By evaluating these rules recursively from the leaves to the root, the framework produces a final team prediction. This allows the model to account for the specific order and structure of a workflow, which is critical in real-world settings like medicine or public administration where multiple experts and AI tools contribute to a single decision.

Key Findings on Performance

The research provides four major insights into when and how complementarity can be achieved:

• The Limits of Selection: The author proves that "selector-based" interactions—where the team simply chooses one of the existing agent predictions (such as in basic AI-reliance or self-reliance)—cannot achieve true complementarity. To outperform the best individual, the team must generate a new output that is not merely a selection from the inputs.

• Success in Regression: In regression tasks using squared loss, complementarity is mathematically equivalent to minimizing the distance between the team's output and the ground truth. The framework provides a clear way to calculate the optimal interaction strategy for these tasks.

• Structural Invariance: The study shows that under linear composition, the specific "shape" of the interaction tree can be reconfigured (using mathematical moves known as Tamari covers) without losing the level of complementarity, provided the internal parameters are adjusted accordingly.

• Obstacles in Classification: In binary and multiclass classification, the paper identifies a significant barrier. Under standard conditions (such as endpoint-monotone losses like cross-entropy), it is impossible for internal local rules to achieve complementarity. This suggests that achieving better-than-individual performance in classification requires more sophisticated, non-internal aggregation methods.

Implications for Future Research

The framework highlights that complementarity is not a guaranteed outcome of combining agents; it is highly sensitive to the structure of the protocol and the nature of the task. Because the author uses a "pointwise-min" benchmark—which evaluates the team against the best possible prediction for each specific instance—the results suggest that many current empirical studies might be overestimating the success of human-AI teams. The author concludes that if this benchmark is considered appropriate for high-stakes decision-making, the field needs to fundamentally revise how it measures and investigates the success of human-AI collaboration.