A No Free Lunch Theorem for Human-AI Collaboration

Jon Kleinberg; Kenny Peng; Nikhil Garg

REVIEW 2 major objections 3 minor 22 references

A No Free Lunch Theorem for Human-AI Collaboration

T0 review · 2 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read The only reliable way to combine calibrated human and AI judgments is to let one agent decide.

desk verdict New one-way impossibility result is real and worth engaging; the restated iff is false as written but fixable. read the letter →

arxiv 2411.15230 v1 pith:BTOSJ4JO submitted 2024-11-21 cs.AI cs.HCcs.LG

Kenny Peng , Nikhil Garg , Jon Kleinberg This is my paper · ORCID

classification cs.AIcs.HCcs.LG

keywords human-AIcollaborationcomplementaritycalibratedpredictionsnofreelunchtheorembinaryclassificationdecisionaggregationlearningtodeferimpossibility

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

This paper proves a no-free-lunch result for human-AI collaboration in binary classification. If each agent produces calibrated probability predictions, no deterministic rule for combining those probabilities into binary classifications can be guaranteed to match the accuracy of the worst individual agent unless that rule always follows one fixed agent. The result matters because the hoped-for benefit of human-AI teams—complementarity, beating both members alone—therefore cannot be achieved for free. It requires extra structure, such as independence between agents' predictions or learned knowledge of how their judgments jointly relate to outcomes. The only automatic exception is when another agent is entirely certain, which leaves a narrow but practical model of collaboration through overriding obvious errors.

What carries the argument

The proof constructs adversarial collaboration settings from finite input spaces and partitions of that space. A partition $\mathcal A_i$ induces a calibrated predictor $P_i(x) = \Pr[Y=1 \mid X \in A_i]$, so a setting can be specified by $(D, \mathcal A_1, \dots, \mathcal A_n)$. For any tuple on which $C$ disagrees with agent $k$, the paper builds a distribution over $X = \{0,1,\dots,n\}$ so that $C$ is wrong at a distinguished point while agent $k$ is at least as accurate; a linear-combination lemma (Proposition 6) then averages these per-agent settings into a single setting where $C$ is worse than every agent. The same construction is reused to force a fixed tie-break at $p_k = 1/2$.

What would settle it

A concrete falsifier would be a non-collaborative strategy $C$ that is not just deferring to one agent, together with a proof or exhaustive computation that $C$ meets the worst-agent accuracy on every collaboration setting. In particular, take $C$ to round the average of two calibrated probabilities and search over finite input spaces with partition-induced calibrated predictors; the paper's Lemma 8 construction implies the search will always find a setting where $C$ underperforms the worst agent, so exhibiting one such setting where it does not would contradict the proof.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for binary classification with $n$ calibrated agents and a deterministic collaboration strategy $C:[0,1]^n \to \{0,1\}$, if $C$ is reliable—meaning it achieves accuracy at least the minimum of the agents' accuracies for every collaboration setting—then $C$ is non-collaborative. In the paper's terms, there exists an agent $k$ such that for every interior tuple of probabilities, $C$ equals the threshold classification $\lfloor p_k \rceil$, with a fixed tie-break at $p_k = 1/2$ and exceptions only when some predictor is exactly $0$ or $1$. A collaboration strategy that genuinely combines agents—by averaging probabilities, taking majority votes, or deferring to the most confident agent—will sometimes perform strictly worse than the least accurate agent.

Load-bearing premise

The theorem's impossibility depends on letting the joint distribution of inputs and labels be completely arbitrary and chosen after the collaboration rule is fixed; if the distribution were restricted—say to real features, independence, or known correlation between agents—then some non-deferring rule could be reliable.

Editorial extensions

If this is right

Averaging probabilities, majority vote, and deferring to the most confident agent are all unreliable: each can perform worse than the least accurate calibrated agent on some setting.
Complementarity in prediction requires extra structure beyond calibrated individual predictions, specifically either independence among agents' signals or learned knowledge of the joint distribution of predictions and outcomes.
The only guaranteed collaboration protocol under the paper's assumptions is to give one agent primary authority and let another agent override only when it is fully certain, i.e. predicts probability exactly $0$ or $1$.
Common human-AI implementations that simply show a human a calibrated algorithmic probability lack both enabling conditions, so they should not be expected to deliver complementarity on their own.
Guarantees for ensemble and expert-combination methods trace to exactly these two structures, which explains why those methods succeed while general calibrated aggregation cannot.

