betaFeedback

WorksComputer Science

Closing Gaps in Online Fair Division

Abstract

We study the online fair division of indivisible items, where items arrive one at a time and must be allocated immediately and irrevocably. We address three central open questions in the literature. First, we show that for every n≥2n\ge 2 agents, every fixed k≥1k\ge 1, and every α∈(0,1]α\in(0,1], no online algorithm can guarantee αα-PROPkk against an adaptive adversary. This remains true even when the total number of goods is known in advance, all values lie in [0,1][0,1], and every good is positively valued by at most two agents. The impossibility extends to a broad range of standard envy-based, proportionality-based, and share-based fairness notions. We also establish an analogous impossibility for chores. Second, in the setting with predictions, a lightweight form of future information, the maximum item value, was previously known to guarantee only 1/n1/n-PROP1, leaving open whether the dependence on nn is necessary. We give a deterministic 19/3019/30-PROP1 algorithm against adaptive adversaries that does not require knowing the total number of goods. Given an additional upper bound κ∈[2,n]κ\in[2,n] on the number of agents who value any good positively, the guarantee improves to max⁡{19/30,n/(n+κ)}\max \{ 19/30, n/(n+κ) \}. The guarantee remains a positive constant under any fixed one-sided prediction error below one. When predictions are exact and the total number of goods m≥nlog⁡nm\ge n\log n is known in advance, a deterministic algorithm achieves the same 19/3019/30-PROP1 factor together with O(mlog⁡n/n)O(\sqrt{m\log n/n}) maximum additive envy after normalizing each agent's values by their maximum item value. Third, against a non-adaptive adversary, we determine the tight high-probability PROP1 guarantee of the classical Like rule, which assigns each good uniformly among the agents who value it positively. Its guarantee improves when fewer agents value the same good, unlike uniform random allocation.

Paper details

vlnc:W_xf5uqsn4
Version
v2 · latest
Published
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-5.6 Sol (bare), GPT-6

View statement
Looking for related papers…