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

Andrea Ferrario

REVIEW 1 major objections 5 minor 6 references

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

T0 review · 1 major / 5 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A tree-based theory shows complementarity is achievable in regression but blocked in binary classification.

desk verdict A genuinely useful formal framework for multi-agent complementarity, with solid math and a real framing problem: the negative results only hold under the pointwise-min benchmark, and the abstract overstates them. read the letter →

arxiv 2606.04779 v2 pith:NBJ7YWT4 submitted 2026-06-03 cs.AI math.CO

Andrea Ferrario This is my paper · ORCID

classification cs.AImath.CO

keywords complementarityhuman-AIinteractionmulti-agentprotocolsplanarbinarytreesprotocolpointwise-minbenchmarkTamarilatticeclassificationimpossibility

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish a formal theory of complementarity — a human-AI interaction beating the best available prediction — for workflows with more than two agents. It models an interaction as a protocol tree whose leaves carry prediction vectors and whose internal nodes combine them with a local rule. Against a pointwise-min benchmark, it proves that selector-style reliance can never be complementary, that in squared-loss regression complementarity reduces to Euclidean distance minimization with a closed-form optimal weight for two agents, and that in binary classification no internal averaging rule can achieve complementarity under endpoint-monotone losses such as cross-entropy. If correct, it would reorient empirical HAI research: complementarity is a genuine regression phenomenon, but classification studies must look beyond interpolating between human and AI probabilities.

What carries the argument

Protocol trees: rooted planar binary trees whose leaves are decorated by ordered agent prediction vectors and whose internal nodes carry a local binary composition rule; evaluating the rule recursively yields the protocol output. The tree-relative complementarity functional Ψ = Φ − Θ compares the pointwise-min benchmark loss Φ (Eq. 6) with the protocol loss Θ (Eq. 7). The argument is carried by the internality property (coordinatewise outputs remain between the input probabilities) combined with endpoint-monotone losses, and by the barycentric coordinate map φ_T from local linear-pooling weights to the simplex of leaf weights, with Tamari-cover reparameterizations preserving protocol output

What would settle it

Run a binary classification experiment with two probabilistic predictors and any internal local rule, such as the coordinatewise arithmetic mean, using an endpoint-monotone loss like cross-entropy, on a dataset where for every case the pooled probability is strictly closer to the true label than both inputs. Theorem 4 predicts the tree-relative complementarity Ψ is always ≤ 0; finding one such dataset with Ψ > 0 would refute it.

Watch

Extended reading notes

Core claim

The central claim is a structural containment result: with the pointwise-min oracle benchmark (Eq. 6), the class of complementary multi-agent protocol outputs is empty for selectors and for internal rules in binary classification. Regression under squared loss is the positive counterpart: the complementarity functional satisfies nΨ = nK_n − ∥y − ŷ_T∥², so maximizing complementarity is equivalent to moving the protocol output close to the ground-truth vector; for N=2 the optimal linear weight is α* = Π[0,1](−B_n/A_n) with B_n = ⟨ŷ_H − ŷ_AI, ŷ_AI − y⟩, giving a residual-correction interpretation. Thus complementarity is attainable only when aggregation is non-internal or the loss is not endpoi

Load-bearing premise

The impossibility results rest on measuring complementarity against the pointwise-min oracle benchmark (Eq. 6); if the right benchmark for a given HAI is instead the best fixed predictor's average loss, then Theorem 1 and Theorem 4 no longer apply and classification complementarity is not ruled out.

Editorial extensions

If this is right

