Beyond the Half Approximation: Fair and Efficient Online Class Matching¶

会议: NeurIPS 2026
arXiv: 2605.23408
领域: 学习理论
关键词: 在线二分匹配, 群体公平性, 类别无嫉妒性, 功利社会福利, 原对偶分析

一句话总结¶

提出了首个基于阈值分阶段分配的在线类别匹配框架，首次打破了强公平性下功利社会福利不超过 1/2 的理论瓶颈，并给出了紧密的公平性代价上界。

研究背景与动机¶

在线二分匹配是网约车派单、在线广告竞价与云资源调度等实时分配系统的基石。在这些系统中，供应端节点预先确定，需求端物品随时间序列到达且必须立即做决策并不可撤销。当代理人自然隶属于不同受保护类别（如不同少数族裔、性别群体或边缘地理区域）时，传统的纯效率最大化算法（如达到 $1-1/e \approx 0.632$ 竞争比极限的经典 RANKING 算法）往往会在边缘群体间造成严重的系统性偏置。为此，近期理论研究提出了「类别无嫉妒性」（Class Envy-Freeness, CEF），要求任意一个类别所得分配的总价值，不低于其从任何其他类别分配包中能提取最大匹配价值的 $\alpha$ 比例。

然而，现有在线类别匹配算法面临极其严峻的效率瓶颈。为了避免算法故意丢弃物品造成运力或曝光浪费，实际算法普遍要求满足「非浪费性」（Non-wastefulness，即只要有未饱和代理对其感兴趣，物品绝不闲置）。虽然非浪费性自然兜底了 $1/2$ 的功利社会福利（Utilitarian Social Welfare, USW），但此前所有能保证常数因子 CEF 的在线算法，其 USW 均被死死卡在 $1/2$ 的天花板上，与无公平约束下的 $1-1/e$ 理论上限相差甚远。学界因此提出了一个悬而未决的核心公开问题：在线类别匹配中，常数级别的群体公平性是否必然强制付出至多 $1/2$ 的效率代价？

本文切入这一理论空白，发现此前算法效率受限的根源在于自始至终采用同一套过度保守的均衡分配逻辑。若能将整个生命周期显式解耦为「公平兜底」与「贪心增益」两个阶段，便能在严格锚定类别公平底线的同时彻底释放后续在线流量的匹配效率。核心 idea：设计以饱和度阈值 $\gamma \in [0, 1]$ 参数化的双阶段分配框架，在各类别达到阈值负载前强制按类均分以保证 CEF 公平性，在跨过阈值后无缝切换为效率优先策略，并在对偶空间构造分段势能函数完成原对偶联合分析。

方法详解¶

整体框架¶

算法围绕阈值参数 $\gamma \in [0, 1]$ 展开，根据匹配形式分别提出面向可分匹配的 EFTT（Equal Filling Till Threshold）算法和面向不可分匹配的 Hybrid Ranking 算法。对于连续到达的在线物品，系统动态维护各代理的当前匹配负载（可分匹配中的分数度数或不可分匹配中的独立随机排序优先级 $\mu_a$）。若存在满意当前物品且尚未达到阈值 $\gamma$ 的代理，系统进入公平均分阶段；一旦所有候选代理均已超过阈值 $\gamma$，系统则转入全局贪心效率最大化阶段。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["在线物品 o 到达<br/>揭示邻域 N(o)"] --> B{"是否存在活跃类别<br/>含感兴趣且度数 &lt; γ 的代理"}
    B -->|是| C["阈值内类别均分分配<br/>各活跃类均摊物品份额并配给最低负载代理"]
    B -->|否| D["跨阈值全局效率最大化<br/>全局贪心匹配度数最低或优先级最优代理"]
    C --> E["对偶势能更新与原对偶分析<br/>按分段核函数 g(z) 分配节点对偶价格"]
    D --> E
    E --> F["输出不可撤销匹配结果"]

关键设计¶

1. 阈值内类别均分分配：在早期生命周期建立跨类别公平防护网

为了抵御对抗式输入在初期制造的结构性偏置，算法在代理负载达到阈值 $\gamma$ 前实施严格的保护性均分。在可分匹配（EFTT）中，定义集合 $Z_\gamma$ 为所有包含「对当前物品 $o$ 感兴趣且当前分数度数小于 $\gamma$ 的代理」的类别集合。只要 $Z_\gamma$ 非空且物品 $o$ 仍有剩余未分配质量，算法便将 $o$ 的分配速率严格均分给 $Z_\gamma$ 中的每一个类别；在每个类别内部，物品质量流向该类中度数最小的候选代理。在不可分匹配（Hybrid Ranking）中，每个代理 $a$ 独立均匀采样随机标号 $\mu_a \sim [0, 1]$，将 $\mu_a \le \gamma$ 的代理划入优先保护集合 $N'$；若到达物品 $o$ 在 $N'$ 中存在可匹配代理，则在其涵盖的类别集合中均匀随机抽取一个类别，并匹配给该类中首个未匹配代理。这一机制切断了早期资源被单一优势群体完全吞噬的可能性，为可分匹配提供了 $1 - e^{-\gamma}$ 的 CEF 理论下界，为不可分匹配提供了 $\gamma/2$ 的 CEF 理论下界。

