Pith. sign in

REVIEW 2 major objections 3 minor 39 references

Envy-Free Allocation of Indivisible Goods via Noisy Queries

T0 review · 2 major / 3 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that, for two agents with additive valuations, the number of noisy queries needed to find an envy-free allocation is Θ~(m^{2.5}/Δ²) in the regime where the optimal negative envy Δ is not too small, matching upper and lower

desk verdict New tight query-complexity result for noisy fair division, but the upper bound is not implementable as stated because it requires knowing Δ. read the letter →

arxiv 2602.06361 v2 pith:KGNXC235 submitted 2026-02-06 cs.GT cs.ITcs.LGmath.ITstat.ML

Zihan Li , Yan Hao Ling , Jonathan Scarlett , Warut Suksompong This is my paper · ORCID
classification cs.GTcs.ITcs.LGmath.ITstat.ML MSC 91B3268Q25
keywords envy-freeallocationindivisiblegoodsnoisyqueriesquerycomplexityGaussiannoisefairdivisionsampletwoagents
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks a basic question: when two agents' valuations of indivisible goods are observed only through noisy queries, how many answers must be collected before a fair — envy-free — division can be guaranteed? Its main assertion is that the answer is governed by a single gap parameter Δ, the amount by which the best allocation clears the envy threshold: the optimal query count scales as m^{2.5}/Δ², up to logarithmic factors, in the regime where Δ is at least about m^{1/4}. The upper bound is achieved by a simple polynomial-time rule that assigns each item by thresholding estimated utilities; the lower bound holds even for adaptive algorithms and unlimited computation. A sympathetic reader should care because the result draws a precise border between what is learnable and what is not when preferences are noisy, and it gives a concrete formula for how much information fairness costs.

What carries the argument

The upper bound uses an item-by-item thresholding rule: assign item i to agent a if c·v_i^a − v_i^b > 0 and to b otherwise, where v_i^ν is the estimated utility of agent ν for item i and c is a tunable balance parameter. Gaussianity makes these decisions probabilistic with known assignment probabilities, and the analysis shows that a suitably chosen c (computed from the estimates) balances envy in both directions. The lower bound uses a randomized hard instance with four item types: items slightly favored by one agent and disfavored by the other are mixed with items strongly favored or disfavored by both, so that random fluctuations in envy from unqueried items overwhelm any allocation that

What would settle it

Run the paper's Table 1 hard instance at Δ = m^{1/2} with q = c·m^{2.5}/Δ² queries for a very small constant c; the lower bound theorem says any algorithm must fail with probability at least 1/3, so an algorithm that succeeds with high probability at that budget would refute the lower bound. Conversely, an algorithm that succeeds with q = m^{2.5}/(100Δ²) on the same instance, for a large range of Δ, would violate the claimed tight scaling of the optimal query complexity.

Watch

Extended reading notes

Core claim

For two agents with additive [0,1] valuations and Gaussian query noise of constant variance, the paper establishes that the number of queries required to find an envy-free allocation is Θ~(m^{2.5}/Δ²) whenever the optimal allocation has negative envy at least Δ ≫ m^{1/4} log² m. Theorem 2 gives a polynomial-time non-adaptive query strategy based on item-by-item thresholding that achieves O~(m^{2.5}/Δ²); Theorem 3 shows that no algorithm — adaptive or randomized — can succeed with fewer than Ω~(m^{2.5}/Δ²) queries on a carefully constructed hard instance. The matching bounds identify the query complexity of envy-free allocation under noise as a function of the fairness gap.

Load-bearing premise

The upper-bound algorithms take the gap Δ (or a valid lower bound on it) and the noise variance σ² as given inputs to set their query budget, but the paper gives no procedure for estimating Δ from the noisy observations, so if only the existence of an optimal allocation with gap Δ is known, the proposed query count cannot actually be computed.

Editorial extensions