Selector-based HAIs, including self-reliance and AI-reliance, never achieve complementarity relative to the pointwise-min benchmark, for any task, loss, or prediction quality.
In squared-loss regression, maximizing complementarity is Euclidean distance minimization from the ground-truth vector; for N=2, the optimal linear-pooling weight has a closed form and depends on whether the human-AI disagreement direction corrects the AI residual.
In regression with linear pooling, Tamari-cover reparameterizations of protocol trees preserve complementarity; for N=4, the two directed Tamari paths from the left comb to the right comb induce the same reparameterization, satisfying the pentagon identity.
In binary classification, no internal local rule can achieve complementarity under endpoint-monotone losses, including Bregman and many finite Bernoulli f-divergence losses; an analogous obstruction holds for coordinatewise-internal multiclass aggregation under cross-entropy.
Non-internal rules such as amplified logit pooling can escape the classification impossibility, although the relation between local outside-interval rates and global complementarity is not deterministic under unbounded cross-entropy.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the appropriate deployment benchmark is the best fixed predictor averaged over cases rather than the pointwise-min oracle, the classification impossibility dissolves; empirical complementarity findings may therefore be highly sensitive to this normative benchmark choice.
A practical design prescription follows: classification workflows seeking complementarity should deliberately extrapolate beyond the convex hull of agent probabilities — e.g., amplified logarithmic pooling — rather than averaging calibrated probabilities.
The Tamari-reparameterization result suggests a broader equivalence principle: under linear pooling, workflow topology matters only through the induced barycentric leaf weights, so two protocols with related parameter maps could be tested for equal loss on real teams.
A testable extension would add interaction costs (depth, monitoring burden) to the optimization, likely shifting the optimal protocol tree away from the complementarity-maximizing topology identified here.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Worth reading. Ferrario gives HAI theory something it lacked: a precise, tree-based language for multi-agent protocols, plus several real results. The regression story is the strongest part—complementarity as Euclidean distance minimization (Prop. 2), the closed-form N=2 optimizer with the residual-correction interpretation (Prop. 4), and the Tamari reparameterization/pentagon identity are clean and correct. The selector impossibility (Thm. 1) and the endpoint-monotone classification obstruction (Thm. 4) are also proved properly; I spot-checked the key algebra and it holds. The paper is honest enough to disclose the benchmark choice in Section 3.2.3. That is where the trouble starts. The impossibility theorems are all relative to the pointwise-min benchmark, not the aggregate benchmark used in most of the HAI literature. And this is not a minor technicality. Under the aggregate benchmark, selectors can be complementary (pick the better agent per case), and internal rules can be complementary too. Simple example: y=(1,0), H=(0.9,0.9), A=(0.1,0.1), m=(u+v)/2. Then L_H=L_A=0.41, L_T=0.25, so C=0.16>0, while the pointwise-min benchmark gives Φ=0.01 and Ψ=-0.24<0. Same internal rule, same endpoint-monotone loss, same dataset. So the headline 'complementarity is obstructed in classification' is only true for one benchmark, and the abstract/conclusion state it without the qualifier. The stress-test note gets this right in substance, though its concrete numbers are off (it claims L_H=L_A=0.41 for H=(0.9,0.1), A=(0.1,0.9), which are not right). The fix is easy: qualify all negative claims as relative to the pointwise-min oracle, and move the benchmark discussion to the front of the paper rather than burying it halfway through. Minor issues: no machine-checked proofs (though the proofs are short and checkable), and the numerical illustrations carry no error bars but are explicitly illustrative, so I am not worried. The distinction between the two benchmarks is genuinely important for HAI practice, and the paper's framework is the right tool to have that conversation in. This deserves a serious referee and, with the benchmark qualifier added to the main claims, acceptance. For me, it is a definite cite in the next twelve months.

Referee Report

1 major / 5 minor

Summary. The paper develops a tree-based formal framework for studying complementarity in multi-agent human–AI interactions. An HAI protocol is represented by an ordered configuration of agents and a rooted planar binary tree whose leaves carry prediction vectors; a local binary composition rule is evaluated recursively to produce the protocol output. Complementarity is defined via the pointwise-min oracle benchmark (Eq. 6), and the main results are: (1) selector rules cannot be complementary (Theorem 1); (2) under squared-loss regression, maximizing complementarity is equivalent to Euclidean distance minimization, with a closed-form optimal pooling weight for N=2 (Props. 2 and 4); (3) under linear pooling, protocol trees induce barycentric coordinate charts and Tamari-cover reparameterizations preserve complementarity, with a pentagon identity for N=4 (Prop. 6, Thms. 2 and 3); (4) in binary classification with endpoint-monotone losses, no internal local rule can achieve positive complementarity (Theorem 4), with an analogous multiclass obstruction under cross-entropy. Numerical illustrations accompany the regression and classification results.

