📊 statistics

Optimal Transport under Group Fairness Constraints

本文为最优传输引入了一种新颖的群体公平性概念，并提出了高效的计算方法，包括一种改进的 Sinkhorn 算法和两种具有理论保证的松弛策略，以平衡公平性约束与匹配质量。

原作者： Linus Bleistein, Mathieu Dagréou, Francisco Andrade, Thomas Boudou, Aurélien Bellet

发布于 2026-06-04

📖 1 分钟阅读☕ 轻松阅读

原作者： Linus Bleistein, Mathieu Dagréou, Francisco Andrade, Thomas Boudou, Aurélien Bellet

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一位大型活动的配对专家。你手头有两组人：申请人（比如正在寻找学校的学生）和职位（比如学校本身）。你的任务是将他们进行配对。

在数学世界中，这种配对过程被称为最优传输（Optimal Transport）。这就像是一个快递服务，试图将包裹从仓库运送到客户手中。目标通常是尽可能地降低“成本”——也就是说，最小化特定申请人与特定职位之间的“距离”或“成本”。

问题：“强者愈强”的陷阱
论文指出，标准匹配算法存在一个缺陷。如果富裕的学生倾向于住在精英学校附近，而贫困的学生倾向于住在资源匮乏的学校附近，那么标准的“最短路径”算法自然会将富裕的学生与精英学校配对，将贫困的学生与资源匮乏的学校配对。这很高效，但并不公平。它强化了现有的社会分层。

解决方案：一套新的规则书
作者提出了一种运行这场配对游戏的新方法，称为群体公平（Group Fairness）。与其只关注人与人之间的距离，他们引入了一个“公平目标”。

想象一下，一位中央规划者（如政府或教育局）递给你一份严格的指令单：

“无论他们住在哪里，我们都希望 60% 的低收入学生能与精英学校匹配在一起。”

这把问题从“寻找最便宜的路径”转变为“寻找一条既便宜又符合特定的人员匹配图谱的路径”。

三种策略
论文探讨了解决这个难题的三种方法：

“完美公平”算法 (FairSinkhorn)：
这就像一位严格的裁判，确保最终的匹配名单完全符合指令单上的数字。它运作得非常完美，但论文指出，其代价可能非常高昂。这就像强迫一辆货车为了把包裹送到特定社区而绕远路，即使原本有一条直达路线。其“成本”（效率）会显著上升。
“惩罚”法：
由于实现完美公平可能过于昂贵，作者建议采用一种更温和的方法。他们在系统中加入了一项“罚款”。
- 类比： 想象你在开车。你想快速到达目的地（低成本），但你也想遵守交通规则（公平）。与其面对一名严厉的警察随时拦下你，不如约定：如果你超速，就支付罚款。你偏离公平原则（超速）得越多，罚款就越高。
- 这使得系统能够找到一个“平衡点”，即在保持基本公平的同时，不会产生过高的成本。论文在数学上证明，即使在数据有限的情况下，这种方法也是稳定且可靠的。
“成本学习”法：
这是最具有创意的一种策略。该系统不再强行规定匹配必须公平，而是学习如何改变地图本身。
- 类比： 想象快递司机正在使用 GPS。标准的 GPS 会说：“走高速公路，这是最快的。”但高速公路会导致不公平的结果。于是，这个新系统重新编写了 GPS 程序。它学会了让“不公平”的路线看起来很昂贵，而让“公平”的路线看起来很便宜。
- 一旦 GPS 被重新编程，你就可以将其应用于任何新的司机群体，而无需每次都重新计算规则。论文表明，这种“重新编程后的地图”对于原本不在训练组中的新人群同样有效。

研究发现

权衡： 你无法同时拥有最便宜的匹配和完美的公平。你必须选择你愿意为“公平”支付多少“成本”。
可重用性： “成本学习”法在速度上胜出。一旦你学习到了这张“新地图”，就可以立即将其应用于新数据，而其他方法则需要每次都进行繁重的重新计算。
现实测试： 他们在模拟数据（如学生与学校）和一个半真实数据集（如社交/约会应用）上进行了测试。在约会应用的场景中，他们尝试确保不同收入水平的人都有公平的机会进行匹配，而不是仅仅让收入水平相近的人互相匹配。

简而言之
这篇论文为修复不公平的匹配系统提供了一个工具包。它提供了一种方式来告诉算法：“不要只追求效率，也要追求公平。”并且提供了三种不同的实现方式：一种是严格但昂贵的，一种是平衡成本与公平的，还有一种是通过学习一套新规则，使公平成为一种自然的结果。

技术摘要：具有群体公平性约束的最优传输

1. 问题陈述

本文探讨了在算法匹配机制中确保**群体公平性（group fairness）**所面临的挑战。这些机制越来越多地被用于分配稀缺资源（例如，工作岗位、学校录取或肾脏交换）。虽然标准的最优传输（Optimal Transport, OT）提供了一个基于特征相似性在两个分布之间进行匹配的强大框架，但如果特征与敏感属性（如社会经济地位或种族）相关，它可能会在无意中强化或放大现有的差异。

作者为 OT 定义了一种全新的群体公平性概念。不同于以往关注个体公平性或特定约束（如最低参与度）的研究，这种方法允许中央规划者指定一个公平性目标矩阵 $F$ 。该矩阵定义了源人口中任何群体 $s$ 与目标人口中任何群体 $w$ 进行匹配的期望概率。其目标是寻找一个既能最小化传输成本，又能满足这些显式组间质量约束的 OT 平面。

2. 方法论

论文提出了一系列解决该问题的层次化方法，涵盖了从精确约束到松弛表述的多种方案。

2.1. 精确公平性：FairSinkhorn

