arXiv 论文攻克在线公平分配三大开放问题，证明多重不可能性
chaumian · x · 2026-09-07
Tzeh Yuan Neoh 与 Nicholas Teh 在 arXiv 发布论文《Closing Gaps in Online Fair Division》，研究不可分物品的在线公平分配（物品逐个到达且须立即不可撤销地分配），解决了该领域三个核心开放问题：
- 不可能性结果：证明面对自适应对手，任何在线算法都无法对 PROPk（比例性近似）给出任何正的乘性近似保证——即使物品总数已知、估值在 [0,1] 区间、每件物品最多被两个 agent 正向估值。该结果还推广到大量基于嫉妒、比例性和份额的标准公平概念，并对“ chores”（负任务）场景同样成立。
- 带预测的算法：此前仅知最大物品值的轻量预测可给出 1/n-PROP1，作者给出确定性的 1/2-PROP1 算法，摆脱对 n 的依赖；若给定正向估值 agent 数上界 κ∈[2,n]，保证提升为 n/(n+κ)，且在单侧预测误差下仍为常数。
- 当物品总数 m 已知且 m≥n·log n 时，对任意固定 β∈(0,1/2)，给出同时保证 β-PROP1 和 O(√(m·log n/n)) 最大加性嫉妒的确定性算法。
「研究」频道最新
- DEX-Comp 压缩 RAG 上下文 16 倍,性能反超未压缩基线 — _reachsumit · 2026-09-07
- 一行改动白嫖涨点：NoRA 归一化 LoRA 下投影提升收敛与抗遗忘 — omarsar0 · 2026-09-07
- APT-RAG 用自适应推理树解决上百文档证据密集型 QA — _reachsumit · 2026-09-07
- Allegro 公开互补商品推荐框架 AlleCompanion:类目约束双塔过滤共购噪声 — _reachsumit · 2026-09-07
- LLM 让符号 AI 老问题复活：自动证明的旧传统值得重读 — Amichayg · 2026-09-07
- Embedding Surgery:查询时局部修正文档向量,DG@10 提升可达 60% — _reachsumit · 2026-09-07