REVIEW 3 major objections 4 minor
Computing Approximately Proportional Allocations of Indivisible Goods: Beyond Additive and Monotone Valuations
T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read This paper extends approximate proportional fairness (PROP1) to non-monotone, satiating valuations, showing that EF1 implies PROP1 for submodular goods and that PROP1 allocations can be computed efficiently for subadditive goods.
desk verdict Plausible and genuinely novel extension of PROP1 to satiating submodular/subadditive valuations, but the exact definition of PROP1 under negative marginal values is the load-bearing detail we can't see from the abstract. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing mechanism is the implication EF1 ⇒ PROP1 in the satiating submodular setting, combined with the round-robin procedure and envy-cycle elimination algorithm. Satiating goods are modeled by non-negative valuation functions that need not be monotone, so the definition of the 'up to one good' relaxation, applied when adding a good can decrease utility, is what carries the proofs.
What would settle it
Brute-force search over small satiating submodular instances could check whether every EF1 allocation satisfies $v_i(A_i)+v_i(g)\ge v_i(M)/n$ for some good $g$; a single violation would refute the main implication.
Extended reading notes
Core claim
The paper's central claim is that PROP1 remains attainable when valuations satiate. For submodular satiating valuations, it proves that every EF1 allocation is PROP1, so PROP1 exists whenever EF1 exists; for monotone submodular valuations, Envy-Cycle Elimination gives such an allocation in polynomial time. A round-robin procedure yields a partial PROP1 allocation for satiating submodular goods after the second-to-last round and a complete PROP1 allocation for monotone submodular valuations. For the broader class of satiating subadditive valuations, a separate polynomial-time algorithm computes a PROP1 allocation. The paper also shows that maximum Nash welfare allocations are PROP1 for monoto
Load-bearing premise
The main results depend on the paper's specific adaptation of PROP1 to valuations with negative marginal values; if that adaptation is weaker than the standard fair-share interpretation, the guarantees may be less meaningful than they appear.
Editorial extensions
If this is right
- For satiating submodular valuations, any future EF1 existence result automatically becomes a PROP1 result, collapsing the two fairness notions for that class.
- Round-robin and Envy-Cycle Elimination compute PROP1 allocations in polynomial time for monotone submodular instances, giving simple practical algorithms.
- PROP1 allocations are polynomial-time computable for satiating subadditive valuations, a broader class than monotone submodular.
- Maximum Nash welfare allocations carry a PROP1 guarantee for monotone submodular goods, adding to the known fairness profile of MNW allocations.
Reading between the lines
- Editorial inference: The proof that EF1 implies PROP1 under submodularity may extend to other one-good relaxations, such as envy-freeness up to any good, if the satiating-good definition is handled in the same way.
- Editorial inference: The paper's PROP1 definition for non-monotone valuations could serve as a fairness benchmark in market-design applications where agents' utilities satiate, without requiring monotonicity.
- Editorial inference: A natural stress test is whether the subadditive algorithm also provides other guarantees, such as a bounded envy ratio, since non-monotone subadditive instances can have large envy.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies proportionality up to one good (PROP1) for allocations of indivisible goods when valuations are non-additive and possibly non-monotone. It introduces instances with satiating goods, where valuations are non-negative but may have negative marginal values. The abstract claims four results: (1) EF1 implies PROP1 for submodular valuations over satiating goods, and for monotone submodular valuations this yields existence and efficient computation via Envy-Cycle Elimination; (2) Round-Robin computes a partial PROP1 allocation after the second-to-last round for satiating submodular goods, and a complete PROP1 allocation for monotone submodular valuations; (3) PROP1 allocations for satiating subadditive goods can be computed in polynomial time; and (4) maximum Nash welfare allocations are PROP1 for monotone submodular goods. The abstract frames these as extensions well beyond additive and monotone valuations, but the full text and proofs are not available for verification.
Significance. If the claims are correct, the paper would substantially broaden the scope of approximate proportionality in fair division. PROP1 is a natural but less studied notion than EF1, and extending it to satiating/non-monotone valuations with polynomial-time algorithms would be a meaningful contribution. The abstract states precise, falsifiable results and connects them to known algorithmic techniques (Round-Robin, Envy-Cycle Elimination, maximum Nash welfare), which is a strength. However, the central definition of PROP1 for non-monotone valuations is not given, and no proofs are available. The significance therefore cannot be fully assessed from the submitted material.
major comments (3)
- [Abstract, first bullet] The definition of PROP1 for valuations with negative marginal values is not stated. In the additive case, PROP1 means that there exists a good g such that v_i(A_i) + v_i(g) ≥ v_i(N)/n. For non-monotone valuations, this existence condition is much stronger than the common non-additive relaxation v_i(A_i) ≥ v_i(N)/n − max_g v_i({g}). The EF1 ⇒ PROP1 implication is load-bearing and depends entirely on which variant is used. Please state the exact definition and prove the theorems against it; otherwise the headline extension beyond additive and monotone valuations may rest on a definitional choice.
- [Abstract, bullets 1–3] The proofs are omitted from the available material. The central technical claims—especially the handling of negative marginal values in the submodular implication, the definition of 'partial PROP1,' and the polynomial-time algorithm for satiating subadditive goods—cannot be checked. In particular, the claim that Round-Robin computes a 'partial PROP1 allocation after the second-to-last round' requires a precise definition of partial PROP1 and an explanation of why the second-to-last round is the relevant stopping point. These are not presentation details; they are the core content of the paper.
- [Abstract, bullets 1–2] The exact scope of the existence claim is unclear. Bullet 1 says EF1 implies PROP1 for submodular valuations over satiating goods, but the efficient computation via Envy-Cycle Elimination is stated only for monotone submodular valuations. Bullet 2 says Round-Robin computes only a partial PROP1 allocation for satiating submodular goods. Is there a complete PROP1 existence guarantee for all satiating submodular valuations, and if so, by which algorithm? If not, the first bullet's 'ensuring existence' is qualified in a way that the abstract does not make precise.
minor comments (4)
- [Abstract] The notion of 'satiating goods' is not defined. The phrase 'non-negative valuation functions that need not be monotone, allowing for negative marginal values' suggests that adding a satiating good can decrease utility, but a formal definition and, if available, a citation to prior work would help.
- [Abstract, last bullet] For maximum Nash welfare allocations, the abstract states only that they are PROP1 for monotone submodular goods. Please clarify whether existence and efficient computation are known or assumed, and define MNW in this setting.
- [Abstract, last bullet] The phrase 'unreasonable fairness' appears to be a quotation; it should be attributed (e.g., to Caragiannis et al., 2016) or removed.
- [Abstract] The phrase 'seemingly simpler fairness concept' is vague. A brief reference to prior PROP1 literature would better frame the contribution.
Circularity Check
No circularity detected in the abstract; the claims are presented as new implications from standard definitions and algorithmic constructions.
full rationale
This is an abstract-only review. The abstract derives EF1 implies PROP1 for submodular satiating valuations, gives algorithmic results for PROP1, and connects MNW to PROP1. There is no evidence of a parameter fitted to data and then called a prediction, no definition of the target result built into the assumptions, and no load-bearing self-citation. The only potentially fragile point is the exact definition of PROP1 for non-monotone valuations with negative marginal values, but that is a modeling/definitional choice, not circular reasoning: the claimed implications are stated as mathematical consequences of the authors' chosen definitions, and the abstract does not show that any conclusion is equivalent to an input by construction. Without the full text, one cannot check the proofs, but absence of visible circularity is the appropriate finding. A reader's concern about weaker-than-expected PROP1 variants would be a correctness or interpretation issue, not circularity. Therefore the circularity score is 0.
Assumptions & free parameters
assumptions (4)
- domain assumption Agent valuations are non-negative functions over bundles of goods.
- domain assumption Satiating goods are modeled by non-monotone valuations that allow negative marginal values.
- standard math Submodular and subadditive functions are defined in the standard set-function sense.
- ad hoc to paper The definition of PROP1 for non-monotone valuations is a natural extension of the additive definition, even when adding a good can reduce utility.
Cite this review
Pith. "Pith review of Computing Approximately Proportional Allocations of Indivisible Goods: Beyond Additive and Monotone Valuations." pith.science (2026). https://pith.science/paper/L532TBW2
@misc{pith2026250812453,
author = {Pith},
title = {Pith review of: Computing Approximately Proportional Allocations of Indivisible Goods: Beyond Additive and Monotone Valuations},
year = {2026},
howpublished = {\url{https://pith.science/paper/L532TBW2}},
note = {Machine review of arXiv:2508.12453}
}
read the original abstract
Although approximate notions of envy-freeness-such as envy-freeness up to one good (EF1)-have been extensively studied for indivisible goods, the seemingly simpler fairness concept of proportionality up to one good (PROP1) has received far less attention. For additive valuations, every EF1 allocation is PROP1, and well-known algorithms such as Round-Robin and Envy-Cycle Elimination compute such allocations in polynomial time. PROP1 is also compatible with Pareto efficiency, as maximum Nash welfare allocations are EF1 and hence PROP1. We ask whether these favorable properties extend to non-additive valuations. We study a broad class of allocation instances with {\em satiating goods}, where agents have non-negative valuation functions that need not be monotone, allowing for negative marginal values. We present the following results: - EF1 implies PROP1 for submodular valuations over satiating goods, ensuring existence and efficient computation via Envy-Cycle Elimination for monotone submodular valuations; - Round-robin computes a partial PROP1 allocation after the second-to-last round for satiating submodular goods and a complete PROP1 for monotone submodular valuations; - PROP1 allocations for satiating subadditive goods can be computed in polynomial-time; - Maximum Nash welfare allocations are PROP1 for monotone submodular goods, revealing yet another facet of their ``unreasonable fairness.''
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.