对于需要严格遵守公平性目标的场景，作者定义了 $F$ -公平最优传输问题。这涉及在满足线性约束的情况下最小化熵正则化 OT 目标函数，其中群体 $(s, w)$ 之间的边际质量必须等于 $F_{sw}$ 。

算法： 他们推导出了一个改进的 Sinkhorn 算法，称为 FairSinkhorn。通过分析对偶形式，他们证明了该解保留了标准 Sinkhorn 迭代的乘性结构，但增加了一个额外的投影步骤以强制执行组级约束。
理论保证： 在测度具有紧支撑的假设下，他们证明了公平 OT 平面的存在性和唯一性。

2.2. 近似公平策略

考虑到精确公平可能会显著降低匹配质量（即“公平的代价”），作者提出了两种松弛策略：

A. 受惩罚的 OT (Fairness-Penalized OT)

这种方法将公平性违规项作为惩罚项纳入目标函数中：
$\min_{\Pi} \text{Tr}[\Pi^\top C] + \varepsilon \text{KL}(\Pi) + \lambda L_F(\Pi)$
其中 $L_F(\Pi)$ 是实际群体匹配概率与目标 $F$ 之间的平方误差， $\lambda$ 控制权衡比例。

优化： 该问题保持凸性。它通过使用广义条件梯度算法来求解，在该算法中，每次迭代都会将公平性惩罚项线性化，并通过标准的 Sinkhorn 算法求解一个带有修改后成本的熵正则化 OT 子问题。
样本复杂度： 作者为该惩罚问题推导出了一个新的有限样本复杂度界限。他们证明了估计误差按 $O(n^{-1/2})$ 缩放，与标准熵正则化 OT 一致，这意味着添加公平性惩罚并不会降低统计效率。

B. 通过双层优化学习成本 (Cost Learning via Bilevel Optimization)

该策略学习一个基准成本函数 $c_\theta$ ，使得生成的 OT 平面能够自然地满足公平性目标。

形式化： 提出了一个双层优化问题，其中外层循环针对成本参数 $\theta$ 最小化公平性损失 $L_F(\Pi_\varepsilon(c_\theta))$ ，内层循环则在固定成本下求解 OT 问题。
参数化： 成本函数可以被参数化为马哈拉诺比斯距离（特征的线性变换）或通过神经网络（非线性嵌入）进行表示。
泛化性： 其核心优势在于可重用性；一旦学习到 $c_\theta$ ，即可使用标准 OT 将其应用于新的、未见过的样本，而无需重新优化。
理论保证： 作者建立了总体解与有限样本近似解之间偏差的一致界限，该界限适用于参数化族中的任何成本。该界限取决于样本量和成本函数的有界性。

3. 核心贡献

新颖的公平性定义： 引入了一种灵活的、基于目标的 OT 群体公平性定义，允许规划者指定任意的组间匹配概率。
算法实现：
- FairSinkhorn： 一个用于求解精确公平 OT 平面的求解器。
- 受惩罚的 OT： 一种凸松弛方法，允许在成本与公平性之间进行可调权衡。
- 成本学习： 一个双层优化框架，用于学习能诱导公平匹配的成本，从而实现泛化。
理论分析：
- 证明了精确公平 OT 的存在性与唯一性。
- 推导了惩罚型熵正则化 OT 的样本复杂度界限（显示出 $O(n^{-1/2})$ 的收敛性）。
- 推导了成本学习方法的一致偏差界限，保证了在未见数据上的公平性。
实证验证： 通过在合成数据（高斯混合模型和圆形分布）以及半合成约会应用数据集上的实验，验证了这些方法的有效性及成本与公平性之间的权衡。

4. 结果

权衡控制： 惩罚方法成功地在 vanilla OT（低成本、高不公平）和 FairSinkhorn（完美公平、高成本）之间进行了插值，允许通过惩罚参数 $\lambda$ 进行精细化控制。
几何敏感性： 在合成数据集上，当数据几何结构复杂时（例如圆形分布），惩罚型 OT 通常比成本学习获得更好的成本-公平性权衡，因为惩罚型 OT 对传输映射没有结构性限制。然而，使用神经网络的成本学习可以逼近线性（马哈拉比斯）成本无法处理的复杂目标。
泛化能力： 在“可重用性”实验中，学习到的成本（无论是马哈拉诺比斯还是 MLP）在新的测试样本上保持了与训练性能相当的公平水平，显著优于 vanilla OT。应用学习成本的推理时间明显低于为每个新批次求解新的惩罚型 OT 问题。
现实应用： 在约会应用数据集（高维、多群体）上，这些方法重现了在合成设置中观察到的凸成本-公平性权衡，验证了其在复杂现实场景中的适用性。

5. 意义与主张

本文声称为监管机构和市场设计者提供了一个原则性的框架，用于在匹配机制中执行公平性目标。通过将公平性构架为组间的显式质量约束，这项工作弥合了理论最优传输与实际政策需求（如配额、多样性目标）之间的鸿沟。

作者强调，其工作：

提供了一种灵活的公平性定义，可以适应各种立法或政治目标（例如“五分之四原则”或多样性配额）。
提供了理论保证，涵盖了惩罚型方法的统计效率以及成本学习方法的泛化能力。
强调了权衡关系，即效率（传输成本）与公平性之间的权衡，并证明虽然精确公平是可能的，但松弛方法通常能提供更实际的平衡。

论文最后指出了一些局限性：当前框架侧重于群体公平性，并未直接扩展到个体公平性。此外，尽管这些方法优化了匹配过程，但作者也承认，公平性目标的本身设计是一个属于算法范围之外的政治与伦理决策。未来的研究方向包括探索个体公平性、对公平-偏差权衡进行更深入的分析，以及建模匹配对个体结果的下游影响。