- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies online allocation of indivisible goods among agents with additive valuations. Each good's values are revealed on arrival, and it must be allocated immediately. Reassignments are allowed but must satisfy either item-level upgrades, where every old good is retained or replaced by a good worth at least as much, or bundle-level upgrades, where each agent's total utility must not decrease. Fairness is measured primarily by maximin share (MMS), the value an agent can secure by partitioning the goods into bundles and taking the least valuable one.
The authors show that, under item-level upgrades, fixed picking sequences achieve nearly approximation of MMS, where is the -th harmonic number. If further requiring envy-freeness up to one good (EF1), then the optimal approximation ratio is reduced to . On the other hand, bundle-level upgrades permit an algorithm that achieves exact MMS, envy-freeness up to any good (EFX), and Pareto optimality for two agents. For , the authors give an algorithm that achieves -MMS together with EF1 and -EFX; they also show that no approximation ratio above is possible even with identical valuations. When item predictions are provided, the authors show how to achieve offline MMS guarantees with an additive loss bounded by prediction error, but they show that requiring exact MMS with correct predictions rules out any positive worst-case MMS approximation under item-level upgrades.
Critical strengths
This paper studies a trending and well-motivated problem, and the writing is generally clear. The online setting with upgrade recourse naturally generalizes prior recourse settings and is interesting to study. The authors establish a variety of results, covering different fairness concepts and the setting with predictions. In particular, it's good-to-know that a fixed picking sequence can achieve nearly optimal approximation factors for item-level upgrade.
Critical weaknesses
The concerned setting doesn't bring new technical insight to the fair-division literature: the proposed algorithms (such as using picking sequences) and analysis seem to largely follow existing ones, and is also too restricted for practical applications. Many gaps remain in the results (although I believe closing them could be difficult).
Questions for authors
No.