# Multicalibration Yields Better Matchings

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 20 references that are in the map.
- First posted on arXiv 14 Nov 2025.

## Builds on (most cited first, 14 of 14)

- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Machine Learning with a Reject Option: A survey](https://mlsanity.com/paper/2107.11277/) (2021)
- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Calibrating Predictions to Decisions: A Novel Approach to Multi-Class Calibration](https://mlsanity.com/paper/2107.05719/) (2021)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Moment Multicalibration for Uncertainty Estimation](https://mlsanity.com/paper/2008.08037/) (2020)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023)
- [Loss Minimization Yields Multicalibration for Large Neural Networks](https://mlsanity.com/paper/2304.09424/) (2023)
- [Complexity-Theoretic Implications of Multicalibration](https://mlsanity.com/paper/2312.17223/) (2023)
- [Robust Decision Making with Partially Calibrated Forecasts](https://mlsanity.com/paper/2510.23471/) (2025)

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

- [Divide et Calibra: Multiclass Local Calibration via Vector Quantization](https://mlsanity.com/paper/2605.21060/) (2026)
- [A CaLLM Judge is a Better Judge: Mitigating Bias in LLM-as-a-judge](https://mlsanity.com/paper/2610.18108/) (2026)

## Abstract (arXiv)

Consider the problem of finding the best matching in a weighted graph where we only have access to predictions of the actual stochastic weights, based on an underlying context. If the predictor is the Bayes optimal one, then computing the best matching based on the predicted weights is optimal. However, in practice, this perfect information scenario is not realistic. Given an imperfect predictor, a suboptimal decision rule may compensate for the induced error and thus outperform the standard optimal rule. In this paper, we propose multicalibration as a way to address this problem. This fairness notion requires a predictor to be unbiased on each element of a family of protected sets of contexts. Given a class of matching algorithms mathcal C and any predictor γ of the edge-weights, we show how to construct a specific multicalibrated predictor hat γ, with the following property. Picking the best matching based on the output of hat γ is competitive with the best decision rule in mathcal C applied onto the original predictor γ. We complement this result by providing sample complexity bounds, and by performing numerical experiments.