Significance. If the results are correct, the paper makes a substantive formal contribution: it moves complementarity from two-agent loss comparisons to a setting with explicit workflow topology, and it gives clean geometric and algebraic characterizations. The closed-form N=2 regression optimizer and the classification impossibility theorem are crisp and falsifiable. The paper is also careful in presenting proofs in appendices, and the key computations I checked (Theorem 2's parameter transport, Proposition 5's coefficient identities, and Theorem 4's endpoint-monotone argument) are sound. The main caveat, already acknowledged in §3.2.3, is that all impossibility results are relative to the pointwise-min benchmark, not the aggregate benchmark C in Eq. (8); this matters for interpreting the practical scope of Theorem 4. Overall, the framework is a valuable addition to the formal HAI literature.

major comments (1)

[Abstract and §9] The headline claim that 'complementarity is obstructed in classification' is stated in the abstract and in the fourth discussion message without the explicit qualifier 'relative to the pointwise-min benchmark'. Section 3.2.3 correctly shows that the aggregate benchmark C (Eq. 8) can report positive complementarity for the same internal rule, dataset, and endpoint-monotone loss, even when Ψ is negative. Since Theorem 4 is a statement about Ψ, the unqualified sentences overstate the theorem's scope. I recommend adding the benchmark qualifier wherever the impossibility is advertised outside the formal theorem statements.

minor comments (5)

[§3.2.3] The notation 'CmT_{N,T}' in Eq. (8) is slightly confusing because the subscript already contains T; consider using C^{m_T}_{N,T} or a clearer symbol such as C_N^{m_T}.
[§4.2] The sentence 'selectors cannot yield complementarity' in the text preceding Theorem 1 is accurate only for Ψ. Since the aggregate benchmark C can be positive for a casewise selector, please add a forward reference to the benchmark discussion in §3.2.3 at this point.
[References] The bibliography lists 'Hemmer et al.' with inconsistent first-author naming: Patrick Hemmer et al. (2021) and Philipp Hemmer et al. (2025). Please standardize.
[Fig. 9] The caption says 'blue points satisfy nΨ>0' while the color scale is not fully accessible in black-and-white print. Consider adding a symbol or grey-scale pattern to distinguish the two classes.
[Appendix E/F] The numerical experiments are explicitly synthetic illustrations, but they lack error bars or repeated-seed sensitivity analysis. A short sentence acknowledging that the plots are deterministic illustrations of the theorems would be sufficient.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the formal results follow algebraically from stated definitions, and the benchmark dependence is explicitly disclosed rather than hidden.

full rationale

The derivation chain is self-contained. Definitions 4–5 fix the complementarity functional relative to the pointwise-min oracle benchmark; Theorem 1 and Theorem 4 are direct analytic consequences of those definitions plus the selector/internality and endpoint-monotonicity assumptions, not of any fitted quantity. Proposition 2 and Proposition 4 derive the squared-loss identity nΨ = nK_n − ||y − ŷ_T||² and the closed-form optimizer α* = Π[0,1](−B_n/A_n) by expanding the quadratic loss; the numerical illustrations compute quantities from fixed prediction vectors and do not fit a parameter and then call a closely related quantity a prediction. The Tamari results (Proposition 7, Theorems 2–3) prove the existence of explicit coordinate changes that preserve root output; the complementarity-invariance statement then follows because Ψ depends on the tree only through the protocol-output loss Θ_T, but the existence claim itself is nontrivial and verified by coefficient identities. Self-citations (Ferrario 2025; Ferrario et al. 2026) concern reliance terminology and future-work 'efficient complementarity'; they are not load-bearing for the theorems. The only scope limitation is that the classification impossibility is relative to the pointwise-min benchmark rather than the aggregate benchmark, and Section 3.2.3 explicitly presents a numerical example in which the aggregate benchmark reports positive complementarity while the pointwise-min benchmark reports failure. That is a disclosed normative benchmark choice, not an equation-level circularity or a fitted-input prediction.

Assumptions & free parameters 2 free parameters · 7 assumptions · 0 invented entities

The core theorems depend only on definitions and standard combinatorics; no data fitting is used. The only hand-chosen numbers are simulation knobs in the numerical illustrations, explicitly declared in Appendices E-G. The pointwise-min benchmark, binary-tree locality, and endpoint-monotone/internal-rule conditions are stated assumptions, not hidden parameters.

free parameters (2)

Pooling weight α in the classification simulation = 0.5 (hand-fixed)
Used in Eq. (25) with α=0.5 for the amplified-logit simulation in §8.1.1; not fitted and not part of the main theorems.
Amplification level λ = varied over {1,2,5,10,20}
Introduced in Eq. (25) to illustrate that non-internal rules can escape Theorem 4; hand-chosen values only, no optimality criterion derived.

assumptions (7)

domain assumption Complementarity is measured against the pointwise-min benchmark Φ = (1/n) Σ_i min_j ℓ(y_i, ŷ_i^(j)) (Eq. 6).
All negative results (Thm 1, Thm 4) are proved against this benchmark. Section 3.2.3 states all complementarity claims are relative to it; the aggregate benchmark would invalidate the classification obstruction.
domain assumption Protocols are represented by rooted planar binary trees with local binary composition (Assumption 2).
Excludes simultaneous or higher-arity interactions; acknowledged as a simplification in §3.2.2.
domain assumption Complementarity functionals decompose as benchmark minus protocol loss (Assumption 1).
Defines Ψ in Def. 5 and is used by every subsequent formula.
domain assumption All agents act on the same dataset and predict the same target for the same prediction task.
Stated in §3.1; restricts the framework to prediction-task HAIs.
domain assumption For Theorem 4, losses are endpoint-monotone and local rules satisfy the internality property.
Theorem hypotheses that define the classification scope. Prop. 8 shows Bregman and finite Bernoulli f-divergence losses are endpoint-monotone; internality is Definition 10.
standard math Standard facts about Catalan numbers, the Tamari lattice, and the associahedron.
Used in Definition 2, Definition 7, and Theorem 3 without proof.
standard math Convexity facts used in Appendix D for Bregman and f-divergence endpoint monotonicity.
Relies on tangent inequalities for convex F and f, and monotonicity of the associated functions G0 and G1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Tree-Based Formalization of Multi-Agent Complementarity in Human-AI Interactions." pith.science (2026). https://pith.science/paper/NBJ7YWT4

@misc{pith2026260604779,
  author       = {Pith},
  title        = {Pith review of: Tree-Based Formalization of Multi-Agent Complementarity in Human-AI Interactions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NBJ7YWT4}},
  note         = {Machine review of arXiv:2606.04779}
}

