acceptodds
Under review as a conference paper at ICLR 2027

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 agents, every fixed , and every , no online algorithm can guarantee -PROP against an adaptive adversary. This remains true even when the total number of goods is known in advance, all values lie in , 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, with a prediction of each agent's maximum item value, a lightweight form of information about future goods, the best previous guarantee was -PROP1, leaving open whether the dependence on is necessary. We give a deterministic -PROP1 algorithm against adaptive adversaries that does not require knowing the total number of goods. Given an additional upper bound on the number of agents who value any good positively, the guarantee improves to . 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 is known in advance, a deterministic algorithm achieves the same -PROP1 factor together with 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. Unlike that of uniform random allocation, its guarantee improves when fewer agents value each good.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
online fair division, fair division

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_kDjeOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies online allocation of indivisible goods under additive valuations. It proves that no online algorithm can guarantee any positive PROPk approximation against an adaptive adversary. With maximum item value predictions, it gives a deterministic 19/30-PROP1 guarantee, with extensions for sparse valuations, prediction errors, and additive envy. It also establishes tight high-probability PROP1 bounds for LIKE against a non-adaptive adversary. The results are supported by theoretical proofs.

Critical strengths
  1. The impossibility result is strong: it covers all online algorithms, including randomized ones, even with a known horizon, bounded values, and only two interested agents per good. This goes well beyond the earlier lower bounds for specific greedy rules.
  2. Improving the MIV guarantee from 1/n to a constant is a substantial advance over Choo et al. (2026). Together with the tight LIKE analysis, the paper clearly shows how future information and the adversary model change what fairness is achievable.
Critical weaknesses

The 19/30 guarantee relies on a carefully tuned piecewise potential whose construction is difficult to follow. No matching upper bound is given, so it remains unclear how close this factor is to the best possible guarantee.

Questions for authors
  1. Is 19/30 simply a convenient certified factor, or is it close to the limit of this potential-based approach?
  2. Is any upper bound below 1 currently known under exact MIV predictions?
Reviewer_wYE6OpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the online fair allocation of indivisible goods under the α-PROPk fairness criterion and establishes three main results.

  1. Impossibility under adaptive adversaries. For any fixed k≥1k\geq1 and α∈(0,1]\alpha\in(0, 1], the authors show that an adaptive adversary can construct a sequence of goods that forces any online allocation algorithm, including randomized algorithms, to violate α\alpha-PROP-k with probability one.

  2. Constant-factor guarantee with exact-upper-bound predictions. When the maximum item value of each agent is known in advance, the authors develop a deterministic online allocation algorithm that guarantees 0.6330.633-PROP1, significantly improving upon the previous 1/n1/n-PROP1 guarantee.

  3. Improved guarantees for LIKE under sparse valuations. When each good is positively valued by at most κ\kappa agents, the LIKE algorithm, which assigns each good uniformly at random among agents who value it positively, achieves α\alpha-PROP1 with probability at least 1 − δ\delta, where α=min⁡{1,3n32κlog(n/δ)}\alpha=\min\{1, \frac{3n}{32\kappa log(n/\delta)}\}, against a non-adaptive adversary.

Critical strengths

1, This paper studies a well-established problem in online fair allocation and makes a substantial improvement over previous results. In particular, the deterministic algorithm achieves a constant-PROP1 guarantee with MIV predictions, that removes the 1/n1/n dependence in the previous guarantee. This is a qualitative rather than merely incremental improvement.

2, This paper establishes a significant impossibility result showing that no online algorithm can guarantee any positive approximation to PROP-k against an adaptive adversary for any fixed kk.

Critical weaknesses

The practical significance of the guarantee is somehow limited by the weakness of the fairness criterion itself. PROP1 already relaxes proportionality by allowing the hypothetical addition of one good, and α\alpha-PROP1 further weakens this requirement through multiplicative approximation. In particular, satisfying α\alpha-PROP1 does not necessarily imply that every agent receives a meaningful amount of actual utility. Also, the positive result in Theorem 4.1 requires knowing each agent's exact maximum item value over the entire future sequence, which may be difficult to justify in realistic online settings. Although the paper extends the guarantee to bounded one-sided prediction errors, it does not address more general prediction errors, particularly underestimation.

Note: Although lack of experiment is a subtle weakness, I do not require nor encourage the authors to add any experiment in rebuttal. I myself would not increase the score merely based on additional experiments.

Questions for authors

1, Could the authors provide a concrete scenario where the reliable upper-bound predictions of each agent's maximum item value are available, especially before the allocation process begins?

2, Please see my comments on the weaknesses above.

Reviewer_cdbgOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies fair division of indivisible items in an online setting: the items arrive online in a sequential manner while the agents are fixed in advance. The main fairness notion studied in the paper is that of proportionality (PROP): each agent’s proportional share is 1/n1/n of the total value of all items, where nn is the number of agents. For indivisible items, the exact notion is not achievable and is relaxed to PROP1, which lowers an agent’s proportional share by the value of the largest item they did not receive, and in extension to PROPk, which lowers the share by the kk largest items. Moreover, an allocation is α\alpha-PROP/PROP1/PROPk if each agent receives at least an α\alpha fraction of their respective share bound. The authors have three sets of results: first, they prove that no algorithm can obtain a meaningful guarantee (no α\alpha-PROPk for any α\alpha) against an adaptive adversary. Their proof first reduces the problem into a two-agent instance where the target notion is PROP1 and then carefully selects a sequence of values based on the difference between each agent’s actual value and their PROP1-share. The second result belongs to the algorithms with predictions paradigm. Under this paradigm, the algorithm is augmented with some extra, possibly inaccurate, information and its output also depends on the quality of the prediction. The paper uses a prediction of the maximum value an agent may obtain from an item (MIV prediction). Under a perfect prediction, the bound is 19/3019/30. This is achieved by a deterministic allocation rule that is built around a suitably selected potential function. If the prediction is inaccurate, but also accompanied by an error bound ϵ\epsilon, the guarantee degrades with ϵ\epsilon. The third contribution gives a tight bound for the LIKE rule against non-adaptive adversaries. The authors’ upper bound also applies to the RAND rule.

Critical strengths

None

Critical weaknesses

I do not think that an (adaptive) adversary is well motivated in the context of online fair division, especially of goods. Moreover, the prediction augmented result assumes an upper bound on the prediction error. Typically, such a bound is not known in advance and one must design a mechanism that is robust, i.e. handles arbitrary errors.

Questions for authors
  1. Can the authors provide some motivation for the settings they study?
  2. I would also be interested in the original bound of 1/21/2, if the authors deem that the non optimized version is more intuitive.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.