Closing Gaps in Online Fair Division
Tzeh Yuan Neoh, Nicholas Teh
cs.GT
2026-09-05
无未来信息时任何正的PROPk近似都不可能；每人一条最大值预测即可确定性做到1/2-PROP1，已知受众上限κ时升到n/(n+κ)。
物品一件件到达，必须立刻分给某个人，事后不能改。广告曝光、推荐位、共享算力排队都是这个设定。离线公平分配里，PROP1（proportionality up to one good，允许再补一件自己没拿到的物品后达到总值的 1/n）几乎是最弱的可接受底线，常被 EF1、MMS 蕴含。在线模型里，更强的 EF1、MMS 早已被证明不可近似。还没回答的问题是：难，是因为那些指标太强，还是「立刻、不可撤销」本身就不允许任何正的比例公平？
Choo 等人此前只对若干贪心规则给出否定，并在最大值预测下做到 1/n-PROP1。这篇把三个缺口一次补上。
第一条是否定。对任意 n≥2、k≥1、α∈(0,1]，没有在线算法能在自适应对手下保证 α-PROPk。已知物品总数、取值落在 [0,1]、每件物品最多两人看重，结论不变；随机化也对自适应对手无效。证明先把 PROPk 降到 PROP1（α-PROPk 蕴含 (α/k)-PROP1），再把 n 人降到 2 人。两人情形跟踪每人当前 PROP1 不等式的归一化松弛：对手反复把一方松弛压回受控区间，同时把另一方固定幅度往下推，直到两边都低于阈值，再抛出一件双方都要的物品，没拿到的那人立刻违约。同一套蕴含关系把否定扩到 EF、EFX、EF1、MMS、PROPX 等常见指标。杂务版本更硬：任何 λ<n 的 λ-PROPk 都不成立。
第二条靠一条很轻的预测：每人只给一个标量，自己对单件物品的最大值（MIV，maximum item value），不知道总值，也不知道何时出现。算法把这件「允许补上的最大值」提前记在账上，用归一化松弛的倒数之和当势函数，每来一件物品就挑一个不抬高势的接收人。每个受影响的人存在一个接收概率，使自己的倒数项期望不变；这些概率加起来不超过 1，所以必有一个确定性选择不增加势。没有额外信息时 κ=n，得到 1/2-PROP1；若已知每件物品最多 κ 人看重，因子升到 n/(n+κ)。预测只高估、相对误差不超过 ε 时，因子变成 n(1-ε)/(n+κ-ε)，ε<1 就仍是正常数。
物品总数 T 已知且 T≥n log n 时，把倒数势和 Benadè 的指数嫉妒势合在一起：先按保住倒数项的概率分配，剩余概率均分。任意固定 β∈(0,1/2)，同时保证 β-PROP1 和 O(√(T log n / n)) 的归一化最大加性嫉妒。
第三条比较两条经典随机规则。Rand 在全体 n 人中均匀抽；Like 只在看重该物品的人中抽。非自适应对手下，Like 以概率 1-δ 保证 Θ(min{1, n/(κ log(n/δ))})-PROP1，κ 小时比 Rand 的 Θ(1/log(n/δ)) 好一个 n/κ 倍；两边都紧。加性嫉妒上恰好反过来：Like 的相关方差更大，二值实例上期望最大嫉妒可以到 Ω(√(m/κ))。
| 设定 | 保证 | 对照 |
| 无预测，自适应对手 | 任何 α-PROPk 都不可能 | 此前只否定部分贪心规则 |
| 精确 MIV 预测 | 1/2-PROP1（κ 已知则 n/(n+κ)） | Choo 等人 1/n-PROP1 |
| 单边误差 ε 的 MIV | n(1-ε)/(n+κ-ε)-PROP1 | 误差连续进入因子 |
| T≥n log n，MIV 加已知地平线 | 任意 β<1/2 的 β-PROP1，外加 O(√(T log n / n)) 归一化最大嫉妒 | 附录更简单证明只到 Θ(1/log n)-PROP1 |
| Like，非自适应 | Θ(min{1, n/(κ log(n/δ))}) | Rand 即使 κ=1 也是 Θ(1/log(n/δ)) |
杂务侧：任何小于 n 的 PROPk 乘性因子都不成立。
给在线推荐、广告、算力调度这类「来一件分一件」的系统画了边界。不想给算法任何未来信息，就别指望最终分配在乘性意义上接近比例公平，哪怕允许每人再补 k 件。愿意多记一个数（每人预计的单件最大值），PROP1 立刻从 1/n 跳到与 n 无关的常数。Like 和 Rand 的对比也很实用：物品受众很窄时 Like 更公平，但嫉妒波动更大，不能两条都要。
这是理论进展，不是即插即用的调度器。算法每件物品 O(n) 算术，实现不难；难的是 MIV 从哪来，以及真实偏好远比加性估值脏。
否定只打自适应对手。非自适应加上随机化就有正保证，两套数字不能混着读。MIV 再轻，也是未来信息，生产里估计单件最大值并不免费，单边高估还要求方向正确。同时保证里的嫉妒是用每人最大值归一化后的加性嫉妒，不是 EF1。Like 的紧界用的是二值估值。Chen 与 Tan 的竞争比是跟「同一实例离线能达到的公平」比，和这篇直接对 PROP 份额的比法不是同一个问题。