Reading between the lines

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

A practical upshot the paper only states implicitly: displaying an AI confidence score to a human is unlikely to improve joint accuracy unless the system also learns, from paired human-AI decisions, when the human's judgment is more reliable than the AI's.
The certainty-override exception suggests a testable design: give an AI veto power only on inputs where a trustworthy model outputs probability exactly $0$ or $1$, with the human deciding everywhere else; the theorem predicts this is the only guaranteed-safe protocol under calibration alone.
The result transfers to ensembles of machine-learning models: averaging calibrated probability outputs is not universally reliable, so ensembles must either decorrelate their members or learn a weighting from validation data, mirroring the paper's independence-versus-learning dichotomy.
Because the theorem relies on unrestricted input distributions, a natural research direction is to characterize restricted families—real feature geometries, independence structures, or known correlations—under which non-deferring rules such as averaging become reliable; the paper explicitly leaves this open.

Share X Bluesky LinkedIn Reddit HN

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

Short version: this is a genuinely new impossibility result, and the main forward theorem is proved carefully. The restated “iff” in Section 4.2 is false as written, but it is a fixable overstatement; the one-way no-free-lunch claim survives.

What’s new: I don’t know of a prior result showing that a deterministic aggregator of calibrated probabilities that is reliable for all distributions must be a single-agent dictator on interior tuples. The proof is self-contained and constructive, using finite input spaces and calibrated predictors induced by partitions. That is formal and reproducible in the sense that the constructions are explicit. I also buy the interpretation: calibration is a per-agent marginal property; it doesn’t constrain joint behavior, so complementarity needs independence or learned joint structure. That’s a useful way to read the empirical human-AI collaboration literature.

Soft spots: the stated iff in Section 4.2 is wrong. Definition 4 lets C behave arbitrarily when some p_i is 0 or 1, and condition (ii) of the restated theorem only covers interior tuples. As a result, a non-collaborative C can fail reliability by mishandling certain inputs. The n=1 example in the stress test is enough: C(p)=floor p on (0,1), C(1)=0, C(0)=1 is non-collaborative by Definition 4 but fails on a point mass at label 1. The fix is to require deferring to any fully confident agent, which the paper’s own Section 2 discussion says is the intended design. That should be made part of the formal characterization. Also Eq (1) calls an expectation of 0-1 error “accuracy”; it is an error rate, so the inequality directions in the definitions need a careful sign check. Minor, but confusing.

I don’t see a deeper flaw. The forward impossibility proof uses valid finite calibrated settings and gluing via Proposition 6; the cases in Lemma 8 hold. The paper also openly flags the arbitrary-distribution assumption and suggests restricted distributions, multi-class problems, and other losses as open problems, so the scope is stated honestly.

Who for: people working on human-AI complementarity, learning to defer, ensemble methods, and impossibility results in prediction aggregation. It won’t change practice by itself, but it clarifies why calibration alone is insufficient. I’d send it to a serious referee; the iff fix is a minor revision, not a desk reject.

Referee Report

2 major / 3 minor

Summary. The paper studies deterministic collaboration strategies C:[0,1]^n -> {0,1} that combine calibrated probabilistic predictions from n agents. A strategy is called reliable if, in every collaboration setting, its 0-1 accuracy is at least the minimum accuracy of the individual agents. The main result, Theorem 1, claims that every reliable strategy is non-collaborative: it must essentially always follow the threshold classification of a single fixed agent, with only a fixed tie-break at p_k=1/2 and an exception when some agent is fully certain. The proof proceeds by showing that any violation of the non-collaborative condition lets one construct finite collaboration settings in which the strategy is strictly worse than the violating agent and no better than the others, and then combines these settings using linear mixtures. The paper uses the theorem to argue that complementarity cannot be achieved for free from calibration alone, and that successful collaboration requires independence or learned joint information.