2. 跨阈值全局效率最大化：在公平达标后全力释放竞争比增益

一旦所有对物品 $o$ 感兴趣的代理在其所属类别中均已达到或超过阈值 $\gamma$（即 $Z_\gamma = \emptyset$ 或不可分匹配中 $N'$ 内无可用代理），公平阶段正式退出，算法立即转入无约束的效率捕获模式。在 EFTT 中，系统采用标准注水法（Water-Filling），直接将物品 $o$ 的剩余质量连续分配给所有候选代理中分数度数最小的个体，彻底打破类别界限；在 Hybrid Ranking 中，则匹配给未饱和集合 $N \setminus N'$ 中拥有最小随机标号 $\mu_a$ 的代理。该设计确保了算法在全流程保持非浪费性（maximal matching），同时利用后半程的无拘束贪心极大地挽回了早期均分带来的社会福利损失，使整体竞争比打破 $1/2$ 壁垒。

3. 对偶势能函数与原对偶联合分析：统一刻画福利与公平的权衡曲面

传统竞争分析通常将公平性与社会福利分开求界，难以穿透二者的内在耦合。本文构造了一个以 $\gamma$ 为分界点的非降对偶势能函数 $g(z)$： $$g(z) = \begin{cases} \frac{\exp(\gamma - 1)}{\gamma + 1}, & z \le \gamma \\ \exp(z - 1), & z > \gamma \end{cases}$$ 在每次分配边 $e=(o, a)$ 增量速率为 $r$ 时，向代理节点注入对偶变量速率 $g(\text{deg}(a)) \cdot r$，向物品节点注入 $(1 - g(\text{deg}(a))) \cdot r$。通过积分验证，对于图中任意一条边 $e=(o,a)$，无论最终该边两端节点的饱和状态落入哪种区间，节点对偶变量之和均严格满足： $$y_o + y_a \ge 1 - \frac{e^{\gamma - 1}}{\gamma + 1}$$ 由此利用弱对偶定理直接确立了算法达到 $1 - \frac{e^{\gamma - 1}}{\gamma + 1}$ 的 USW 竞争比。

4. 紧致的对抗构造：纠正历史松弛并确立公平性代价理论极限

为了探究任意非浪费算法在满足 $\alpha$-CEF 下所能达到的社会福利极限，作者设计了一个双阶段对抗图构造：第一阶段引入 $p(k-1)+q$ 个全连接物品，强迫任何 $\alpha$-CEF 算法必须向 $k-1$ 个小类别分配足够多的配额；第二阶段针对这 $k-1$ 个小类别分别独立输入大小为 $q$ 的经典上三角对抗子图（Karp-Vazirani-Vazirani 构造）。通过求解极小化对抗收益的对偶线性规划并令类数 $k \to \infty$ 与 $q \to \infty$，证明了任何非浪费 $\alpha$-CEF 算法的 USW 竞争比严格无法超过： $$\text{USW} \le \frac{1 + \alpha - e^{\alpha - 1}}{1 + \alpha}$$ 这一结果彻底修正了 Hajiaghayi 等人在 2023 年给出的 $1/(1+\alpha)$ 上界在 $\alpha \le 1/(e-1) \approx 0.58$ 时大于无约束理论上限 $1-1/e \approx 0.632$ 的失效缺陷。

实验关键数据¶

主实验¶

论文对所提出的 EFTT 算法（可分匹配）、Hybrid Ranking 算法（不可分匹配）与理论上界在不同参数下的保证进行了全面解析与对比，主结果对比如下表所示：

