Multicalibration yields better matchings
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912709444894720 |
|---|---|
| author | Baldeschi, Riccardo Colini Di Gregorio, Simone Fioravanti, Simone Fusco, Federico Guy, Ido Haimovich, Daniel Leonardi, Stefano Linder, Fridolin Perini, Lorenzo Russo, Matteo Tax, Niek |
| author_facet | Baldeschi, Riccardo Colini Di Gregorio, Simone Fioravanti, Simone Fusco, Federico Guy, Ido Haimovich, Daniel Leonardi, Stefano Linder, Fridolin Perini, Lorenzo Russo, Matteo Tax, Niek |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_11413 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multicalibration yields better matchings Baldeschi, Riccardo Colini Di Gregorio, Simone Fioravanti, Simone Fusco, Federico Guy, Ido Haimovich, Daniel Leonardi, Stefano Linder, Fridolin Perini, Lorenzo Russo, Matteo Tax, Niek Machine Learning 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. |
| title | Multicalibration yields better matchings |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2511.11413 |