Multicalibration Yields Better Matchings

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.

Many machine-learning systems first predict uncertain quantities and then pass those predictions to an optimization algorithm, such as one that decides which people, jobs, or resources should be matched. When the predictions are imperfect, the best-looking decision according to the predictor can be worse than a simple rule that compensates for its mistakes. Engineers may add hand-written patches to fix bad cases, but these patches make the system harder to maintain and may fail when data changes. We propose a principled way to adjust the predictions before the optimization step. Our method is based on multicalibration: the idea that a predictor should not be consistently too high or too low on important groups of cases. Here, those groups are chosen to reflect the decisions made by candidate matching rules. We prove that, after this adjustment, running the usual matching algorithm on the new predictions performs almost as well as the best rule from a chosen family applied to the original predictions.