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

Multicalibration Yields Better Matchings / Colini Baldeschi, R., Di Gregorio, S., Fioravanti, S., Fusco, F., Guy, I., Haimovich, D., Leonardi, S., Linder, F., Perini, L., Russo, M., Sirin, C., Tax, N.. - 306:(2026), pp. 21230-21240. (43rd International Conference on Machine Learning (ICML 2026) Seoul, South Korea ).

Multicalibration Yields Better Matchings

Colini Baldeschi, Riccardo;Di Gregorio, Simone;Fioravanti, Simone;Fusco, Federico;Leonardi, Stefano;Sirin, Cem;
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 C and any predictor gamma of the edge-weights, we show how to construct a specific multicalibrated predictor gamma-hat, with the following property. Picking the best matching based on the output of gamma-hat is competitive with the best decision rule in C applied onto the original predictor gamma. We complement this result by providing sample complexity bounds, and by performing numerical experiments.
2026
43rd International Conference on Machine Learning (ICML 2026)
multicalibration; matching; predict-then-optimize; decision-focused learning
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Multicalibration Yields Better Matchings / Colini Baldeschi, R., Di Gregorio, S., Fioravanti, S., Fusco, F., Guy, I., Haimovich, D., Leonardi, S., Linder, F., Perini, L., Russo, M., Sirin, C., Tax, N.. - 306:(2026), pp. 21230-21240. (43rd International Conference on Machine Learning (ICML 2026) Seoul, South Korea ).
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1782025
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact