acceptodds
Under review as a conference paper at ICLR 2027

One Item of Slack: Separating EF1 from EFX under Noisy Observations

Abstract

Envy-freeness up to one item (EF1) asks that an agent's envy of another bundle vanish once *some* single item is dropped from it; EFX asks this for *every* item. We study what that quantifier costs when valuations are learned from noisy observations rather than given. Our setting repairs envy in a fixed allocation from a pool of spare goods, with standard fair division the case in which nothing is allocated in advance and every good must be handed out. In it we exhibit two agents with coverage valuations, a standard submodular class, over pool goods and two fixed items, on which one fixed extension, consulting nothing at all, is -EF1, while -EFX and -EF need observations for every . For -EFX the exponent is tight: observations suffice on the same family. Every instance admits an exactly envy-free extension, so the cost is not infeasibility in disguise. Neither ingredient forces the quadratic cost alone. Letting the algorithm split the two fixed items makes -EFX free on these valuations, and with no fixed allocation two agents reach -EFX from observations under arbitrary monotone valuations, where hides logarithmic factors; exact EFX there still takes exponentially many queries. A transfer principle turns any deterministic oracle algorithm tolerating small errors into a learning algorithm, giving there for -EF1 with agents. One item of slack lets an allocation stop tracking valuations at the scale of single items. A fixed pair that cannot be reallocated separately puts that scale back.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
fair division, envy-freeness, EFX, sample complexity, noisy valuations, query complexity

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_nTfGOpenReview ↗
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 ε\varepsilon-EFX and ε\varepsilon-EF require Ω(m2)\Omega(m^2) observations for ε≤1/128\varepsilon\le 1/128. Every instance admits an exactly envy-free extension, and an O(m2)O(m^2) 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 O~(nm/ε2)\widetilde O(nm/\varepsilon^2) observations for ε\varepsilon-EF1 under arbitrary monotone valuations, and O~(m/ε3)\widetilde O(m/\varepsilon^3) for two-agent ε\varepsilon-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 O(m/ε)O(m/\varepsilon) 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 1−1/e1-1/e 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 Θ~(m/Δ2)\widetilde\Theta(m/\Delta^2) bound to Li et al. (2026). Using that reference’s definition of Δ\Delta, its principal tight rate is Θ~(m5/2/Δ2)\widetilde\Theta(m^{5/2}/\Delta^2) 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 1/21/2—is easy on the constructed family. In fact, the same lower-bound argument extends to multiplicative factors sufficiently close to one. Writing α=38−η=3831024\alpha=\frac38-\eta=\frac{383}{1024}, multiplicative cc-EFX requires the first agent’s pool bundle to have value at least cαc\alpha. The recovery argument therefore applies with effective additive tolerance εeff=(1−c)α\varepsilon_{\mathrm{eff}}=(1-c)\alpha. For c≥375/383≈0.9791c\ge 375/383\approx0.9791, this is at most 1/1281/128, so the same quadratic lower bound follows; c=0.99c=0.99 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.

Reviewer_CtnhOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
3(+1)
Read review
Paper summary
  • the paper looks at fair division when an algorithm can request independent, bounded observations where the mean is agents' values for chosen bundles. the objective is to find allocations satisfying additive approximations to EF1 or EFX.
  • They give theoretical guarantees in various settings.
Critical strengths
  • The results are technically interesting. Specifically, Thm 3.1 and Prop 3.4 give a nice comparison between EF1 and EFX on two agent coverage valuations. Thm 4.2 and 4.3 give algorithms for standard fair division with arbitrary monotone valuations, showing how well-established fair division algorithms can be adapted to noisy observations while still retaining the standard fairness guarantees in the noiseless case.
Critical weaknesses
  • In sec 3, the authors compare the EFX lower bound (thm 3.1) which assumes a fixed initial allocation and budget of m/2m/2 with the EF1 upper bound of Thm 4.2 (which is for standard fair division). Sure, the comparison is valid, but these two results crucially does not establish a near linear lower bound and a quadratic EFX LB for the same general class of instances. since the paper's goal is to compare EF1 and EFX, this distinction is important
  • the two agent EF1 discussion does not include a substantially smaller UB. Oh et al. (2021)'s binary search alg can be adapted to small errors in the estimmated values while using only O(log⁡m)O(\log m) value estimates. Applying thm 4.1 then gives us O(ε2log⁡mlog⁡((1+log⁡m)/δ))O(\varepsilon^2 \log m \log (( 1 + \log m) / \delta)) observations. This improves substantially on the EF1 bound used in the comparison with EFX.
