{"id":"2edfde3c-2c6e-4daf-8b7a-ca7ce249488a","arxiv_id":"2508.12453","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"EF1 implies PROP1 for submodular valuations with satiating goods, and PROP1 allocations are polynomial-time computable for satiating subadditive goods.","lead":"Fair sharing rules usually assume people always want more of every item, but real tastes can become saturated. This paper proves that common algorithms still deliver approximately fair shares for a broad class of such non-monotone preferences.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"PROP1's exact 'up to one good' relaxation for satiating, non-monotone valuations is not stated in the abstract; if it is the usual max-singleton-deficiency version rather than an existence-of-addition version, the headline implications may be weaker than they appear.","rationale":"The reader's weakest-assumption analysis identified exactly the load-bearing point: the behavior of PROP1 when marginal values are negative is not specified in the abstract, and the stated implications may be vacuous or much weaker under a non-standard adaptation. My stress-test agrees. Since the full text is unavailable, the appropriate disposition remains UNVERDICTED rather than ACCEPT or REJECT; the concern is a precise, checkable condition that should be settled from the definitions and proofs. I therefore recommend no change to the reader's verdict. The concrete test is designed to discriminate between the strong existence-based PROP1 and the weaker deficiency-based PROP1, and to determine whether the claimed EF1⇒PROP1 theorem and the algorithmic guarantees actually hold for the stronger notion or only for the weaker one.","tokens_in":800,"tokens_out":17020,"duration_ms":211703,"concrete_test":"Obtain the full text and locate the formal definition of PROP1 (expected in Section 2). Then run a brute-force verification over all normalized non-negative submodular valuations on a 4-good instance (enumerated value oracle) and all complete EF1 allocations. For each allocation, test the standard existence version: ∃g∉A_i with v_i(A_i∪{g}) ≥ v_i(N)/n. If any complete EF1 allocation fails this test, Theorem 1 cannot be using the standard additive-style PROP1, and the paper's version must be the weaker max-singleton-deficiency relaxation. Also record, for each such counterexample, whether the paper's definition is satisfied, to determine whether the contribution is a new fairness guarantee or a redefinition of the target.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that EF1 implies PROP1 for submodular valuations over satiating goods, and that PROP1 allocations can be computed efficiently for satiating subadditive goods. Everything else rests on this implication. The abstract never defines PROP1 for valuations with negative marginal values. In the additive setting, PROP1 means that some outside good can be added to reach the proportional share: v_i(A_i) + v_i(g) ≥ v_i(N)/n. For satiating valuations, this existence condition is substantially stronger than the common non-additive relaxation v_i(A_i) ≥ v_i(N)/n − max_g v_i({g}), and it is stronger still than a version phrased in terms of the maximum marginal value, which may be negative. If the paper uses the max-singleton-deficiency version, then the theorem can hold even though no single good actually brings the agent up to her proportional share; the advertised continuation 'beyond additive and monotone valuations' then depends on a definitional choice. The proofs must be checked to see which PROP1 variant is operative, and whether the efficient algorithms are shown to satisfy that variant or a weaker one.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":1125,"tokens_out":3369,"duration_ms":38917,"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":[{"comment":"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.","section":"Abstract, first bullet"},{"comment":"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.","section":"Abstract, bullets 1–3"},{"comment":"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.","section":"Abstract, bullets 1–2"}],"minor_comments":[{"comment":"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.","section":"Abstract"},{"comment":"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.","section":"Abstract, last bullet"},{"comment":"The phrase 'unreasonable fairness' appears to be a quotation; it should be attributed (e.g., to Caragiannis et al., 2016) or removed.","section":"Abstract, last bullet"},{"comment":"The phrase 'seemingly simpler fairness concept' is vague. A brief reference to prior PROP1 literature would better frame the contribution.","section":"Abstract"}],"recommendation":"uncertain","confidential_remarks":"The submission as provided is abstract-only; I could not verify any of the proofs. The main risk is the definition of PROP1 for non-monotone valuations: if the paper uses the max-singleton-deficiency variant, the advertised implications may be weaker than they first appear. I would be willing to review the full manuscript if it is made available."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The takeaway: this paper looks like a real extension of PROP1 results beyond additive and monotone valuations, but the crucial definition of PROP1 for non-monotone satiating goods is not stated in the abstract, and that's the one thing that could make the headline claims weaker than advertised.\n\nWhat's new and good: the question is natural – do the additive-valuation results (EF1 ⇒ PROP1, Round-Robin and Envy-Cycle Elimination compute PROP1, MNW is PROP1) survive when agents have non-monotone but non-negative valuations over satiating goods? The four bullet results are plausible and, if correct, more than incremental: they cover submodular and subadditive classes, and the partial-PROP1 result after the second-to-last round is a neat nuance. The MNW connection for monotone submodular valuations also reinforces the \"unreasonable fairness\" theme. No flags on circularity or data fitting – this is standard theory.\n\nSoft spots: the main one is exactly what the stress-test note flags. For additive valuations, PROP1 has a clean existential form: v_i(A_i) + v_i(g) ≥ v_i(N)/n for some good g. With satiating, non-monotone goods, adding a good can decrease value, so that existential version is much stronger than the max-singleton-deficiency relaxation v_i(A_i) ≥ v_i(N)/n − max_g v_i({g}). If the paper uses the deficiency version for non-monotone valuations, then the headline \"EF1 implies PROP1\" could hold trivially or with a weaker guarantee than a reader would assume. The abstract doesn't define which variant is operative. That's a load-bearing definitional choice, and the proofs need to show which one the algorithms satisfy.\n\nThe other limitation is mine as much as the paper's: I've only seen the abstract, so I can't verify the technical claims. That said, nothing in the statements looks off, and the authors are working in a well-trodden area with standard definitions.\n\nVerdict: worth sending to a serious referee. The referee should pin down the PROP1 definition early, check whether the algorithms guarantee the strong or weak variant, and make sure the submodular existence claims actually cover non-monotone cases. If the definition is the standard one, the paper is likely a solid, useful contribution. I'd want the full text before citing it, but I'd be glad to see it in a reading group.\n\nRecommendation: engage with it – desk rejection would be wrong.","headline":"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.","tokens_in":1540,"tokens_out":2443,"would_cite":false,"duration_ms":26799,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["fair division","indivisible goods","PROP1","EF1","submodular valuations","subadditive valuations","satiating goods","non-monotone valuations"],"falsifier":"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.","tokens_in":741,"feed_emoji":"🍰","tokens_out":8164,"duration_ms":81936,"temperature":0.7,"pith_summary":"This paper asks whether proportional fairness up to one good — a guarantee that holds for additive valuations — still holds when goods can satiate agents, meaning valuation functions are non-negative but not necessarily monotone and may have negative marginal values. It asserts that for submodular valuations over satiating goods, every envy-free-up-to-one-good allocation is also proportional-up-to-one-good, and that this gives existence and efficient computation via Envy-Cycle Elimination for monotone submodular valuations. It also claims round-robin produces a partial PROP1 allocation for satiating submodular goods and a complete one for monotone submodular valuations, and that PROP1 allocations for satiating subadditive goods can be computed in polynomial time. If these claims hold, approximate proportionality is not limited to additive preferences, which matters because satiation and non-monotonicity are common in real-world allocation settings.","feed_headline":"Proportional fairness up to one good survives non-additive valuations","feed_subtitle":"EF1 implies PROP1 for satiating submodular goods; PROP1 is poly-time for subadditive ones.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[],"fun_headline_variants":["Satiating goods don't break fair allocation: PROP1 exists","Fair division: PROP1 holds for non-additive valuations","PROP1 achievable for satiating goods in polynomial time","Beyond additive: EF1 implies PROP1 for submodular goods","Proportionality up to one good survives satiating items"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Satiating goods don't break fair allocation: PROP1 exists","Fair division: PROP1 holds for non-additive valuations","PROP1 achievable for satiating goods in polynomial time","Beyond additive: EF1 implies PROP1 for submodular goods","Proportionality up to one good survives satiating items"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000199,"raw_usage":{"total_tokens":1236,"prompt_tokens":800,"completion_tokens":436,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":544,"completion_tokens_details":{"reasoning_tokens":351}},"tokens_in":544,"tokens_out":436,"duration_ms":5836,"temperature":1.0,"reasoning_tokens":351,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T19:25:13.173500+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}