Optimal Transport under Group Fairness Constraints¶

会议: ICML 2026
arXiv: 2601.07144
代码: https://github.com/LinusBleistein/fair_ot (有)
领域: AI安全 / 算法公平性 / 最优传输
关键词: 群体公平性、最优传输、Sinkhorn、双层优化、成本学习

一句话总结¶

本文把"群体公平性"显式编码为一个 \(K_s \times K_w\) 的组间匹配概率目标 \(\mathbf{F}\)，提出 FairSinkhorn 精确求解、惩罚式 OT 凸松弛、以及 双层成本学习 三种方案，分别给出有限样本复杂度 \(O(1/\sqrt{n})\) 和 fairness 偏差界 \(O(\exp(5R_\Theta/\varepsilon)/\sqrt{n})\)，在合成与半合成（约会 app）数据集上勾画出"代价 - 公平性"权衡前沿。

研究背景与动机¶

领域现状：算法匹配（招生、招聘、约会、肾移植、城市资源分配）越来越多地由中心化算法决定，最优传输（OT）因其在经济学和社会科学中的良好建模性质成为主流工具。给定两个分布 \(\mu, \eta\) 和成本 \(c\)，熵正则化 OT 求解 \(\min_\pi \int c(x,y)\,d\pi + \varepsilon \mathbf{KL}(\pi|\mu\otimes\eta)\)，并用 Sinkhorn 算法高效迭代。

现有痛点：当特征 \(X, Y\) 与敏感属性 \(S, W\)（性别、种族、社会经济地位）强相关时，标准 OT 会产出"块对角"式高度同质的匹配——例如把高收入学生几乎全部分配到精英学校。已有 fairness × matching 文献几乎集中在个体公平（相似个体得相似结果）或特定问题的参与配额（肾移植 KPD），缺乏一个针对 OT 本身、可由中央规划者灵活指定的"组间匹配概率"框架。

核心矛盾：(a) 现有 fair-OT 工作大多把 OT 当作下游公平预测的工具（如 Wasserstein 重心投影），而不是研究传输计划本身的公平性；(b) 精确公平往往代价巨大（"price of fairness"），需要一个能精细控制 trade-off 的松弛框架；(c) 把公平目标"印"进匹配里之后，能否在新样本上复用也是开放问题。

本文目标：(1) 形式化"组间匹配概率 = 目标 \(\mathbf{F}\)"这一新型群体公平定义；(2) 给出精确解算法 + 两类松弛方法；(3) 给松弛方法配套有限样本理论保证。

切入角度：观察到公平约束 \(\pi_{SW}(s,w) = \mathbf{F}_{sw}\) 在传输计划 \(\mathbf{\Pi}\) 上是线性的，因此 Lagrange 对偶仍可写成 Sinkhorn 风格的乘性形式；同时熵正则保证唯一性与可微性，让"通过学成本来诱导公平"的双层优化变成良定问题。

核心 idea：用一个"组间概率目标矩阵 \(\mathbf{F}\)"统一表达限制同源婚配、最低少数族裔配额、4/5 雇佣规则、欧盟董事会 40% 性别配额等真实规则，并提供从精确到松弛的算法谱系。

方法详解¶

整体框架¶

输入：两份带敏感属性的样本 \((\mathbf{x}_i, \mathbf{s}_i)_{i=1}^n \sim \mu\)、\((\mathbf{y}_j, \mathbf{w}_j)_{j=1}^m \sim \eta\)，成本矩阵 \(\mathbf{C}_{ij} = c(\mathbf{x}_i, \mathbf{y}_j)\)，熵正则 \(\varepsilon\)，公平目标 \(\mathbf{F} \in \Pi(\mathbf{p}, \mathbf{q})\)（满足边际等于敏感属性分布）。

输出：传输计划 \(\mathbf{\Pi} \in \mathbb{R}_+^{n\times m}\)，行列和分别为 \(1/n \cdot \mathbf{1}_n\)、\(1/m \cdot \mathbf{1}_m\)，并使组间质量 \(\sum_{i: s_i=s, j: w_j=w} \mathbf{\Pi}_{ij}\) 尽量接近 \(\mathbf{F}_{sw}\)。

三条求解路径形成一个谱系：FairSinkhorn（精确 = 硬约束）→ Penalized OT（直接惩罚 = 凸松弛）→ Cost Learning（间接重塑几何 = 可复用的双层优化）。

关键设计¶