Significance. If the one-way theorem is correct, this is a valuable conceptual result. The proof is self-contained and gives explicit finite constructions (Lemma 8, Proposition 9, Proposition 6); it does not rely on fitted parameters or circular assumptions. The paper is also appropriately cautious in Section 5 about the unrestricted distribution over X × {0,1}. The broad message, that calibration alone does not justify deferring to a confident-but-not-certain agent, is important for human-AI collaboration. However, the manuscript currently overstates the result by presenting an 'if and only if' characterization that is false, and this must be corrected before publication.

major comments (2)

[4.2 (Theorem 1)] The restated Theorem 1 in Section 4.2 is an 'if and only if' characterization, but the reverse implication is false as written. Definition 4 constrains C only on the interior (0,1)^n, leaving the boundary behavior free, so a strategy satisfying the stated interior conditions can be unreliable. For example, for n=1 define C(p)=1 for p>1/2, C(p)=0 for p<1/2, C(1)=0, C(0)=1, and C(1/2)=1. This satisfies conditions (i) and (ii) with k=1 and alpha=1. Now take X={x}, D the point mass with P_1(x)=1 and Y=1. P_1 is calibrated and acc_1=1, but C outputs 0 at the only input, so acc_C=0<1. Thus reliability does not follow from the stated conditions. The forward direction, proved via Lemma 8 and Proposition 9, appears sound, but the theorem should be restated as a one-way implication. Alternatively, Definition 4 should require C(p)=p_i whenever p_i is 0 or 1, which is what the informal discussion in Section 2 promises.
[2 (Definition 4 and the discussion after Theorem 1)] The informal claim that the only exception is deferring to a fully confident agent is not reflected in the formal definition, which permits arbitrary boundary choices when some p_i is 0 or 1. Because a calibrated predictor with P_i(x)=1 implies the label is 1 almost surely, any reliable strategy must output 1 on such points. The current definition allows boundary choices that break reliability, and this is exactly what makes the 'if' direction false. The formal definitions and the theorem should be aligned so that the promised certainty exception is part of the characterization, or the theorem should be stated without the converse direction.

minor comments (3)

[Proposition 6 proof] In the proof of Proposition 6, 'first randomly sampling m with probability λℓ' should read 'with probability λ_m'; the subscript typo makes the mixture construction harder to follow.
[Lemma 8 proof] In the second case of the proof, 'agent i is incorrect on x=0 and correct on x=1' should read '... and correct on x=i', matching the table and the input space X={0,1,...,n}.
[5 (Open Problems)] The important qualification that the result places no restrictions on the distribution over X × {0,1} appears only in the open problems. Consider stating this assumption earlier, since it is central for interpreting the theorem as a no-free-lunch result.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1 is proved from explicit finite calibrated constructions, with no fitted parameters, no prediction read back from inputs, and no load-bearing self-citation.

full rationale

The derivation is self-contained. Reliability is defined as a universal guarantee over all collaboration settings, and the proof proceeds by assuming a strategy C violates the non-collaborative condition, then constructing, for each agent k, a finite calibrated setting S_k (Lemma 8) in which C is strictly worse than agent k and no better than the others, using the actual tuple on which C deviates from the threshold classification. Proposition 6 glues these settings into a single distribution where C is worse than every agent, contradicting reliability. Proposition 9 handles the p_k = 1/2 case with another explicit construction. No parameter is fitted to data, no empirical citation carries the mathematical argument, and no conclusion is assumed inside the construction; the theorem is a direct implication of the definitions. The interpretive discussion in Section 3 and the analogy to the No Free Lunch theorem are not load-bearing for the proof. A boundary-case issue affects the literal truth of the restated 'iff' in Section 4.2, but that is a correctness caveat, not a circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters, invented entities, or fitted constants appear. The theorem is a pure impossibility argument resting on the calibration assumption, the unrestricted distribution assumption, and the deterministic-strategy assumption.

assumptions (4)