abstract

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.

Figures

Figures reproduced from arXiv: 2606.04779 by the authors.

**Figure 2.** The rooted planar binary tree for N = 2, with leaves decorated by human and AI roles, the corresponding prediction vectors yˆ (1) and yˆ (2) . yˆT is the tree output. If An > 0, the maximizing weight is α ∗ = Π[0,1] − Bn An . If An = 0, the aggregate is constant in α and yields no complementarity. Proof. Appendix A. Proposition 4 admits an explicit geometric interpretation. Let us rewrite Bn as Bn = ∥yˆ H − yˆ AI… view at source ↗

**Figure 3.** Geometry for the N = 2 regression case with linear pooling. The segment of the line through yˆ AI and yˆ H that lies between the two vectors is the locus of feasible human–AI team predictions. The line through the origin 0 is the human–AI disagreement direction. The vector yˆ AI − y is projected onto this line and θ is the angle between yˆ AI − y and yˆ H − yˆ AI . The interior case inequalities (16) are both satisf… view at source ↗

Figures from the paper (6 more)

**Figure 4.** Figure 4: N = 2 regression complementarity under linear pooling using the California housing dataset. Each curve shows the quadratic value of nΨ mid 2,α T [($100,000)2 ] as a function of the aggregation weight α, for synthetic human predictions constructed by controlling the ang…

**Figure 5.** Figure 5: The two rooted planar binary trees for N = 3 and the ordered configuration (expert, assistant, AI), with corresponding prediction vectors yˆ (1) , yˆ (2), and yˆ (3). The trees represent two distinct protocols of the same predictiontask HAI: TL = ((12)3) first combine…

**Figure 6.** Figure 6: N = 3 regression complementarity under linear pooling using the California housing dataset. Each panel shows the values of P(α1, α2)/n [($100,000)2 ] and the protocol-indifference locus P(α1, α2) = 0 for the two protocol trees TL = ((12)3) and TR = (1(23)). Blue region…

**Figure 7.** Figure 7: The five rooted planar binary trees for N = 4 under the ordered configuration (user, AI, AI, user), with corresponding prediction vectors yˆ (1) , yˆ (2) , yˆ (3) , yˆ (4) and tree outputs yˆT1 , . . . , yˆT5 . 6 Trees in Regression Under Linear Pooling: Barycentric Co…

**Figure 8.** Figure 8: The pentagon identity satisfied by the Tamari-cover reparameterizations for [PITH_FULL_IMAGE:figures/full_fig_p018_8.png]

**Figure 9.** Figure 9: N = 2 binary classification under cross-entropy with amplified logit pooling and fixed α = 0.5. Each point is one simulated pair of probabilistic predictors, plotted by the class-wise rates (k0, k1) of canonical local complementarity: for yi = 0, the pooled prediction …

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