FairSinkhorn：在 Sinkhorn 里多一步"组级再投影"
- 功能：在熵正则 OT 上加入精确组间约束 \(\text{Tr}[\mathbf{\Pi}^\top \mathbf{B}_{sw}] = \mathbf{F}_{sw}\)，其中 \(\mathbf{B}_{sw}\) 是指示样本组对的 0/1 矩阵。
- 核心思路：把 Lagrange 对偶变量 \(\mathbf{h} \in \mathbb{R}^{K_s \times K_w}\) 引入后，最优解形如 \(\mathbf{\Pi} = \text{diag}(e^{\mathbf{f}/\varepsilon})(\mathbf{K} \odot \mathbf{H}) \text{diag}(e^{\mathbf{g}/\varepsilon})\)，其中 \(\mathbf{K} = e^{-\mathbf{C}/\varepsilon-1}\) 是标准 Sinkhorn 核，\(\mathbf{H} = \sum_{sw} e^{h_{sw}/\varepsilon} \mathbf{B}_{sw}\) 是一张按 \((s,w)\) 块常值的"公平系数"矩阵。算法在标准的 \(\mathbf{u}, \mathbf{v}\) 行列归一之间，多插入一步 \(\mathbf{L}^{(t+1)} \leftarrow \mathbf{F} \oslash \Phi(\mathbf{u}^{(t+1)}, \mathbf{v}^{(t+1)})\) 来更新 \(\mathbf{H}\)，其中 \(\Phi\) 把当前传输的组级质量加总。
- 设计动机：fairness 约束是线性的，因此可以"嫁接"到 Sinkhorn 的乘性结构上，复杂度与原算法同阶；实验显示收敛速度与原 Sinkhorn 几乎一致。这是论文中"perfect fairness"的基线，但它会强行抹平所有组间几何信息，导致传输成本可能显著上升——这也正是后两种松弛方法的动机。
惩罚式 OT：一个凸的"代价 - 公平性"旋钮
- 功能：用平方惩罚 \(\mathcal{L}_\mathbf{F}(\mathbf{\Pi}) = \sum_{(s,w)} (\text{Tr}[\mathbf{\Pi}^\top \mathbf{B}_{sw}] - \mathbf{F}_{sw})^2 \le \rho\) 替代硬约束，并把它加进目标 \(\min_\mathbf{\Pi} \text{Tr}[\mathbf{\Pi}^\top \mathbf{C}] + \varepsilon \mathbf{KL}(\mathbf{\Pi}) + \lambda \mathcal{L}_\mathbf{F}(\mathbf{\Pi})\)，\(\lambda\) 即"公平强度"旋钮。
- 核心思路：因为 \(\mathcal{L}_\mathbf{F}\) 是凸的，整体仍强凸、唯一解。求解用广义条件梯度：在每次迭代把惩罚项围绕当前 \(\mathbf{\Pi}^t\) 线性化，得到修正成本 \(\mathbf{C} + \nabla \mathcal{L}_\mathbf{F}(\mathbf{\Pi}^t)\)，再用标准 Sinkhorn 解这个子问题作为搜索方向，最后线搜索取凸组合，保证下降。理论上，作者证明 \(\mathbb{E}|m^\star(\mu_n, \eta_n) - m^\star(\mu, \eta)| \lesssim 1/\sqrt{n}\)，与标准熵正则 OT 同阶——即加 fairness 惩罚不损失统计效率。证明用"夹逼"：把样本最优值 \(m_n^\star\) 夹在两个对线性化子问题求值的随机量之间，再调用 rakotomamonjy2015 / genevay2019 / rigollet2022 的工具链。
- 设计动机：精确公平太硬，但很多场景只需"接近"公平即可。\(\lambda\) 让 \(\mathbf{\Pi}\) 沿一条凸曲线在 Sinkhorn（\(\lambda=0\)）与 FairSinkhorn（\(\lambda\to\infty\)）之间平滑移动，规划者可根据可接受代价就地选点；并且因为是凸问题，结果可复现、可解释。
双层成本学习：学一个"诱导公平"的几何
- 功能：不直接修改 \(\mathbf{\Pi}\)，而是学一个参数化成本 \(c_\theta\)，使得它诱导的熵正则 OT 解 \(\mathbf{\Pi}_\varepsilon(c_\theta)\) 自然满足公平目标。
- 核心思路：写成双层优化 \(\min_\theta \mathcal{L}_\mathbf{F}(\mathbf{\Pi}_\varepsilon(c_\theta)) + \frac{1}{\lambda} \mathscr{D}(c_\theta, c_\text{base})\) s.t. \(\mathbf{\Pi}_\varepsilon(c_\theta) = \arg\min_\mathbf{\Pi} \text{Tr}[\mathbf{\Pi}^\top \mathbf{C}_\theta] + \varepsilon \mathbf{KL}(\mathbf{\Pi})\)，其中 \(\mathscr{D}\) 约束学到的成本不要偏离基准成本（如平方欧氏）太远。内层熵正则 OT 因强凸而有唯一解，因此双层目标良定。两种参数化：Mahalanobis \(c_\mathbf{M}(x,y) = (x-y)^\top \mathbf{M} (x-y)\)（可解释，看哪些特征方向被强调或压制）和神经成本 \(c_\theta(x,y) = \|\phi_{\theta_1}(x) - \phi_{\theta_2}(y)\|_2^2\)（更灵活，能做非线性几何变换）。梯度通过迭代微分或隐式微分得到。理论上，作者证明对参数族任一 \(\theta\)，新样本上的 fairness 偏差满足 \(\sup_\theta \mathbb{E}[|\mathcal{L}_\mathbf{F}(\mathbf{\Pi}_\varepsilon(c_\theta)) - \mathcal{L}_\mathbf{F}(\pi_\varepsilon^\star(c_\theta))|] \lesssim \exp(5R_\Theta/\varepsilon)/\sqrt{n}\)，其中 \(R_\Theta\) 是成本族上界。
- 设计动机：惩罚式 OT 对每批新样本都要重解；而成本学到之后可以缓存、对新数据直接跑标准 OT，省下推理时间并把 fairness 推广到未见样本。此外可解释成本（Mahalanobis）能直接告诉规划者"原始空间的哪些方向是导致不公平的元凶"。

