# Towards Human-AI Complementarity with Prediction Sets

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 58 references that are in the map.
- First posted on arXiv 27 May 2024.

## Builds on (most cited first, 30 of 36)

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Effect of Confidence and Explanation on Accuracy and Trust Calibration in AI-Assisted Decision Making](https://mlsanity.com/paper/2001.02114/) (2020)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Consistent Estimators for Learning to Defer to an Expert](https://mlsanity.com/paper/2006.01862/) (2020)
- [Learning to Complement Humans](https://mlsanity.com/paper/2005.00582/) (2020)
- [The Algorithmic Automation Problem: Prediction, Triage, and Human Effort](https://mlsanity.com/paper/1903.12220/) (2019)
- [Towards a Science of Human-AI Decision Making: A Survey of Empirical Studies](https://mlsanity.com/paper/2112.11471/) (2021)
- [Differentiable Learning Under Triage](https://mlsanity.com/paper/2103.08902/) (2021)
- [Who Should Predict? Exact Algorithms For Learning to Defer to Humans](https://mlsanity.com/paper/2301.06197/) (2023)
- [Improving Expert Predictions with Conformal Prediction](https://mlsanity.com/paper/2201.12006/) (2022)
- [Conformal Prediction for Deep Classifier via Label Ranking](https://mlsanity.com/paper/2310.06430/) (2023)
- [Top-label calibration and multiclass-to-binary reductions](https://mlsanity.com/paper/2107.08353/) (2021)
- [Sample Efficient Learning of Predictors that Complement Humans](https://mlsanity.com/paper/2207.09584/) (2022)
- [How model accuracy and explanation fidelity influence user trust](https://mlsanity.com/paper/1907.12652/) (2019)
- [Classification Under Human Assistance](https://mlsanity.com/paper/2006.11845/) (2020)
- [Regression Under Human Assistance](https://mlsanity.com/paper/1909.02963/) (2019)
- [Conformal Prediction Sets Improve Human Decision Making](https://mlsanity.com/paper/2401.13744/) (2024)
- [On the Utility of Prediction Sets in Human-AI Teams](https://mlsanity.com/paper/2205.01411/) (2022)
- [Advancing Human-AI Complementarity: The Impact of User Expertise and Algorithmic Tuning on Joint Decision Making](https://mlsanity.com/paper/2208.07960/) (2022)
- [Conformal prediction under ambiguous ground truth](https://mlsanity.com/paper/2307.09302/) (2023)
- [Human-Aligned Calibration for AI-Assisted Decision Making](https://mlsanity.com/paper/2306.00074/) (2023)
- [Set-valued classification -- overview via a unified framework](https://mlsanity.com/paper/2102.12318/) (2021)
- [Uncalibrated Models Can Improve Human-AI Collaboration](https://mlsanity.com/paper/2202.05983/) (2022)
- [Designing Decision Support Systems Using Counterfactual Prediction Sets](https://mlsanity.com/paper/2306.03928/) (2023)
- [Misplaced Trust: Measuring the Interference of Machine Learning in Human Decision-Making](https://mlsanity.com/paper/2005.10960/) (2020)
- [Reinforcement Learning Under Algorithmic Triage](https://mlsanity.com/paper/2109.11328/) (2021)
- [Auditing for Human Expertise](https://mlsanity.com/paper/2306.01646/) (2023)

## Built on by (most cited first, 25 of 25)

- [Conformal Prediction Sets Can Cause Disparate Impact](https://mlsanity.com/paper/2410.01888/) (2024)
- [A Causal Framework for Evaluating Deferring Systems](https://mlsanity.com/paper/2405.18902/) (2024)
- [Controlling Counterfactual Harm in Decision Support Systems Based on Prediction Sets](https://mlsanity.com/paper/2406.06671/) (2024)
- [A No Free Lunch Theorem for Human-AI Collaboration](https://mlsanity.com/paper/2411.15230/) (2024)
- [Towards Human-AI Complementarity in Matching Tasks](https://mlsanity.com/paper/2508.13285/) (2025)
- [Human-AI Collaborative Uncertainty Quantification](https://mlsanity.com/paper/2510.23476/) (2025)
- [Explaining and Improving Information Complementarities in Multi-Agent Decision-making](https://mlsanity.com/paper/2502.06152/) (2025)
- [To Ask or Not to Ask: Learning to Require Human Feedback](https://mlsanity.com/paper/2510.08314/) (2025)
- [Designing Algorithmic Delegates: The Role of Indistinguishability in Human-AI Handoff](https://mlsanity.com/paper/2506.03102/) (2025)
- [You Don't Bring Me Flowers: Mitigating Unwanted Recommendations Through Conformal Risk Control](https://mlsanity.com/paper/2507.16829/) (2025)
- [Narrowing Action Choices with AI Improves Human Sequential Decisions](https://mlsanity.com/paper/2510.16097/) (2025)
- [Multi-Round Human-AI Collaboration with User-Specified Requirements](https://mlsanity.com/paper/2602.17646/) (2026)
- [Conformal Set-based Human-AI Complementarity with Multiple Experts](https://mlsanity.com/paper/2508.06997/) (2025)
- [No Need for Learning to Defer? A Training Free Deferral Framework to Multiple Experts through Conformal Prediction](https://mlsanity.com/paper/2509.12573/) (2025)
- [ComplLLM: Fine-tuning LLMs to Discover Complementary Signals for Decision-making](https://mlsanity.com/paper/2602.19458/) (2026)
- [Beyond Fixed False Discovery Rates: Post-Hoc Conformal Selection with E-Variables](https://mlsanity.com/paper/2604.11305/) (2026)
- [Learning to Decide with AI Assistance under Human-Alignment](https://mlsanity.com/paper/2605.12646/) (2026)
- [Concise and Logically Consistent Conformal Sets for Neuro-Symbolic Concept-Based Models](https://mlsanity.com/paper/2605.18202/) (2026)
- [Strategic Decision Support for AI Agents](https://mlsanity.com/paper/2606.12587/) (2026)
- [Is Uncertainty Quantification a Viable Alternative to Learned Deferral?](https://mlsanity.com/paper/2508.02319/) (2025)
- [2-Step Agent: A Framework for the Interaction of a Decision Maker with AI Decision Support](https://mlsanity.com/paper/2602.21889/) (2026)
- [Overcoming the Incentive Collapse Paradox](https://mlsanity.com/paper/2603.27049/) (2026)
- [Set-Valued Policy Learning](https://mlsanity.com/paper/2605.19830/) (2026)
- [How AI Assistance Affects Human Skill Development: A Study of Learning with Logic Puzzles](https://mlsanity.com/paper/2608.23543/) (2026)
- [Should I stay or should I show? Learning to selectively disclose information](https://mlsanity.com/paper/2609.39818/) (2026)

## Abstract (arXiv)

Decision support systems based on prediction sets have proven to be effective at helping human experts solve classification tasks. Rather than providing single-label predictions, these systems provide sets of label predictions constructed using conformal prediction, namely prediction sets, and ask human experts to predict label values from these sets. In this paper, we first show that the prediction sets constructed using conformal prediction are, in general, suboptimal in terms of average accuracy. Then, we show that the problem of finding the optimal prediction sets under which the human experts achieve the highest average accuracy is NP-hard. More strongly, unless P = NP, we show that the problem is hard to approximate to any factor less than the size of the label set. However, we introduce a simple and efficient greedy algorithm that, for a large class of expert models and non-conformity scores, is guaranteed to find prediction sets that provably offer equal or greater performance than those constructed using conformal prediction. Further, using a simulation study with both synthetic and real expert predictions, we demonstrate that, in practice, our greedy algorithm finds near-optimal prediction sets offering greater performance than conformal prediction.