6 extracted references · 2 linked inside Pith

[5]

No-regret learning with unbounded losses: The case of logarithmic pooling

Eric Neyman and Tim Roughgarden. No-regret learning with unbounded losses: The case of logarithmic pooling. Advances in Neural Information Processing Systems, 36:21857–21877, 2023a. Eric Neyman and Tim Roughgarden. From proper scoring rules to max-min optimal forecast aggregation.Operations Research, 71(6):2175–2195, 2023b. Helbert Paat and Guohao Shen. C...

arXiv
[1930]

Explainable AI is dead, long live explainable AI! Hypothesis-driven decision support using evaluative AI

Tim Miller. Explainable AI is dead, long live explainable AI! Hypothesis-driven decision support using evaluative AI. InProceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency, pages 333–342,

2023
[1966]

Is the most accurate AI the best teammate? Optimizing ai for teamwork

Gagan Bansal, Besmira Nushi, Ece Kamar, Eric Horvitz, and Daniel S Weld. Is the most accurate AI the best teammate? Optimizing ai for teamwork. InProceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11405–11414, 2021a. Gagan Bansal, Tongshuang Wu, Joyce Zhou, Raymond Fok, Besmira Nushi, Ece Kamar, Marco Tulio Ribeiro, and Daniel...

2021
[1967]

Human-algorithm collaboration: Achieving complementarity and avoiding unfairness

Kate Donahue, Alexandra Chouldechova, and Krishnaram Kenthapadi. Human-algorithm collaboration: Achieving complementarity and avoiding unfairness. InProceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 1639–1656,

2022
[2024]

Effect of confidence and explanation on accuracy and trust calibration in AI-assisted decision making

Yunfeng Zhang, Q Vera Liao, and Rachel KE Bellamy. Effect of confidence and explanation on accuracy and trust calibration in AI-assisted decision making. InProceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 295–305,

2020
[2025]

Epistemology gives a future to complementarity in human-AI interactions.arXiv preprint arXiv:2601.09871,

Andrea Ferrario, Alessandro Facchini, and Juan M Durán. Epistemology gives a future to complementarity in human-AI interactions.arXiv preprint arXiv:2601.09871,

arXiv

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.

[1] [5]

No-regret learning with unbounded losses: The case of logarithmic pooling

Eric Neyman and Tim Roughgarden. No-regret learning with unbounded losses: The case of logarithmic pooling. Advances in Neural Information Processing Systems, 36:21857–21877, 2023a. Eric Neyman and Tim Roughgarden. From proper scoring rules to max-min optimal forecast aggregation.Operations Research, 71(6):2175–2195, 2023b. Helbert Paat and Guohao Shen. C...

arXiv

[2] [1930]

Explainable AI is dead, long live explainable AI! Hypothesis-driven decision support using evaluative AI

Tim Miller. Explainable AI is dead, long live explainable AI! Hypothesis-driven decision support using evaluative AI. InProceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency, pages 333–342,

2023

[3] [1966]

Is the most accurate AI the best teammate? Optimizing ai for teamwork

Gagan Bansal, Besmira Nushi, Ece Kamar, Eric Horvitz, and Daniel S Weld. Is the most accurate AI the best teammate? Optimizing ai for teamwork. InProceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11405–11414, 2021a. Gagan Bansal, Tongshuang Wu, Joyce Zhou, Raymond Fok, Besmira Nushi, Ece Kamar, Marco Tulio Ribeiro, and Daniel...

2021

[4] [1967]

Human-algorithm collaboration: Achieving complementarity and avoiding unfairness

Kate Donahue, Alexandra Chouldechova, and Krishnaram Kenthapadi. Human-algorithm collaboration: Achieving complementarity and avoiding unfairness. InProceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 1639–1656,

2022

[5] [2024]

Effect of confidence and explanation on accuracy and trust calibration in AI-assisted decision making

Yunfeng Zhang, Q Vera Liao, and Rachel KE Bellamy. Effect of confidence and explanation on accuracy and trust calibration in AI-assisted decision making. InProceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 295–305,

2020

[6] [2025]

Epistemology gives a future to complementarity in human-AI interactions.arXiv preprint arXiv:2601.09871,

Andrea Ferrario, Alessandro Facchini, and Juan M Durán. Epistemology gives a future to complementarity in human-AI interactions.arXiv preprint arXiv:2601.09871,

arXiv