设置 / 机制	阈值参数 $\gamma$	CEF 公平性保证	USW 社会福利竞争比	理论上限 (UB)	相比基线突破
经典无约束 (RANKING / Water-filling)	$\gamma = 0$	$0.0000$	$1 - 1/e \approx 0.6321$	$0.6321$	纯效率基线 (无公平保证)
历史公平基线 (Hosseini et al. / Hajiaghayi et al.)	-	$1 - 1/e \approx 0.6321$ (Div) / $0.5000$ (Indiv)	$\le 0.5000$	$1.0000$ (无效界)	受限于非浪费性 1/2 壁垒
EFTT (Divisible, 本文)	$\gamma = 0.5000$	$1 - e^{-0.5} \approx 0.3935$	$1 - \frac{e^{-0.5}}{1.5} \approx 0.5956$	$0.6133$	突破 1/2 (+19.1% 相对福利增益)
EFTT (Divisible, 本文平衡点)	$\gamma = 0.7915$	$0.5468$	$0.5468$	$0.5750$	同时实现 >0.54 的 CEF 与 USW
EFTT (Divisible, 强公平)	$\gamma = 1.0000$	$1 - 1/e \approx 0.6321$	$0.5000$	$0.5000$	达到最优 CEF 并匹配理论上限
Hybrid Ranking (Indivisible, 本文)	$\gamma = 0.5000$	$0.2500$	$0.5956$	$0.6133$	离散下突破 1/2 效率界
Hybrid Ranking (Indivisible, 本文平衡点)	$\gamma = 0.7024$	$0.3512$	$0.5645$	$0.5891$	离散匹配下高福利与强公平兼备
Hybrid Ranking (Indivisible, 强公平)	$\gamma = 1.0000$	$0.5000$	$0.5000$	$0.5000$	离散下达到最大可能 1/2 CEF

消融实验¶

下表给出了阈值参数 $\gamma$ 在区间 $[0, 1]$ 内连续变动时，可分匹配与不可分匹配各项指标的单调演化轨迹：

参数 $\gamma$	可分 CEF ($1 - e^{-\gamma}$)	不可分 CEF ($\gamma / 2$)	共同 USW 保证 ($1 - \frac{e^{\gamma-1}}{\gamma+1}$)	新推导理论上限 ($\frac{1+\alpha-e^{\alpha-1}}{1+\alpha}$)	旧上限对比 ($1/(1+\alpha)$)
$0.00$	$0.0000$	$0.0000$	$0.6321$ ($1 - 1/e$)	$0.6321$	$1.0000$ (平凡界)
$0.20$	$0.1813$	$0.1000$	$0.6272$	$0.6288$	$0.8465$ (远高于真实值)
$0.40$	$0.3297$	$0.2000$	$0.6133$	$0.6191$	$0.7520$ (松弛过大)
$0.60$	$0.4512$	$0.3000$	$0.5886$	$0.5985$	$0.6891$ (仍超过无约束界)
$0.80$	$0.5507$	$0.4000$	$0.5447$	$0.5592$	$0.6448$ (开始有意义)
$1.00$	$0.6321$	$0.5000$	$0.5000$	$0.5000$	$0.5000$ (仅在端点收敛)

关键发现¶

打破半数效率魔咒：无论是可分匹配还是不可分匹配，只要设定 $\gamma \in (0, 1)$，算法均能在保有可观常数 CEF 保证的同时，严格超越 $1/2$ 的 USW 竞争比。例如在 $\gamma = 0.7915$ 时，可分匹配达到了 $0.5468$-CEF 和 $0.5468$-USW，终结了长期以来关于公平性是否必然将社会福利拉低至 $0.5$ 以下的争论。
理论上下界近乎闭合：新构造的理论上限曲线在整个 $\alpha \in [0, 1]$ 区间内高度贴合 EFTT 算法的表现，在 $\alpha \to 0$ 时精确渐近回落到无公平约束的 $1 - 1/e$，在 $\alpha \to 1$ 时收敛至非浪费极限 $0.5$，使得在线类别匹配的「公平性代价」（Price of Fairness）首次得到了实质性的定量刻画。
不可分性带来的公平折损：在不可分匹配中，受限于单项物品无法切分的离散性，Hybrid Ranking 的 CEF 保证为 $\gamma/2$，低于可分情况下的 $1 - e^{-\gamma}$，但其社会福利竞争比与可分情形完全一致。

亮点与洞察¶

阈值解耦机制：采用两阶段策略，在负载达到阈值 $\gamma$ 之前专注构建群体公平底线，之后全速回补社会福利，将非凸的在线公平约束转化为清晰可控的参数化切换流程。
分段平滑的原对偶构造：提出带阈值分段点的对偶核函数 $g(z)$，使得原本分离的公平分配与注水贪心能够在同一个线性规划对偶框架下得到闭式分析。
纠正历史松弛上限：敏锐指出既有文献中的公平性代价上界在低公平要求区间甚至超过了无约束匹配上限 $1 - 1/e$ 的荒谬现象，借助两阶段复合对抗构造建立了真正严谨的理论边界。

局限与展望¶