损失函数 / 训练策略¶

精确版（FairSinkhorn）只需迭代 \(T\) 次定点更新，无可学参数。惩罚式 OT 是凸问题，\(\lambda\) 控制 fairness 强度。成本学习版用 SGD/Adam 优化 \(\theta\)，每步内层跑一次熵正则 Sinkhorn；正则化项 \(\mathscr{D}(c_\theta, c_\text{base})\) 用 \(\|\mathbf{M} - \mathbf{I}\|_F^2\) 或网络权重 \(\ell_2\) 范数实现。\(\varepsilon\)、\(\lambda\) 通过 grid 扫描描出 trade-off 曲线。

实验关键数据¶

主实验¶

合成实验：Gaussians（两组学生 / 学校按高斯混合分布生成，privileged 靠近 elite）和 Circles（少数群体在半径 2 圆环上）。目标 \(\mathbf{F} = \begin{bmatrix} 0.20 & 0.30 \\ 0.28 & 0.22 \end{bmatrix}\)，即 60% 弱势学生匹配精英学校。

方法	公平违反 \(\mathcal{L}_\mathbf{F}\)	传输代价（相对 Sinkhorn）	备注
Sinkhorn (vanilla)	高（块对角偏差大）	0（基准）	完全忽略公平
Sinkhorn + 调大 \(\varepsilon\)	仍高	上升	仅靠熵正则无法逼近 \(\mathbf{F}\)
FairSinkhorn	\(\approx 0\)（精确）	显著上升	完美公平，代价最高
Penalized OT（变 \(\lambda\)）	平滑插值	平滑插值	凸曲线，trade-off 最灵活
Cost learning - Mahalanobis	中（Circles 上 \(\ge 10^{-2}\)）	中	线性变换不够，受限于几何
Cost learning - MLP	低	中（Gaussians 上与 Penalized 同档）	非线性几何，Circles 上才追得上 Penalized

半合成约会 App 实验：Kaggle 数据集子采样匹配美国人口统计，敏感属性为 7 档收入，feasible matching 由性取向决定。目标 \(\mathbf{F}_{sw} = \mathbb{P}(S=s_i) \mathbb{P}(W=w_j)\)（即独立 = 完全打破收入同源婚配）。结果与合成实验一致：trade-off 曲线呈凸形，Penalized 与 Cost Learning 几乎重合，扩展性良好到高维 + 多组。

消融实验¶