Questions for authors
  • See critical weaknesses
Reviewer_r1AKOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies fair division from a query complexity point of view. The agents' valuations are not known, but can be estimated through queries: each query returns a sample of a random variable whose mean is the agent's value for the queried bundle, so values are estimated from samples. The goal is to output an allocation that is EF, EF1 or EFX up to an additive slack ε\varepsilon, using as few samples as possible.

The paper considers two settings: the standard fair division setting, and the Envy Elimination by Adding Goods (EEAG) framework of Bentert et al (2025). In EEAG, some items are already allocated and cannot be moved, and at most kk additional items from a pool of mm goods can be handed out.

The paper's main result is a lower bound in EEAG. For a family of two-agent instances where one agent holds two fixed items and k=m/2k = m/2, any algorithm that outputs an ε\varepsilon-EFX (or ε\varepsilon-EF) allocation needs Ω(m2)\Omega(m^2) samples for ε≤1/128\varepsilon \le 1/128, i.e., quadratically many in the number of items. The paper studies fair division from a query complexity point of view. The agents' valuations are not known, but can be estimated through queries: each query returns a sample of a random variable whose mean is the agent's value for the queried bundle, so values are estimated from samples. The goal is to output an allocation that is EF, EF1 or EFX up to an additive slack ε\varepsilon, using as few samples as possible.

The paper considers two settings: the standard fair division setting, and the Envy Elimination by Adding Goods (EEAG) framework of Bentert et al (2025). In EEAG, some items are already allocated and cannot be moved, and at most kk additional items from a pool of mm goods can be handed out.

The paper's main result is a lower bound in EEAG. For a family of two-agent instances where one agent holds two fixed items and k=m/2k = m/2, any algorithm that outputs an ε\varepsilon-EFX (or ε\varepsilon-EF) allocation needs Ω(m2)\Omega(m^2) samples for ε≤1/128\varepsilon \le 1/128, i.e., quadratically many in the number of items. On the same instances, an EF1 allocation can be output without any samples, and a matching O(m2)O(m^2) upper bound holds for ε\varepsilon-EFX.

On the positive side, the paper gives a general principle that turns query algorithms robust to small errors into sampling algorithms. In the standard setting with monotone valuations, this yields ε\varepsilon-EF1 for nn agents with O~(nm/ε2)\tilde{O}(nm/\varepsilon^2) samples and ε\varepsilon-EFX for two agents with O~(m/ε3)\tilde{O}(m/\varepsilon^3) samples., and a matching O(m2)O(m^2) upper bound holds for ε\varepsilon-EFX.

On the positive side, the paper gives a general principle that turns query algorithms robust to small errors into sampling algorithms. In the standard setting with monotone valuations, this yields ε\varepsilon-EF1 for nn agents with O~(nm/ε2)\tilde{O}(nm/\varepsilon^2) samples and ε\varepsilon-EFX for two agents with O~(m/ε3)\tilde{O}(m/\varepsilon^3) samples.

Critical strengths
  1. The paper works on a timely and interesting problem, fitting for the conference's scope. Indeed, the idea of asking how many samples we need to achieve approximations of EF/EF1/EFX is well motivated.

  2. The paper offers a good first picture of the problem, with some non-trivial results. Its main result is a lower bound (Theorem 3.1): on a family of two-agent EEAG instances, in which one agent holds two fixed items and the other must be compensated with goods from a pool of mm goods, any algorithm that outputs an ε\varepsilon-EFX (or ε\varepsilon-EF) allocation needs Ω(m2)\Omega(m^2) samples, since it must essentially identify which pool goods carry a small extra value; in contrast, an EF1 allocation needs no samples at all (Lemma 3.2). The bound is tight for ε\varepsilon-EFX on this family (Proposition 3.4), although it applies only to EEAG instances. The paper also gives a general principle for turning robust query algorithms into sampling algorithms (Theorem 4.1), and applies it to obtain ε\varepsilon-EF1 for nn agents (Theorem 4.2) and ε\varepsilon-EFX for two agents (Theorem 4.3) in the standard setting. Finally, the proofs appear correct.

