- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper studies the number of noisy value observations needed to find approximately fair allocations of indivisible goods. It considers bounded, independent observations whose means equal the underlying bundle values, and focuses on repairing an existing allocation by distributing additional goods subject to a budget. Its central result constructs a two-agent family with coverage valuations on which exact EF1 requires no observations, whereas additive -EFX and -EF require observations for . Every instance admits an exactly envy-free extension, and an algorithm matches the EFX lower bound on this family.
The paper also develops a robust oracle-to-sampling framework. In the standard setting, with no initial allocation, it obtains observations for -EF1 under arbitrary monotone valuations, and for two-agent -EFX. Allowing the initial goods in the hard family to be reassigned eliminates its observation requirement entirely. Thus, the separation concerns the interaction between the fairness requirement and allocation constraints. Validation consists primarily of theoretical proofs, supplemented by exhaustive checks on small instances, adversarial perturbation tests, synthetic experiments, and experiments using valuations induced from preference rankings.
Critical strengths
A clean, tight information-theoretic separation on the same feasible instances. Theorem 3.1 and Proposition 3.4 establish a substantive distinction between EF1 and EFX: a fixed allocation extension achieves exact EF1 without learning anything, while every randomized adaptive algorithm needs quadratically many observations for approximate EFX. Exact envy-free feasibility rules out nonexistence as the explanation, and the matching upper bound shows that the exponent is inherent to this family. The construction also gives an understandable mechanism: EF1 can discard the high-value initial item, whereas EFX must satisfy the constraint obtained by discarding the low-value item, forcing recovery of many hidden item identities. This is the strongest consideration supporting acceptance.
The upper bounds provide a meaningful algorithmic complement beyond the constructed family. Theorems 4.2–4.3 cover arbitrary monotone valuations and address the fact that noisy estimates need not preserve monotonicity. The two-agent EFX algorithm is particularly interesting: retiring previously checked items within an epoch and controlling progress through a potential function yield only distinct bundle consultations. Together with the result obtained by releasing the initial allocation, these algorithms clarify when the quadratic obstacle disappears. They make the contribution more substantial than an isolated hard-instance construction.
Critical weaknesses
The comparison with prior learning models contains substantive errors. Appendix G, p. 25, claims that the distinction from Balkanski et al.’s The Limitations of Optimization from Samples is the objective rather than the access model, and that their indistinguishability argument carries over to adaptively chosen queries. This is incorrect: that work considers examples drawn independently from a fixed distribution, while the present paper permits adaptive bundle queries. The cited work explicitly contrasts its impossibility result with the approximation available for coverage maximization through value-oracle access. Consequently, its impossibility cannot be transferred to adaptive queries in the manner claimed. This matters because the discussion uses that comparison to explain why the fairness objective, rather than access to information, accounts for tractability. The introduction also attributes a bound to Li et al. (2026). Using that reference’s definition of , its principal tight rate is in the stated sufficiently-large-gap regime, and its observations concern individual items rather than arbitrary bundles. These distinctions need correction for an accurate assessment of the paper’s contribution relative to the closest noisy-query work.
The claimed necessity of additive approximation is false. Section 3.2 states that the relaxation must be additive, but its argument only shows that a sufficiently weak multiplicative guarantee—specifically, a factor at most —is easy on the constructed family. In fact, the same lower-bound argument extends to multiplicative factors sufficiently close to one. Writing , multiplicative -EFX requires the first agent’s pool bundle to have value at least . The recovery argument therefore applies with effective additive tolerance . For , this is at most , so the same quadratic lower bound follows; is one concrete example. This does not invalidate the main theorems, but it contradicts a stated boundary of the result and weakens the paper’s explanation of which assumptions are essential.
Questions for authors
No.