If this is right

  • The query complexity grows as 1/Δ²: the smaller the fairness gap of the optimal allocation, the quadratically more noisy answers are needed.
  • Non-adaptive queries achieve the optimal scaling, and adaptivity does not help in the covered regime, since the lower bound allows adaptive and randomized algorithms.
  • The two-agent results transfer directly to proportionality, because for two agents envy-freeness and proportionality coincide up to rescaling.
  • For very small gaps (Δ ≲ m^{1/4}) the paper leaves open the possibility that a fundamentally different, bundle-based algorithm could beat the stated bound.
  • Extending to more than two agents is identified as a challenging open direction, since the pairwise thresholding rule does not obviously generalize. (This is a direct consequence of the paper's own discussion in the conclusion.)

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The quadratic dependence on the gap mirrors classical pure-exploration sample complexity, suggesting that the √m factor arises from the need to control aggregate fluctuations in envy across m items rather than from estimating every item individually.
  • In practice the theorem implies a two-phase design: first estimate or bound Δ from pilot data, then budget queries according to m^{2.5}/Δ²; the paper does not provide such an estimator, so an explicit adaptive scheme to learn Δ while allocating would be a natural and testable extension.
  • The lower bound's hard instance predicts that any algorithm must pay this query cost even when it is allowed to choose which items to query adaptively; this could be checked empirically on the Table 1 construction by testing simple algorithms across a range of query budgets.
  • If the noise is sub-Gaussian rather than Gaussian, the upper-bound analysis may extend, but the paper's lower bound relies on Gaussian tail calculations; whether the same tight scaling holds for, say, bounded symmetric noise is an open question.
  • The result suggests that noisy settings do not make fair division impossible; they make it expensive in a precisely quantifiable way, and the cost is payable in queries rather than in algorithmic ingenuity.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper introduces a noisy-query model for two-agent envy-free allocation of indivisible goods, where each value query returns the agents' valuations corrupted by independent additive Gaussian noise. The core quantity is the optimal negative envy Δ, defined as the minimum envy of any allocation (negative means envy-free with slack). For two agents, additive [0,1] utilities, constant noise variance, and Δ ≥ m^{1/4} log² m (and Δ ≤ Cm), the paper claims a tight query complexity Θ~(m^{2.5}/Δ²): Theorem 2 gives a polynomial-time non-adaptive algorithm using O~(m^{2.5}/Δ²) queries, and Theorem 3 gives an algorithm-independent Ω~(m^{2.5}/Δ²) lower bound that holds even for adaptive algorithms. General noise levels are also discussed, and results are translated to proportionality.

Significance. The paper opens a natural and largely unexplored direction—envy-free allocation under noisy value queries—and identifies a gap-dependent scaling that is, in spirit, reminiscent of pure-exploration bandit bounds. The lower-bound construction (Table 1) and its analysis are sophisticated, and the lower bound is robust to adaptivity and computational power. The upper-bound strategy of item-by-item thresholding with a balance parameter is also interesting. If the proofs are corrected, the paper would constitute a solid contribution to both fair division and query complexity. However, as written, the central upper-bound proof contains a concentration-scale error, and the role of Δ as an algorithm input is not formalized; these issues block acceptance.

major comments (2)
  1. [Appendix C.2.1, Lemma 13 and Eq. (43)–(44)] The proof sets t = m√q log m in the Bernstein bound, but Var[f(c)] ≤ m²/q implies a standard deviation of m/√q, so the correct tail scale is (m/√q) log m. With t = m√q log m, the positive slack term in Lemma 7 is m√q log m, which dominates the negative term -1/5 m^{-3/2} q^{1/2} Δ² for the q in (29). Consequently, the bracketed expression in (43) is positive, and (44) does not follow; multiplying by √q gives -1/5 m^{-3/2} q Δ² + 3 m q log m, which is large and positive. Replacing m√q by m/√q throughout Lemmas 7–9 and the proof of Theorem 4 appears to restore the argument (the ratio becomes 3 when q = 15 m^{5/2} log m / Δ²), but as written the main upper bound is unproved.
  2. [Section 2, Eq. (1); Theorems 2 and 4] Δ is introduced as the '(unknown) optimal negative envy' in Eq. (1), yet the query count q in Theorem 2 and in the more detailed Theorems 4–6 is an explicit function of Δ. No theorem or algorithm statement specifies that the algorithm receives Δ or a known lower bound Δ₀ ≤ Δ. A non-adaptive algorithm cannot compute q = Õ(m^{2.5}/Δ²) without this input, and the parenthetical 'or a lower bound thereof' in the Introduction is never formalized. The authors should either state that Δ₀ is given as input and state the query bound as a function of Δ₀, or provide an adaptive stopping rule that achieves the same scaling without prior knowledge of Δ. As written, the upper-bound half of the Θ claim is not an implementable algorithm.
minor comments (3)
  1. [Appendix C.2.4, proof of Lemma 9] The proof references 'Lemma 21' when bounding the number of items with x_i(c1) ≠ x_i(c2); the correct reference appears to be Lemma 14. A similar cross-reference typo occurs in the proof of Lemma 17 in Section C.4.3, which cites 'Lemma 21' instead of its own analog Lemma 14.
  2. [Section 6, Eq. (7)] The notation q ≤ O(...) is conventional for a lower-bound threshold, but could be confused with an upper bound. Consider writing 'q ≤ c σ m^{2.5}/Δ²' with explicit small constants.
  3. [Abstract] The expression √m/(Δ/m)² might be clearer as m^{2.5}/Δ² directly, since the current form requires one extra step to parse.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the bounds are parameterized by the gap Δ, not fitted to the conclusion.

full rationale

The derivation chain is self-contained. The upper bound (Theorems 2, 4, 5, 6) is a standard parameterized guarantee: the query count q is set algebraically from m, σ, and the gap Δ, and the allocation threshold c is selected from the observed estimates by checking a data-dependent condition (Lemmas 9 and 17); no fitted value is later relabeled as a prediction. The lower bound (Theorems 3 and 7) constructs hard instances whose parameters ε and γ are chosen as explicit functions of m and Δ (Lemma 22 and Section D.6), then applies standard information-theoretic tools (Assouad's lemma, KL chain rule, Berry–Esseen) to show that any algorithm fails. The instance parameters are not chosen from the algorithm's output or from the failure event. The only self-citations (Li et al. 2025; Cai et al. 2023) are either contextual comparisons or standard Bayes-rule lemmas with short proofs, and are not load-bearing for the main claim. The concern that Δ is unknown and q cannot be computed without a lower bound on Δ is an implementability/parameterization issue, not a circular reduction: the theorem states a conditional guarantee in terms of an instance parameter, rather than deriving a prediction from that parameter by construction.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The paper introduces no new physical entities, forces, or conserved quantities. The only hand-chosen scalars are the lower-bound instance parameters ε and γ, which define hard instances rather than fitting data. The main implicit load-bearing assumption is that the algorithm may use Δ (or a lower bound) to choose its query budget, despite Δ being called unknown.

free parameters (2)
  • ε (lower-bound hard instance) = ε = 2(Δ+1)/(m − 2√(log(2/δ)m))
    Chosen by hand in Lemma 22 to make the optimal allocation of the hard instance have envy at most −Δ. It is a construction parameter, not fitted to data.
  • γ (lower-bound hard instance) = γ = 1/2 for Δ=ω(m^{3/4}); γ = c' m^{1/4} ε for Δ=O(m^{3/4})
    Chosen to inflate fluctuations in the second-half items and match the m^{2.5}/Δ² scaling in the two lower-bound regimes. It is a construction parameter, not fitted to data.
assumptions (5)
  • domain assumption Additive utilities with valuations in [0,1]
    The problem setup in Section 2 restricts to additive utilities and [0,1] scaling; the proofs use boundedness for Bernstein/Hoeffding bounds.
  • domain assumption There exists an optimal allocation with envy at most −Δ
    Eq. (1) assumes OptEnvy ≤ −Δ; this gap is necessary for the finite-query results and is not derived.
  • domain assumption Independent additive Gaussian noise N(0,σ²) with known variance
    Eq. (2) defines the query model; the upper-bound algorithms use σ² to set q, and the lower bound is tailored to Gaussian likelihoods.
  • domain assumption The algorithm is given a lower bound on Δ (or knows Δ) to set q
    Theorems 2/5/6 state q in terms of Δ, but Section 2 calls Δ unknown. This implicit assumption is not formalized and is the paper's main modeling gap.
  • standard math Standard probability and information-theory tools hold
    Chernoff, Bernstein, Berry-Esseen, Assouad's lemma, KL chain rule, Hoeffding for sampling without replacement, and Lemma 26 from (Cai et al., 2023) are assumed; they are standard and cited.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Envy-Free Allocation of Indivisible Goods via Noisy Queries." pith.science (2026). https://pith.science/paper/KGNXC235

@misc{pith2026260206361,
  author       = {Pith},
  title        = {Pith review of: Envy-Free Allocation of Indivisible Goods via Noisy Queries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KGNXC235}},
  note         = {Machine review of arXiv:2602.06361}
}
abstract

We introduce a problem of fairly allocating indivisible goods (items) in which the agents' valuations cannot be observed directly, but instead can only be accessed via noisy queries. In the two-agent setting with Gaussian noise and bounded valuations, we derive upper and lower bounds on the required number of queries for finding an envy-free allocation in terms of the number of items, $m$, and the negative-envy of the optimal allocation, $\Delta$. In particular, when $\Delta$ is not too small (namely, $\Delta \gg m^{1/4}$), we establish that the optimal number of queries scales as $\frac{\sqrt m }{(\Delta / m)^2} = \frac{m^{2.5}}{\Delta^2}$ up to logarithmic factors. Our upper bound is based on non-adaptive queries and a simple thresholding-based allocation algorithm that runs in polynomial time, while our lower bound holds even under adaptive queries and arbitrary computation time.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 2 linked inside Pith

  1. [1]

    Addanki, R., Galhotra, S., and Saha, B. (2021). How to design robust algorithms using noisy comparison oracle. Proceedings of the VLDB Endowment , 14(10):1703–1716

    2021

  2. [2]

    A., and Wu, X

    Amanatidis, G., Aziz, H., Birmpas, G., Filos-Ratsikas, A., Li, B., Moulin, H., Voudouris, A. A., and Wu, X. (2023). Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence , 322:103965

    2023

  3. [3]

    Aziz, H. (2020). Developments in multi-agent fair allocation. In AAAI Conference on Artificial Intelligence , pages 13563--13568

    2020

  4. [4]

    Banihashem, K., Hajiaghayi, M., Shin, S., and Slivkins, A. (2023). Bandit social learning: Exploration under myopic behavior. https://arxiv.org/abs/2302.07425

    arXiv 2023

  5. [5]

    and Maillard, O.-A

    Bardenet, R. and Maillard, O.-A. (2015). Concentration inequalities for sampling without replacement. Bernoulli , 21(3):1361--1385

    2015

  6. [6]

    Barman, S., Khan, A., Maiti, A., and Sawarni, A. (2023). Fairness and welfare quantification for regret in multi-armed bandits. In AAAI Conference on Artificial Intelligence , pages 6762--6769

    2023

  7. [7]

    W., and Tawarmalani, M

    Bhattacharya, R., Nguyen, T., Sun, W. W., and Tawarmalani, M. (2024). Active learning for fair and stable online allocations. In ACM Conference on Economics and Computation , pages 196--197

    2024

  8. [8]

    Bu, X., Li, Z., Liu, S., Song, J., and Tao, B. (2024). Logarithmic comparison-based query complexity for fair division of indivisible goods. In Conference on Web and Internet Economics , pages 348--365

    2024

Show all 39 references
  1. [9]

    T., and Scarlett, J

    Cai, X., Lam, C. T., and Scarlett, J. (2023). On average-case error bounds for kernel-based B ayesian quadrature. Transactions on Machine Learning Research

    2023

  2. [10]

    Duchi, J. (2023). Lecture notes on statistics and information theory. https://web.stanford.edu/class/stats311/lecture-notes.pdf

    2023

  3. [11]

    Feige, U., Raghavan, P., Peleg, D., and Upfal, E. (1994). Computing with noisy information. SIAM Journal on Computing , 23(5):1001--1018

    1994

  4. [12]

    Harada, T., Ito, S., and Sumita, H. (2025). Bandit max-min fair allocation. In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases , pages 380--397

    2025

  5. [13]

    Hossain, S., Micha, E., and Shah, N. (2021). Fair algorithms for multi-agent multi-armed bandits. In Advances in Neural Information Processing Systems , pages 24005--24017

    2021

  6. [14]

    and Szepesv \'a ri, C

    Lattimore, T. and Szepesv \'a ri, C. (2020). Bandit algorithms . Cambridge University Press

    2020

  7. [15]

    Li, F., Liu, J., and Ji, B. (2019). Combinatorial sleeping bandits with fairness constraints. IEEE Transactions on Network Science and Engineering , 7(3):1799--1813

    2019

  8. [16]

    Li, Z., Manurangsi, P., Scarlett, J., and Suksompong, W. (2025). Complexity of round-robin allocation with potentially noisy queries. Information and Computation , 306:105332

    2025

  9. [17]

    Lim, E., Tan, V. Y. F., and Soh, H. (2024). Stochastic bandits for egalitarian assignment. Transactions on Machine Learning Research

    2024

  10. [18]

    and Raghavan, P

    Motwani, R. and Raghavan, P. (2010). Randomized Algorithms . Chapman & Hall/CRC

    2010

  11. [19]

    Moulin, H. (2019). Fair division in the internet age. Annual Review of Economics , 11:407--441

    2019

  12. [20]

    D., and Suksompong, W

    Oh, H., Procaccia, A. D., and Suksompong, W. (2021). Fairly allocating many goods with few queries. SIAM Journal on Discrete Mathematics , 35(2):788--813

    2021

  13. [21]

    Patil, V., Ghalme, G., Nair, V., and Narahari, Y. (2021). Achieving fairness in the stochastic multi-armed bandit problem. Journal of Machine Learning Research , 22(174):1--31

    2021

  14. [22]

    D., and Zhu, D

    Peters, D., Procaccia, A. D., and Zhu, D. (2022). Robust rent division. In Advances in Neural Information Processing Systems , pages 13864--13876

    2022

  15. [23]

    Petrov, V. V. (1995). Limit Theorems of Probability Theory: Sequences of Independent Random Variables . Oxford University Press

    1995

  16. [24]

    and Roughgarden, T

    Plaut, B. and Roughgarden, T. (2020a). Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics , 34(2):1039--1068

  17. [25]

    and Roughgarden, T

    Plaut, B. and Roughgarden, T. (2020b). Communication complexity of discrete fair division. SIAM Journal on Computing , 49(1):206--2431068

  18. [26]

    and Wu, Y

    Polyanskiy, Y. and Wu, Y. (2025). Information Theory: From Coding to Learning . Cambridge University Press

    2025

  19. [27]

    D., Schiffer, B., and Zhang, S

    Procaccia, A. D., Schiffer, B., and Zhang, S. (2024). Honor among bandits: No-regret learning for online fair division. In Advances in Neural Information Processing Systems , pages 13183--13227

    2024

  20. [28]

    and Vannella, F

    Russo, A. and Vannella, F. (2024). Fair best arm identification with fixed confidence. In IEEE Conference on Decision and Control , pages 1173--1180

    2024

  21. [29]

    Sawarni, A., Pal, S., and Barman, S. (2023). Nash regret guarantees for linear bandits. In Advances in Neural Information Processing Systems , pages 33288--33318

    2023

  22. [30]

    and Zhang, S

    Schiffer, B. and Zhang, S. (2025). Improved regret bounds for online fair division with bandit learning. In AAAI Conference on Artificial Intelligence , pages 14079--14086

    2025

  23. [31]

    Sinha, A., Joshi, A., Bhattacharjee, R., Musco, C., and Hajiesmaili, M. (2023). No-regret algorithms for fair resource allocation. In Advances in Neural Information Processing Systems , pages 48083--48109

    2023

  24. [32]

    Sui, Y., Zoghi, M., Hofmann, K., and Yue, Y. (2018). Advancements in dueling bandits. In International Joint Conference on Artificial Intelligence , pages 5502--5510

    2018

  25. [33]

    Suksompong, W. (2021). Constraints in fair division. ACM SIGecom Exchanges , 19(2):46--61

    2021

  26. [34]

    Talebi, M. S. and Proutiere, A. (2018). Learning proportionally fair allocations with low regret. Proceedings of the ACM on Measurement and Analysis of Computing Systems , 2(2):36:1--36:31

    2018

  27. [35]

    Verma, A., Saha, I., Yokoo, M., and Low, B. K. H. (2024). Keep everyone happy: Online fair division of numerous items with few copies. https://arxiv.org/abs/2408.12845

    2024 arXiv

  28. [36]

    Vershynin, R. (2018). High-Dimensional Probability: An Introduction with Applications in Data Science . Cambridge University Press

    2018

  29. [37]

    Walsh, T. (2020). Fair division: the computer scientist's perspective. In International Joint Conference on Artificial Intelligence , pages 4966--4972

    2020

  30. [38]

    Yamada, H., Komiyama, J., Abe, K., and Iwasaki, A. (2024). Learning fair division from bandit feedback. In International Conference on Artificial Intelligence and Statistics , pages 3106--3114

    2024

  31. [39]

    Zhu, B., Wang, Z., Ghaddar, N., Jiao, J., and Wang, L. (2023). On the optimal bounds for noisy computing. In IEEE International Symposium on Information Theory , pages 1788--1793

    2023

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.