用公平性约束提升不完美预测下的匹配质量
Multicalibration Yields Better Matchings
- 引入多校准机制优化权重预测偏差
- 基于校准后预测的匹配性能逼近最优决策规则
- 适用于需公平性保障的匹配场景，如招聘、资源分配
研究在仅能访问基于上下文的权重预测值时，如何找到加权图中的最优匹配。当预测器为贝叶斯最优时，基于预测权重计算的匹配即为最优。但在实际中，预测往往不完美。此时，次优决策规则可能通过补偿预测误差而表现更优。本文提出使用多校准（multicalibration）来解决此问题——该公平性概念要求预测器在各类受保护上下文集合上无偏。对于任意匹配算法类 $\mathcal C$ 和原始预测器 $γ$，我们构造出一个特定的多校准预测器 $\hat γ$，使得基于 $\hat γ$ 输出选择的最优匹配，与在 $γ$ 上应用 $\mathcal C$ 中最佳决策规则的表现相当。我们还提供了样本复杂度界限，并进行了数值实验验证。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。