# Tree-Based Formalization of Multi-Agent Complementarity in Human-AI Interactions

arXiv: https://arxiv.org/abs/2606.04779 · HTML: https://mlsanity.com/paper/2606.04779/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 29 references that are in the map.
- First posted on arXiv 3 Jun 2026.

## Builds on (most cited first, 15 of 15)

- [Does the Whole Exceed its Parts? The Effect of AI Explanations on Complementary Team Performance](https://mlsanity.com/paper/2006.14779/) (2020)
- [Effect of Confidence and Explanation on Accuracy and Trust Calibration in AI-Assisted Decision Making](https://mlsanity.com/paper/2001.02114/) (2020)
- [When combinations of humans and AI are useful: A systematic review and meta-analysis](https://mlsanity.com/paper/2405.06087/) (2024)
- [Appropriate Reliance on AI Advice: Conceptualization and the Effect of Explanations](https://mlsanity.com/paper/2302.02187/) (2023)
- [Explainable AI is Dead, Long Live Explainable AI! Hypothesis-driven decision support](https://mlsanity.com/paper/2302.12389/) (2023)
- [Learning to Defer to Multiple Experts: Consistent Surrogate Losses, Confidence Calibration, and Conformal Ensembles](https://mlsanity.com/paper/2210.16955/) (2022)
- [Human-Algorithm Collaboration: Achieving Complementarity and Avoiding Unfairness](https://mlsanity.com/paper/2202.08821/) (2022)
- [Forming Effective Human-AI Teams: Building Machine Learning Models that Complement the Capabilities of Multiple Experts](https://mlsanity.com/paper/2206.07948/) (2022)
- [Complementarity in Human-AI Collaboration: Concept, Sources, and Evidence](https://mlsanity.com/paper/2404.00029/) (2024)
- [A Taxonomy of Human and ML Strengths in Decision-Making to Investigate Human-ML Complementarity](https://mlsanity.com/paper/2204.10806/) (2022)
- [A No Free Lunch Theorem for Human-AI Collaboration](https://mlsanity.com/paper/2411.15230/) (2024)
- [From Proper Scoring Rules to Max-Min Optimal Forecast Aggregation](https://mlsanity.com/paper/2102.07081/) (2021)
- [No-Regret Learning with Unbounded Losses: The Case of Logarithmic Pooling](https://mlsanity.com/paper/2202.11219/) (2022)
- [Epistemology gives a Future to Complementarity in Human-AI Interactions](https://mlsanity.com/paper/2601.09871/) (2026)
- [Conformal Set-based Human-AI Complementarity with Multiple Experts](https://mlsanity.com/paper/2508.06997/) (2025)

## Abstract (arXiv)

Complementarity is the case in which a human--AI interaction (HAI) outperforms the best prediction benchmark available among its members. Although this idea is central in HAI research, formal work on complementarity remains limited. Existing frameworks do not model how agents' predictions compose into workflow-sensitive multi-agent protocols. We close this gap by introducing a tree-based formalization of complementarity in multi-agent HAI. An HAI protocol is represented by an ordered agent-role configuration together with a rooted planar binary tree whose leaves are decorated by prediction vectors. A local binary composition rule is evaluated recursively along the tree, yielding a tree-relative complementarity functional relative to a pointwise-min benchmark. We prove four results. First, selector-based HAIs, including reliance, cannot achieve complementarity regardless of task, loss, or prediction quality. Second, in regression under squared loss, complementarity is equivalent to Euclidean distance minimization from the ground-truth vector; for N=2, the optimal linear-pooling weight has a closed form and a residual-correction interpretation. Third, under linear local composition, every protocol tree defines a barycentric coordinate chart on the simplex of leaf weights; Tamari-cover reparameterizations of protocol trees preserve complementarity, and for all N, any two Tamari paths with the same initial and terminal trees preserve the protocol output and complementarity. Fourth, in binary classification, no internal local composition can achieve complementarity under endpoint-monotone losses, including standard Bregman and many finite Bernoulli f-divergence losses; an analogous obstruction holds for multiclass aggregation under cross-entropy. In summary, our framework shows that complementarity is attainable in multi-agent regression, but obstructed in classification.