domain assumption Each predictor is calibrated on D in the strong sense Pr[Y=1 | P(X)=p] = p for every p in Image(P).
This is the only constraint on agents' predictions; the adversarial constructions in Lemma 8 and Proposition 9 rely on calibration holding exactly while the joint distribution of the agents' predictions is free.
domain assumption The input distribution D is unrestricted: any probability distribution over X times {0,1} is allowed.
The proof constructs adversarial finite distributions after seeing the collaboration strategy; restricting D, for example with feature structure, could open the door to reliable collaboration. The open problems section flags this.
domain assumption Collaboration strategies are deterministic functions from [0,1]^n to {0,1}.
Theorem 1 does not address randomized strategies; the negative result is proven only for deterministic rules.
standard math Standard probability theory over finite and countable spaces is used without formalization.
The proof assumes basic measure-theoretic probability and the existence of distributions over finite sets.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A No Free Lunch Theorem for Human-AI Collaboration." pith.science (2026). https://pith.science/paper/BTOSJ4JO

@misc{pith2026241115230,
  author       = {Pith},
  title        = {Pith review of: A No Free Lunch Theorem for Human-AI Collaboration},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BTOSJ4JO}},
  note         = {Machine review of arXiv:2411.15230}
}

read the original abstract

The gold standard in human-AI collaboration is complementarity -- when combined performance exceeds both the human and algorithm alone. We investigate this challenge in binary classification settings where the goal is to maximize 0-1 accuracy. Given two or more agents who can make calibrated probabilistic predictions, we show a "No Free Lunch"-style result. Any deterministic collaboration strategy (a function mapping calibrated probabilities into binary classifications) that does not essentially always defer to the same agent will sometimes perform worse than the least accurate agent. In other words, complementarity cannot be achieved "for free." The result does suggest one model of collaboration with guarantees, where one agent identifies "obvious" errors of the other agent. We also use the result to understand the necessary conditions enabling the success of other collaboration techniques, providing guidance to human-AI collaboration.

Figures

Figures reproduced from arXiv: 2411.15230 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 20 canonical work pages

[1]

R. Alur, M. Raghavan, and D. Shah. Distinguishing the indistinguishable: Human expertise in algorithmic prediction. arXiv preprint arXiv:2402.00793, 2024

arXiv 2024
[2]

K. J. Arrow. A difficulty in the concept of social welfare. Journal of Political Economy, 58 0 (4): 0 328--346, 1950

work page 1950
[3]

Bhatt, J

U. Bhatt, J. Antor \'a n, Y. Zhang, Q. V. Liao, P. Sattigeri, R. Fogliato, G. Melan c on, R. Krishnan, J. Stanley, O. Tickoo, et al. Uncertainty as a form of transparency: Measuring, communicating, and using uncertainty. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pages 401--413, 2021

work page 2021
[4]

A. Blum. On-line algorithms in machine learning. Online Algorithms: The State of the Art, pages 306--325, 2005

work page 2005
[5]

Bondi, R

E. Bondi, R. Koster, H. Sheahan, M. Chadwick, Y. Bachrach, T. Cemgil, U. Paquet, and K. Dvijotham. Role of human- AI interaction in selective prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 5286--5294, 2022

work page 2022
[6]

L. Breiman. Random forests. Machine Learning, 45: 0 5--32, 2001

2001
[7]

Bu c inca, M

Z. Bu c inca, M. B. Malaya, and K. Z. Gajos. To trust or to think: cognitive forcing functions can reduce overreliance on AI in AI -assisted decision-making. Proceedings of the ACM on Human-computer Interaction, 5 0 (CSCW1): 0 1--21, 2021

work page 2021
[8]

\'A . A. Cabrera, A. Perer, and J. I. Hong. Improving human- AI collaboration with descriptions of AI behavior. Proceedings of the ACM on Human-Computer Interaction, 7 0 (CSCW1): 0 1--21, 2023

work page 2023

Show all 22 references

[9]

de Condorcet

N. de Condorcet. Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix. 1785
[10]

De Toni, N

G. De Toni, N. Okati, S. Thejaswi, E. Straitouri, and M. Gomez-Rodriguez. Towards human- AI complementarity with predictions sets. arXiv preprint arXiv:2405.17544, 2024

2024 arXiv
[11]

Donahue, A

K. Donahue, A. Chouldechova, and K. Kenthapadi. Human-algorithm collaboration: Achieving complementarity and avoiding unfairness. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 1639--1656, 2022

2022
[12]

Green and Y