配置	现象	说明
仅调 \(\varepsilon\)（vanilla OT）	公平违反不收敛到 \(\mathbf{F}\)	熵正则只能让 plan 更"模糊"，不会自动趋向 \(\mathbf{F}\)
\(\lambda\) 由小到大（Penalized）	沿 Sinkhorn → FairSinkhorn 的凸曲线	验证了 trade-off 可控且连续
Mahalanobis vs MLP（Cost Learning）	Circles 上 MLP 显著更低	线性几何对环状分布无能为力
Train cost → reuse on test set	推理时间比 Penalized 快 1-2 个数量级，公平损失略增（generalization gap MLP > Mahalanobis）	学到的成本可复用，新样本上 fairness 仍远好于 vanilla OT

关键发现¶

熵正则不能替代公平约束：再大的 \(\varepsilon\) 也不会让 vanilla OT 自动靠近 \(\mathbf{F}\)，证实显式公平机制的必要性。
Penalized 几乎"压倒性"地最灵活：因为它在所有耦合 \(\Pi\) 上搜索，而 Cost Learning 受限于"熵正则 OT 解 + 参数成本族"这一更窄子集；但代价是每批新样本都要重算。
Cost Learning 的核心价值是"可迁移"：学一次、用多次，特别适合实时匹配系统（招聘、约会）；并且 Mahalanobis 矩阵的特征值/向量本身就是公平诊断工具。
理论与实验闭环：Penalized 的 \(O(1/\sqrt{n})\) 和 Cost Learning 的 \(O(\exp(5R_\Theta/\varepsilon)/\sqrt{n})\) 都在实验中被"反向验证"——样本量增大时新样本上的 fairness gap 确实收窄。

亮点与洞察¶

fairness target 这一抽象非常通用：4/5 雇佣规则、欧盟 40% 女性董事配额、法国奖学金最低配额都可以表达成一个 \(\mathbf{F}\)，把法规直接接入算法。这是文中我最欣赏的"概念性贡献"。
公平约束是线性的 → Sinkhorn 加一步就够：FairSinkhorn 的推导异常干净，只在 \(\mathbf{u}, \mathbf{v}\) 之外多维护一个块常值矩阵 \(\mathbf{T}^{(t)}\)，几乎零额外开销，可直接 drop-in 替换现有 OT pipeline。
凸惩罚不损失统计效率：证明加 fairness 惩罚后样本复杂度仍是 \(O(1/\sqrt{n})\)，这一结论对整个"约束 OT"领域都有独立价值。
可迁移的 trick：双层"学成本以诱导某种 plan 性质"的范式可以推广到 fairness 以外——比如把 \(\mathcal{L}_\mathbf{F}\) 换成稀疏性、单调性、域不变性等目标，直接得到一族"约束诱导式 OT"算法。

局限与展望¶

只覆盖群体公平：个体公平（"相似个体得相似匹配"）需要不同形式化，不能简单套用 \(\mathbf{F}\)。
没有讨论 fairness-bias trade-off：当 \(\mathbf{F}\) 本身被 mis-specified 时（规划者对真实人口分布判断错误），三种方法的鲁棒性都未量化。
下游效用未建模：把学生分到大学只是匹配，后续工资 / 学业成就才是真正关心的福利指标；论文把这一步留给未来工作。
复杂度依赖 \(\exp(5R_\Theta/\varepsilon)\)：成本学习的偏差界随 \(\varepsilon\) 减小指数爆炸，所以小正则区间下的泛化保证比较弱；实操上需要在 fairness、cost、\(\varepsilon\) 三角中谨慎调参。
改进思路：(a) 把 \(\mathbf{F}\) 本身做成可学的（让规划者只指定上界 / 不等式约束）；(b) 引入因果图，把 sensitive attribute → feature 的相关性显式建模，得到 counterfactual 版本的公平 OT；(c) 与 stable matching（Gale-Shapley）混合，得到既稳定又群体公平的算法。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 把"组间匹配概率目标 \(\mathbf{F}\)"作为一类全新的公平定义引入 OT，并首次系统给出三种求解路径与对应理论保证
实验充分度: ⭐⭐⭐⭐ 合成 + 半合成（约会 app）覆盖了二维 / 高维、两组 / 七组，trade-off 曲线与可迁移性都得到验证；但缺少真实关键应用（招聘、招生）的端到端 case study
写作质量: ⭐⭐⭐⭐⭐ 故事线（school → fairness target → exact → penalized → cost learning）层层递进，定义、命题、算法、定理交替推进，pacing 几乎完美
价值: ⭐⭐⭐⭐⭐ 给"算法治理 + 配额监管"提供了一个数学清晰、计算高效、可复用的工具箱，监管者、平台和研究者都能受益