Research map / Multi-agent systems and games / Human-AI and goal-conditioned
A No Free Lunch Theorem for Human-AI Collaboration
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical no-free-lunch result showing that any deterministic collaboration strategy combining calibrated probabilistic predictions that never performs worse than the least accurate agent must essentially always defer to one fixed agent.
Problem
When can combining calibrated probabilistic predictions from multiple agents (e.g., humans and algorithms) in binary classification guarantee complementarity, i.e., accuracy at least as good as the least accurate agent and sometimes better than all agents?
Approach
Proves that reliable (never worse than the worst agent) deterministic collaboration strategies over calibrated predictors must be non-collaborative, deferring to a single fixed agent except when another agent is fully certain (predicts exactly 0 or 1); the proof builds adversarial collaboration settings via partitions and mixes them linearly.
Key results
- Any reliable deterministic collaboration strategy over calibrated agents is non-collaborative: it essentially always defers to a single fixed agent, except when another agent is fully certain (predicts exactly 0 or 1).
- Common strategies (probability averaging, majority vote, deferring to the most confident agent) are shown not to be reliable, sometimes performing worse than the least accurate agent.
- Under 0-1 accuracy, calibration alone is insufficient for guaranteed complementarity; joint information across agents (learning or independence) is needed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a deterministic collaboration strategy that does not always defer to one fixed agent | Collaboration among calibrated agents · Binary classification | 0-1 accuracy | Hurt |
| Defer to a fixed agent except when another agent is fully certain | Collaboration among calibrated agents · Binary classification | 0-1 accuracy | Helped |
| Defer to an agent who is very confident but not certain | Collaboration among calibrated agents · Binary classification | 0-1 accuracy | No clear effect |
| Use independence between agents’ predictions | Prediction aggregation · Binary classification | 0-1 accuracy | Helped |
| Learn the joint behavior of agents to decide when and how much to trust them | Prediction aggregation · Binary classification | 0-1 accuracy | Helped |
Surprising findings
- Calibration alone, which gives each agent strong individual information, does not suffice to guarantee that combining agents never underperforms the worst agent.
- Being merely very confident (e.g., predicting 0.95) is not enough for a safe override; only full certainty (0 or 1) permits deferral guarantees.
Limitations
- Results apply only to 0-1 accuracy in binary classification; extension to other losses (e.g., l2) and multi-class is open.
- The result places no restrictions on the data distribution, so structured settings where collaboration succeeds are not characterized.
- Analysis is theoretical with no empirical validation on real human-AI collaboration data.
Experimental setup
Metrics: 0-1 accuracy
Builds on: Wolpert and Macready No Free Lunch theorem Arrow's Impossibility Theorem Condorcet's Jury Theorem
Closest papers by meaning
- Human-AI Teaming Through the Lens of Calibration (NeurIPS 2026 · similarity 0.89)
- Human Expertise in Algorithmic Prediction (NeurIPS 2024 · similarity 0.86)
- Towards Human-AI Complementarity with Prediction Sets (NeurIPS 2024 · similarity 0.86)
- Adaptive Agents for Mixed-Initiative Human-AI Collaborations (AAAI 2025 · similarity 0.86)
- Learning to Decide with AI Assistance under Human-Alignment (NeurIPS 2026 · similarity 0.86)
- Designs for Enabling Collaboration in Human-Machine Teaming via Interactive and Explainable Systems (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.