B. Green and Y. Chen. The principles and limits of algorithm-in-the-loop decision making. Proceedings of the ACM on Human-Computer Interaction, 3 0 (CSCW): 0 1--24, 2019

2019
[13]

Kiani, B

A. Kiani, B. Uyumazturk, P. Rajpurkar, A. Wang, R. Gao, E. Jones, Y. Yu, C. P. Langlotz, R. L. Ball, T. J. Montine, et al. Impact of a deep learning assistant on the histopathologic classification of liver cancer. NPJ Digital Medicine, 3 0 (1): 0 23, 2020

2020
[14]

Lai and C

V. Lai and C. Tan. On human predictions with explanations and predictions of machine learning models: A case study on deception detection. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 29--38, 2019

2019
[15]

Littlestone, P

N. Littlestone, P. M. Long, and M. K. Warmuth. On-line learning of linear functions. In Proceedings of the twenty-third annual ACM Symposium on Theory of Computing, pages 465--475, 1991

1991
[16]

Madras, T

D. Madras, T. Pitassi, and R. Zemel. Predict responsibly: improving fairness and accuracy by learning to defer. Advances in Neural Information Processing Systems, 31, 2018

2018
[17]

Mozannar, A

H. Mozannar, A. Satyanarayan, and D. Sontag. Teaching humans when to defer to a classifier via exemplars. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 5323--5331, 2022

2022
[18]

R. E. Schapire et al. A brief introduction to boosting. In IJCAI, volume 99, pages 1401--1406. Citeseer, 1999

1999
[19]

W. Shin, J. Han, and W. Rhee. AI -assistance for predictive maintenance of renewable energy systems. Energy, 221: 0 119775, 2021

2021
[20]

Straitouri, L

E. Straitouri, L. Wang, N. Okati, and M. G. Rodriguez. Improving expert predictions with conformal prediction. In International Conference on Machine Learning, pages 32633--32653. PMLR, 2023

2023
[21]

Vaccaro, A

M. Vaccaro, A. Almaatouq, and T. Malone. When combinations of humans and AI are useful: A systematic review and meta-analysis. Nature Human Behaviour, pages 1--11, 2024

2024
[22]

D. H. Wolpert and W. G. Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1 0 (1): 0 67--82, 1997

1997

Pith tools

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

[1] [1]

R. Alur, M. Raghavan, and D. Shah. Distinguishing the indistinguishable: Human expertise in algorithmic prediction. arXiv preprint arXiv:2402.00793, 2024

arXiv 2024

[2] [2]

K. J. Arrow. A difficulty in the concept of social welfare. Journal of Political Economy, 58 0 (4): 0 328--346, 1950

work page 1950

[3] [3]

Bhatt, J

U. Bhatt, J. Antor \'a n, Y. Zhang, Q. V. Liao, P. Sattigeri, R. Fogliato, G. Melan c on, R. Krishnan, J. Stanley, O. Tickoo, et al. Uncertainty as a form of transparency: Measuring, communicating, and using uncertainty. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pages 401--413, 2021

work page 2021

[4] [4]

A. Blum. On-line algorithms in machine learning. Online Algorithms: The State of the Art, pages 306--325, 2005

work page 2005

[5] [5]

Bondi, R

E. Bondi, R. Koster, H. Sheahan, M. Chadwick, Y. Bachrach, T. Cemgil, U. Paquet, and K. Dvijotham. Role of human- AI interaction in selective prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 5286--5294, 2022

work page 2022

[6] [6]

L. Breiman. Random forests. Machine Learning, 45: 0 5--32, 2001

2001

[7] [7]

Bu c inca, M

Z. Bu c inca, M. B. Malaya, and K. Z. Gajos. To trust or to think: cognitive forcing functions can reduce overreliance on AI in AI -assisted decision-making. Proceedings of the ACM on Human-computer Interaction, 5 0 (CSCW1): 0 1--21, 2021

work page 2021

[8] [8]

\'A . A. Cabrera, A. Perer, and J. I. Hong. Improving human- AI collaboration with descriptions of AI behavior. Proceedings of the ACM on Human-Computer Interaction, 7 0 (CSCW1): 0 1--21, 2023

work page 2023