不可分匹配的 CEF 间隙：Hybrid Ranking 的不可分 CEF 因子为 $\gamma/2$（最高 $0.5$），相比可分匹配的 $1 - 1/e \approx 0.632$ 仍有提升空间，未来需探索超越在线独立采样的强关联舍入技术。
偏好模型局限于二值图：当前模型假设代理对物品的评价为二值（喜欢或不喜欢），尚未推广至边带权重（Edge-weighted）或带预算约束的广义出价场景。
对抗到达模型的保守性：研究针对全对抗式（Adversarial）输入序列，若在随机到达顺序（Random-order）或随机已知分布模型下，有望取得显著高于 $1 - 1/e$ 的效率-公平联合保证。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次打破在线类别匹配长达数年的 1/2 效率壁垒，且给出了近乎闭合的理论上下界。
实验充分度: ⭐⭐⭐⭐☆ 理论推导与数值分析极为完备，对双阶段对抗下界与参数权衡曲面的刻画无懈可击。
写作质量: ⭐⭐⭐⭐⭐ 论文主干脉络清晰，原对偶分析与标记策略形式化极为严谨优美。
价值: ⭐⭐⭐⭐⭐ 为实时受限分配系统（网约车、数字广告）中的算法公平治理提供了兼具可解释性与性能保证的理论范式。

设置 / 机制	阈值参数 \(\gamma\)	CEF 公平性保证	USW 社会福利竞争比	理论上限 (UB)	相比基线突破
经典无约束 (RANKING / Water-filling)	\(\gamma = 0\)	\(0.0000\)	\(1 - 1/e \approx 0.6321\)	\(0.6321\)	纯效率基线 (无公平保证)
历史公平基线 (Hosseini et al. / Hajiaghayi et al.)	-	\(1 - 1/e \approx 0.6321\) (Div) / \(0.5000\) (Indiv)	\(\le 0.5000\)	\(1.0000\) (无效界)	受限于非浪费性 1/2 壁垒
EFTT (Divisible, 本文)	\(\gamma = 0.5000\)	\(1 - e^{-0.5} \approx 0.3935\)	\(1 - \frac{e^{-0.5}}{1.5} \approx 0.5956\)	\(0.6133\)	突破 1/2 (+19.1% 相对福利增益)
EFTT (Divisible, 本文平衡点)	\(\gamma = 0.7915\)	\(0.5468\)	\(0.5468\)	\(0.5750\)	同时实现 >0.54 的 CEF 与 USW
EFTT (Divisible, 强公平)	\(\gamma = 1.0000\)	\(1 - 1/e \approx 0.6321\)	\(0.5000\)	\(0.5000\)	达到最优 CEF 并匹配理论上限
Hybrid Ranking (Indivisible, 本文)	\(\gamma = 0.5000\)	\(0.2500\)	\(0.5956\)	\(0.6133\)	离散下突破 1/2 效率界
Hybrid Ranking (Indivisible, 本文平衡点)	\(\gamma = 0.7024\)	\(0.3512\)	\(0.5645\)	\(0.5891\)	离散匹配下高福利与强公平兼备
Hybrid Ranking (Indivisible, 强公平)	\(\gamma = 1.0000\)	\(0.5000\)	\(0.5000\)	\(0.5000\)	离散下达到最大可能 1/2 CEF

参数 \(\gamma\)	可分 CEF (\(1 - e^{-\gamma}\))	不可分 CEF (\(\gamma / 2\))	共同 USW 保证 (\(1 - \frac{e^{\gamma-1}}{\gamma+1}\))	新推导理论上限 (\(\frac{1+\alpha-e^{\alpha-1}}{1+\alpha}\))	旧上限对比 (\(1/(1+\alpha)\))
\(0.00\)	\(0.0000\)	\(0.0000\)	\(0.6321\) (\(1 - 1/e\))	\(0.6321\)	\(1.0000\) (平凡界)
\(0.20\)	\(0.1813\)	\(0.1000\)	\(0.6272\)	\(0.6288\)	\(0.8465\) (远高于真实值)
\(0.40\)	\(0.3297\)	\(0.2000\)	\(0.6133\)	\(0.6191\)	\(0.7520\) (松弛过大)
\(0.60\)	\(0.4512\)	\(0.3000\)	\(0.5886\)	\(0.5985\)	\(0.6891\) (仍超过无约束界)
\(0.80\)	\(0.5507\)	\(0.4000\)	\(0.5447\)	\(0.5592\)	\(0.6448\) (开始有意义)
\(1.00\)	\(0.6321\)	\(0.5000\)	\(0.5000\)	\(0.5000\)	\(0.5000\) (仅在端点收敛)