Critical weaknesses
  1. The results are narrow: the claimed separation is not as strong as stated.

The paper presents its main contribution as a separation between EF1 and EFX, but this separation is established only on a single family of instances, and it is supported by comparing results from two models that are not directly comparable.

  • The Ω(m2)\Omega(m^2) lower bound for ε\varepsilon-EFX is proved only for a family of two-agent EEAG instances. The contrasting near-linear bound for ε\varepsilon-EF1 (Theorem 4.2) holds in the standard setting, yet the paper at some points compares the two directly. For example, immediately after Theorem 3.1, Section 3 reads it "against Thm. 4.2" and concludes that the EFX lower bound is quadratic whereas the EF1 upper bound is near-linear. This comparison is not valid. In the standard setting, two-agent ε\varepsilon-EFX needs only O~(m/ε3)\tilde{O}(m/\varepsilon^3) samples (Theorem 4.3). In EEAG, the only ε\varepsilon-EF1 upper bound for general monotone valuations is exponential in the budget (Corollary E.3). Within neither model does the paper establish a gap between the two notions.
  • The positive results are also narrow. Theorem 4.2 is a direct extension of envy-cycle elimination, and the paper itself suspects that it is not tight (see Open Problem G.1). Theorem 4.3 covers only two agents, via the classical cut-and-choose. No theoretical result is given for ε\varepsilon-EFX with more agents.
  • The relation to prior work is not fully established. Oh et al. (2021) already separate EF1 from EFX in the exact query model, which the paper itself (Section 2) treats as a special case of its observation model; this separation is not discussed enough. The result of Li et al. (2026) appears to be misreported: the paper states their bound as Θ~(m/Δ2)\tilde{\Theta}(m/\Delta^2), whereas Li et al. state Θ~(m2.5/Δ2)\tilde{\Theta}(m^{2.5}/\Delta^2).
  1. The setup of the paper is messy, and the paper is not particularly well written.
  • The choice of model is not clear and is only slightly motivated. For a new problem, the standard fair division model is the natural starting point. It was not clear to me why the paper develops its idea on a very specific model, EEAG, which it motivates only lightly.
  • An impossibility result for EEAG does not transfer to the standard model, contrary to what the paper claims, or seems to claim, by presenting EEAG as the more general model. I believe the authors do not really intend this claim; as one can see by reading the paper carefully, the hard family becomes trivial in the standard setting (see e.g., Figure 2(b)). This should, however, be communicated much more clearly.
  • The writing is dense and hasty, and the reader cannot get the results on a first reading. Some parts read like internal notes. For example, Section 3, the first results section, opens with "The quadratic barrier persists under small additive tolerance", before any barrier has been shown. It then states Theorem 3.1 before the instance it refers to, and immediately afterwards compares it with a theorem that has not yet been stated or proven (Theorem 4.2). There are also several inconsistencies and informal remarks, including references to nonexistent results (Proposition 4.9, Definition 2) and comments such as "We found this in testing" (proof of Theorem 4.3, Appendix D).
Questions for authors
  1. Choice of model. Could the authors explain in more detail the choice of the EEAG model with coverage valuations? In my reading, this choice is not adequately motivated in the manuscript. In particular, why not study the question first in the standard fair division model, or in EEAG with additive valuations, as in Bentert et al. (2025)?

  2. EFX versus EF on the hard family. On the hard family of Theorem 3.1, the binding EFX condition is the one obtained by dropping an item of tiny value (η=2−10\eta = 2^{-10}). As a result, the same lower bound holds for ε\varepsilon-EF, and the two curves in Figure 2 coincide (Section 6.1). Using such instances is a standard way to prove EFX lower bounds. However, the title and conclusion present the result as a separation between EF1 and EFX. Could the authors comment on whether there are instances that separate ε\varepsilon-EFX from ε\varepsilon-EF1 while remaining clearly distinct from (approximate) EF? If not, would it be more accurate to describe the result as a separation between EF1 and (approximate) EF?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.