# Outcome Indistinguishability

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

## Key facts

- Cited by 75 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Nov 2020.

## Built on by (most cited first, 30 of 75)

- [Calibrating Predictions to Decisions: A Novel Approach to Multi-Class Calibration](https://mlsanity.com/paper/2107.05719/) (2021)
- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [A Unifying Theory of Distance from Calibration](https://mlsanity.com/paper/2211.16886/) (2022)
- [Performative Prediction: Past and Future](https://mlsanity.com/paper/2310.16608/) (2023)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [Making Decisions under Outcome Performativity](https://mlsanity.com/paper/2210.01745/) (2022)
- [Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration](https://mlsanity.com/paper/2302.06726/) (2023)
- [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023)
- [Simple and near-optimal algorithms for hidden stratification and multi-group learning](https://mlsanity.com/paper/2112.12181/) (2021)
- [An Algorithmic Framework for Bias Bounties](https://mlsanity.com/paper/2201.10408/) (2022)
- [Calibration by Distribution Matching: Trainable Kernel Calibration Metrics](https://mlsanity.com/paper/2310.20211/) (2023)
- [Loss Minimization Yields Multicalibration for Large Neural Networks](https://mlsanity.com/paper/2304.09424/) (2023)
- [Representative Language Generation](https://mlsanity.com/paper/2505.21819/) (2025)
- [HappyMap: A Generalized Multi-calibration Method](https://mlsanity.com/paper/2303.04379/) (2023)
- [When is Multicalibration Post-Processing Necessary?](https://mlsanity.com/paper/2406.06487/) (2024)
- [On Computationally Efficient Multi-Class Calibration](https://mlsanity.com/paper/2402.07821/) (2024)
- [Reconciling Individual Probability Forecasts](https://mlsanity.com/paper/2209.01687/) (2022)
- [Multicalibrated Regression for Downstream Fairness](https://mlsanity.com/paper/2209.07312/) (2022)
- [Omnipredictors for Constrained Optimization](https://mlsanity.com/paper/2209.07463/) (2022)
- [From Pseudorandomness to Multi-Group Fairness and Back](https://mlsanity.com/paper/2301.08837/) (2023)
- [Fair Risk Control: A Generalized Framework for Calibrating Multi-group Fairness Risks](https://mlsanity.com/paper/2405.02225/) (2024)
- [Avoiding Obfuscation with Prover-Estimator Debate](https://mlsanity.com/paper/2506.13609/) (2025)
- [Optimal Multi-Distribution Learning](https://mlsanity.com/paper/2312.05134/) (2023)
- [Human Expertise in Algorithmic Prediction](https://mlsanity.com/paper/2402.00793/) (2024)
- [Revisiting the Predictability of Performative, Social Events](https://mlsanity.com/paper/2503.11713/) (2025)
- [Multicalibrated Partitions for Importance Weights](https://mlsanity.com/paper/2103.05853/) (2021)
- [Testing Calibration in Nearly-Linear Time](https://mlsanity.com/paper/2402.13187/) (2024)

## Abstract (arXiv)

Prediction algorithms assign numbers to individuals that are popularly understood as individual "probabilities" -- what is the probability of 5-year survival after cancer diagnosis? -- and which increasingly form the basis for life-altering decisions. Drawing on an understanding of computational indistinguishability developed in complexity theory and cryptography, we introduce Outcome Indistinguishability. Predictors that are Outcome Indistinguishable yield a generative model for outcomes that cannot be efficiently refuted on the basis of the real-life observations produced by Nature. We investigate a hierarchy of Outcome Indistinguishability definitions, whose stringency increases with the degree to which distinguishers may access the predictor in question. Our findings reveal that Outcome Indistinguishability behaves qualitatively differently than previously studied notions of indistinguishability. First, we provide constructions at all levels of the hierarchy. Then, leveraging recently-developed machinery for proving average-case fine-grained hardness, we obtain lower bounds on the complexity of the more stringent forms of Outcome Indistinguishability. This hardness result provides the first scientific grounds for the political argument that, when inspecting algorithmic risk prediction instruments, auditors should be granted oracle access to the algorithm, not simply historical predictions.