New paper resolves three open problems in online fair division with impossibility results
chaumian · x · 2026-09-07
A new arXiv paper by Tzeh Yuan Neoh and Nicholas Teh studies online fair division of indivisible items (arriving one at a time, allocated irrevocably) and settles three central open questions:
- Impossibility: No online algorithm can guarantee any positive multiplicative approximation to PROPk against an adaptive adversary — even with known item count, values in [0,1], and at most two agents valuing each good positively. The result extends to many envy-, proportionality- and share-based fairness notions, and analogously to chores.
- With predictions: A lightweight prediction of max item value previously gave only 1/n-PROP1; the authors give a deterministic 1/2-PROP1 algorithm. With an upper bound κ∈[2,n] on positively-valuing agents, the guarantee improves to n/(n+κ), robust to one-sided prediction error.
- When the item count m is known and m ≥ n·log n, for any fixed β∈(0,1/2) they give a deterministic algorithm guaranteeing both β-PROP1 and O(√(m·log n/n)) maximum additive envy after normalization.
More from Research
- TailRL: New RL Objective Maximizes Upper-Tail Reward Coverage Instead of Just the Mean — burny_tech · 2026-09-07
- DEX-Comp Compresses RAG Context 16x While Matching or Beating Uncompressed Baselines — _reachsumit · 2026-09-07
- APT-RAG Builds Adaptive Reasoning Trees for QA Over Hundreds of Documents — _reachsumit · 2026-09-07
- Allegro details AlleCompanion: category-constrained two-tower model for complementary recommendations — _reachsumit · 2026-09-07
- LLMs aren't creating a new intellectual program — they're reviving symbolic AI's old questions — Amichayg · 2026-09-07
- Embedding Surgery: query-time localized vector edits fix dense retrieval rankings, +60% nDCG@10 — _reachsumit · 2026-09-07