- 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
- 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.
- 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
- Is 19/30 simply a convenient certified factor, or is it close to the limit of this potential-based approach?
- Is any upper bound below 1 currently known under exact MIV predictions?