Multicalibration Yields Better Matchings

Riccardo Colini Baldeschi, Simone Di Gregorio, Simone Fioravanti, Federico Fusco, Ido Guy, Daniel Haimovich, Stefano Leonardi, Fridolin Linder, Lorenzo Perini, Matteo Russo, Cem Sirin, Niek Tax
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:21230-21240, 2026.

Abstract

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 $\gamma$ of the edge-weights, we show how to construct a specific multicalibrated predictor $\hat \gamma$, with the following property. Picking the best matching based on the output of $\hat \gamma$ is competitive with the best decision rule in $\mathcal C$ applied onto the original predictor $\gamma$. We complement this result by providing sample complexity bounds, and by performing numerical experiments.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-colini-baldeschi26a, title = {Multicalibration Yields Better Matchings}, author = {Colini Baldeschi, Riccardo and Gregorio, Simone Di and Fioravanti, Simone and Fusco, Federico and Guy, Ido and Haimovich, Daniel and Leonardi, Stefano and Linder, Fridolin and Perini, Lorenzo and Russo, Matteo and Sirin, Cem and Tax, Niek}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {21230--21240}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/colini-baldeschi26a/colini-baldeschi26a.pdf}, url = {https://proceedings.mlr.press/v306/colini-baldeschi26a.html}, abstract = {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 $\gamma$ of the edge-weights, we show how to construct a specific multicalibrated predictor $\hat \gamma$, with the following property. Picking the best matching based on the output of $\hat \gamma$ is competitive with the best decision rule in $\mathcal C$ applied onto the original predictor $\gamma$. We complement this result by providing sample complexity bounds, and by performing numerical experiments.} }
Endnote
%0 Conference Paper %T Multicalibration Yields Better Matchings %A Riccardo Colini Baldeschi %A Simone Di Gregorio %A Simone Fioravanti %A Federico Fusco %A Ido Guy %A Daniel Haimovich %A Stefano Leonardi %A Fridolin Linder %A Lorenzo Perini %A Matteo Russo %A Cem Sirin %A Niek Tax %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-colini-baldeschi26a %I PMLR %P 21230--21240 %U https://proceedings.mlr.press/v306/colini-baldeschi26a.html %V 306 %X 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 $\gamma$ of the edge-weights, we show how to construct a specific multicalibrated predictor $\hat \gamma$, with the following property. Picking the best matching based on the output of $\hat \gamma$ is competitive with the best decision rule in $\mathcal C$ applied onto the original predictor $\gamma$. We complement this result by providing sample complexity bounds, and by performing numerical experiments.
APA
Colini Baldeschi, R., Gregorio, S.D., Fioravanti, S., Fusco, F., Guy, I., Haimovich, D., Leonardi, S., Linder, F., Perini, L., Russo, M., Sirin, C. & Tax, N.. (2026). Multicalibration Yields Better Matchings. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:21230-21240 Available from https://proceedings.mlr.press/v306/colini-baldeschi26a.html.

Related Material