{"id":"1aff30bd-dcb8-4690-b486-f5ef888288a9","arxiv_id":"2411.12696","paper_version":4,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper defines weighted-envy-freeable allocations, proves a no-positive-cycle characterization, and gives polynomial-time subsidy bounds for general, identical, and binary additive valuations; the general-additive proof has gaps.","lead":"This paper studies how much third-party money is needed to make allocations of indivisible items envy-free when agents have different entitlements, and gives polynomial-time algorithms with worst-case subsidy bounds for three valuation settings. It introduces weighted-envy-freeable allocations and shows the unweighted characterization fails once weights differ.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The general-additive bound in Theorem 3.16 rests on Proposition 3.13's Case 3, where the constructed random allocation B^t is not a feasible complete allocation of O_t; as written the modified-valuation bridge fails, so the central (W-w1)V subsidy bound is unsupported.","rationale":"Read in good faith, the paper has solid contributions: Theorem 3.2's cycle characterization is correctly argued, and the identical/binary sections (Theorems 4.7 and 5.13) are self-contained and plausible. The central general-additive result, however, is exactly the point that depends on the modified-valuation bridge. The reader's weakest-assumption diagnosis is on target: Proposition 3.14 misses the w_i factor but is easily corrected; the Case 3 construction in Proposition 3.13 is not. Tracking bundle cardinalities and item ownership in Case 3 shows the constructed B^t is either incomplete or includes an extra item not present in A^t, so it cannot be compared with A^t under the max-weight matching optimality. No proof of the round-wise non-positive modified cycles remains in the text. This does not mean the theorem is false; the argument may be repairable by a different exchange or by a summed-over-rounds argument. But as written the (W-w1)V bound is unsupported, so the reader's moderate-confidence REJECT is justified. My read does not change the verdict.","tokens_in":27739,"tokens_out":31361,"duration_ms":308360,"concrete_test":"Recompute the Case 3 construction on an explicit 3-cycle (i1,i2,i3) with weights, say, (1,2,2), following the literal steps of Proposition 3.13: transfer one item from i2 to i1 and from i3 to i2, remove one item from i1, and add one future item to i2. Count each bundle's size and the set of items left unassigned. If B^t is not a complete allocation of O_t with |B^t_i|=w_i, then the expected-value identity displayed in the proof cannot hold and Proposition 3.13 is unproven; that is the load-bearing step for Theorem 3.16.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 3.13 is the step that converts the per-round optimal matching of Algorithm 1 into WEF-ability under the modified valuations; without it Theorem 3.16 has no bridge to Propositions 3.14-3.15. In Case 3 the proof decomposes a positive modified-cost cycle into paths and constructs B^t by (1) transferring an item from i_{j+1} to i_j for each 1≤j≤k-1, (2) removing an item from i_1, and (3) adding a future item from A^{t+1}_{i_{k-1}} to i_{k-1}. The displayed expectation sums only j=1,...,k-2 plus the future/own-item term, so under the literal step (1) the transfer i_k->i_{k-1} and the loss of an item by i_k are not accounted for. If step (1) is read instead as j=1,...,k-2, then the item removed from i_1 has no recipient and the future item makes B^t use an item that was not allocated in A^t; in either reading B^t is not a complete allocation of O_t with each agent receiving exactly w_i items, the only class over which Algorithm 1 is optimal. Hence the contradiction with optimality does not follow. The separate missing w_i factor in Proposition 3.14 is a repairable statement error, but the Case 3 infeasibility is a genuine gap in the central proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a weighted extension of envy-freeness with subsidies: agents have entitlements (weights), and an allocation is WEF-able if subsidies can make it weighted envy-free. The authors prove a weighted analogue of the Halpern-Shah no-positive-cycle characterization (Theorem 3.2), give a worst-case subsidy bound for a fixed WEF-able allocation (Theorem 3.6), and present polynomial-time algorithms with subsidy bounds for three additive valuation settings: general additive valuations (Algorithm 1, Theorem 3.16), identical additive valuations (Algorithm 2, Theorem 4.7), and binary additive valuations via an adapted General Yankee Swap (Algorithm 3, Theorem 5.13). The claimed general-additive bound is (W-w1)V/gcd(w) after normalization, reducing to (n-1)V for equal weights.","tokens_in":28036,"tokens_out":11147,"duration_ms":108294,"significance":"The characterization in Theorem 3.2 and the fixed-allocation bound in Theorem 3.6 are clean and genuinely extend the unweighted theory. The identical-valuations section (Section 4) and the binary-valuations section (Section 5) are detailed and, if correct, give tight or near-tight bounds that reduce properly to known unweighted results. The general-additive result of Section 3.2 is the main advertised contribution, but its proof currently has a load-bearing gap: Proposition 3.13's Case 3 constructs an infeasible allocation, and the modified-valuation bridge in Propositions 3.14-3.15 does not support the stated per-agent bound as written. Because that bridge is what supplies Theorem 3.16, the paper is not yet publishable in its present form, although the other sections are substantial enough that a careful revision is warranted.","major_comments":[{"comment":"The random allocation B^t constructed to contradict the optimality of A^t is not a feasible complete allocation of O_t with exactly w_i items per agent. Step (1) says to transfer an item from i_{j+1} to i_j for every 1 <= j <= k-1, which includes the transfer i_k -> i_{k-1}; step (2) removes an item from i_1; step (3) adds an item from A^{t+1}_{i_{k-1}} to i_{k-1}. Under this reading i_k ends with w_{i_k}-1 items and i_{k-1} ends with w_{i_{k-1}}+1 items, one of which is not in O_t. If step (1) is instead read as ranging only over j <= k-2, then the item removed from i_1 has no recipient, and again B^t is not an allocation of O_t. The displayed expectation also omits the transfer i_k -> i_{k-1}, so the claimed equality with the cost of the path P does not match the stated construction. Since Algorithm 1 is only optimal over complete allocations of O_t in which each agent receives exactly w_i items, the contradiction with optimality does not follow. This invalidates the proof of Proposition 3.13 and hence the WEF-ability under modified valuations used in Theorem 3.16.","section":"Section 3.2, Proposition 3.13, Case 3"},{"comment":"The comparison between the original and modified subsidy requirements is not justified as stated. Observation 3.12 gives, for each edge, \\bar v_i(A_j)-\\bar v_i(A_i) >= v_i(A_j)/w_j - v_i(A_i)/w_i, so the modified-cost of a path is at least the original weighted path cost. Therefore the original subsidy w_i * ell_i^v is at most w_i times the modified subsidy, not at most the modified subsidy as Proposition 3.14 claims when the modified graph is taken with unit weights. Separately, Proposition 3.15 evaluates \\bar v_i(A_j) as \\sum_{t in [T]} \\bar v_i(A^t_j), but \\bar v_i is defined only on round bundles and is not item-additive as defined; this summation requires an explicit definition of \\bar v_i on final bundles. Both points affect the per-agent bound w_i V claimed in Theorem 3.16.","section":"Section 3.2, Propositions 3.14 and 3.15"}],"minor_comments":[{"comment":"The sentence 'After at most ⌈m/W⌉ valuations, all items are allocated' should say 'iterations' rather than 'valuations'.","section":"Section 3.2, after Algorithm 1"},{"comment":"The telescoping display in the proof of Lemma 4.3 has a typographical error: the final sum is written as a difference of two identical terms, which obscures the intended cancellation.","section":"Section 4, Lemma 4.3, Equation (2)"},{"comment":"In step 4 of Example 4.4, the value of the envy is computed as 3/(7/2) = 6/7, but the displayed expression omits the subtraction of the zero term for the empty bundle; this is harmless but should be cleaned up.","section":"Example 4.4"},{"comment":"The main theorem and Table 1 state the total bound as (W-w1)V, while Lemma 3.17 proves the stronger (W-w1)V/gcd(w) after dividing all weights by their gcd; the statements should be reconciled, for example by stating the normalization explicitly in the theorem.","section":"Theorem 3.16 and Table 1"}],"recommendation":"major_revision","confidential_remarks":"The reader's rejection is grounded in a real gap: the Case 3 construction in Proposition 3.13 is infeasible as written, and Proposition 3.14 has a missing factor of w_i under the unit-weight reading. I recommend major revision rather than rejection because the no-positive-cycle characterization, the fixed-allocation bound, and the identical- and binary-valuation sections are independent, substantial contributions, and the general-additive proof may be repairable with a correct cardinality-preserving construction and a careful statement of the modified-valuation bridge. The authors should also clarify whether the modified valuation is meant to be additive across rounds and whether the modified graph is weighted by the original weights or by unit weights."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper starts well: it introduces WEF-ability, proves the natural no-positive-cycle characterization (Theorem 3.2), and shows convincingly that the unweighted EF-ability results do not carry over (Example 1.1). The given-allocation subsidy bound (Theorem 3.6) and the lower bound (Theorem 3.9) are clean. The identical-valuation and binary-valuation sections are detailed and, as far as I can see, correct; Algorithm 2 and the Yankee-Swap adaptation are substantive and worth having.\n\nThe problem is the main general-additive result, Theorem 3.16. The bridge used to prove it is Propositions 3.13-3.15, and Proposition 3.13's Case 3 does not work. The proof constructs a random allocation B^t by transferring items along a path, removing an item from i_1, and adding a future item from A^{t+1}_{i_{k-1}}. But the displayed expectation does not match the construction: if the transfers run over all j=1..k-1, then i_k loses an item and i_{k-1} gains two items (one from i_k and one future), so B^t is not an allocation of the current item set O_t with each agent receiving exactly w_i items; if the transfers are only up to k-2, then the item removed from i_1 is unaccounted for and the future item is still outside O_t. In either reading, B^t is infeasible for the class over which Algorithm 1 is optimal, so the contradiction with optimality does not follow. This is a load-bearing gap, not a typo.\n\nProposition 3.14 is also misstated: the proof only gives s_i <= w_i * s'_i, missing the factor w_i. That one is easily repaired and does not affect the final bound, but it should be flagged.\n\nMy overall take: the conceptual framework and the special-case algorithms are solid and will be useful. The general-additive theorem is unsupported as written, and fixing the Case 3 argument may require a genuinely different idea. I would send this to a serious referee, but with the understanding that the general result needs major repair. For a reading group, the paper is worth discussing precisely because the gap is instructive.","headline":"Solid conceptual contribution with a clean WEF-ability characterization, but the headline general-additive subsidy bound has a real proof gap in Proposition 3.13's Case 3; the identical and binary results look good.","tokens_in":28585,"tokens_out":6171,"would_cite":true,"duration_ms":54940,"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":"An allocation can be made weighted-envy-free with subsidies exactly when its weighted envy graph has no positive-cost cycles, and three polynomial-time algorithms bound the required subsidy.","keywords":["weighted envy-freeness","subsidies","indivisible items","fair division","additive valuations","binary valuations","envy graph","polynomial-time algorithm"],"falsifier":"Take a small additive instance with integer weights, run Algorithm 1, and compute the true minimal subsidy for its output via Theorem 3.5 (longest paths in the weighted envy graph). If any agent's minimal subsidy exceeds $w_i V$, or the total exceeds $(W-w_1)V$, the main general-additive theorem is false; comparing the original and modified-valuation longest-path costs also directly tests Proposition 3.14.","tokens_in":27529,"feed_emoji":"⚖️","tokens_out":8951,"duration_ms":78519,"temperature":0.7,"pith_summary":"The paper asks how much third-party money is needed to make an allocation of indivisible items envy-free when agents have different entitlements, or weights. It establishes that an allocation can be made weighted-envy-free with subsidies if and only if its weighted envy graph has no positive-cost cycles, and that the minimal subsidy vector is obtained from longest paths in that graph. For agents with additive valuations, it gives three polynomial-time algorithms: one for general valuations (integer weights) with per-agent subsidy at most $w_i V$ and total at most $(W-w_1)V$; one for identical valuations with per-agent subsidy at most $V$ and total at most $(n-1)V$; and one for binary valuations with per-agent subsidy at most $w_i/w_1$ and total at most $W/w_1-1$. When all weights are equal, these bounds reduce to the known unweighted bounds, so the weighted setting generalizes the earlier theory while exposing that welfare-maximizing reassignments no longer characterize envy-freeability.","feed_headline":"Capped subsidies guarantee weighted envy-free allocation","feed_subtitle":"Three polynomial-time algorithms cover general, identical, and binary valuations, matching known unweighted bounds when weights are equal.","key_machinery":"The carrying object is the weighted envy graph $G_{A,w}$, a complete directed graph on agents with edge cost $\\operatorname{cost}_A(i,j)=v_i(A_j)/w_j-v_i(A_i)/w_i$. The load-bearing theorem is that an allocation is WEF-able iff every directed cycle has non-positive total cost; the minimal subsidy vector is then $s_i = w_i \\cdot \\ell_i(A)$, where $\\ell_i(A)$ is the maximum cost of a path starting at $i$. Each algorithm is engineered so its output avoids positive-cost cycles: Algorithm 1 via one-to-many maximum-value matching, Algorithm 2 via an item-by-item rule minimizing $v(A_i\\cup\\{o\\})/w_i$, and Algorithm 3 via a weighted General Yankee Swap that preserves non-redundancy and bounds longest-path costs.","core_discovery":"The central discovery is that weighted envy-freeability is exactly the absence of positive-cost cycles in the weighted envy graph, in which the edge from $i$ to $j$ costs $v_i(A_j)/w_j - v_i(A_i)/w_i$. Unlike the unweighted case, an allocation that maximizes utilitarian (or weighted utilitarian) welfare over reassignments need not be WEF-able, and a WEF-able allocation need not maximize welfare. The paper proves the characterization, shows how to compute a componentwise-minimal subsidy vector in strongly polynomial time, and then designs allocation algorithms whose weighted envy graphs are guaranteed to be cycle-free with controlled path lengths. The resulting bounds are $(W-w_1)V$ for general additive valuations with integer weights (improved by dividing by $\\gcd(w)$), $(n-1)V$ for identical additive valuations, and $W/w_1-1$ for binary additive valuations.","pith_inferences":["The no-positive-cycle characterization is stated for additive valuations, but the graph argument itself only uses the fact that subsidies shift edge costs linearly; the same criterion likely extends to any quasilinear domain where each agent's value for a bundle is well defined, such as submodular or single-minded valuations, though the subsidy bounds would need separate arguments.","The gap between the general-additive upper bound $(W-w_1)V$ and the appendix's examples suggests the true worst-case subsidy may scale with the ratio $W/w_1$ in a more refined way, and the modified-valuation proof gap is a natural place to look for a corrected or tightened bound.","Weighted subsidy bounds may transfer to other weighted fairness notions: the same longest-path subsidy formula could be specialized to weighted proportionality or weighted maximin share, where analogous positive-cycle obstructions would characterize when money can close the gap.","A direct numerical experiment on random additive instances could test whether Algorithm 1's output ever approaches or exceeds its printed bound; the appendix indicates the bound is not tight, so a tighter analysis may be possible."],"forward_implications":["With equal weights, all three bounds collapse to the known unweighted bound $(n-1)V$, so the weighted results are strict extensions of the earlier theory.","For any given WEF-able allocation, the componentwise-minimal subsidy vector can be computed in $O(nm+n^3)$ time by shortest-path methods on the negated weighted envy graph.","For general additive valuations with integer weights, the subsidy bound is independent of the number of items $m$, and dividing all weights by their gcd improves the bound to $(W-w_1)V/\\gcd(w)$.","For identical additive valuations, the total subsidy is at most $(n-1)V$ regardless of the weights, and this is tight even with equal weights.","For binary additive valuations, the weighted Yankee Swap yields a WEF-able allocation with total subsidy at most $W/w_1-1$, and the allocation is non-redundant, hence welfare-maximizing for the binary case."],"supporting_citations":[{"why":"Supplies the unweighted characterization of envy-freeable allocations and the subsidy bounds that this paper generalizes to weighted entitlements, and the example that the weighted version no longer matches the welfare-maximization condition.","marker":"[18]"},{"why":"Provides the iterated maximum matching algorithm and the one-dollar-per-agent subsidy bound that Algorithm 1 generalizes to a one-to-many weighted matching.","marker":"[7]"},{"why":"Provides the General Yankee Swap transfer-path framework, gain function, and non-redundancy guarantee on which Algorithm 3 is based.","marker":"[30]"},{"why":"Defines the WEF(x,y) bounded-envy notion used to prove the path-cost bounds in Theorems 3.7 and to certify that Algorithms 2 and 3 produce WEF(0,1) allocations.","marker":"[11]"},{"why":"Gives the polynomial-time minimum-cost flow algorithm used to implement each matching round of Algorithm 1.","marker":"[16]"},{"why":"Gives the network-flow reduction by which the one-to-many maximum-value matching problem is solved as an integral min-cost flow.","marker":"[17]"}],"fun_headline_variants":["Bounded subsidies make weighted envy-freeness possible","Weighted envy-free allocation with capped subsidies","Capped payouts for fair weighted division","Polynomial-time weighted envy-free with bounded subsidies","Guaranteeing weighted fairness with finite subsidies"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The general-additive total-subsidy bound $(W-w_1)V$ depends on a 'modified valuations' bridge that assumes the matching output is EF-able under unit weights with the original required subsidy no larger than the modified one, yet Proposition 3.14's printed inequality omits the weight factor and the Case 3 construction transfers items without preserving bundle cardinalities, so the bridge is the load-bearing point whose failure would leave that bound unsupported.","fun_headline_variants_meta":{"raw":{"variants":["Bounded subsidies make weighted envy-freeness possible","Weighted envy-free allocation with capped subsidies","Capped payouts for fair weighted division","Polynomial-time weighted envy-free with bounded subsidies","Guaranteeing weighted fairness with finite subsidies"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000948,"raw_usage":{"total_tokens":4018,"prompt_tokens":890,"completion_tokens":3128,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":506,"completion_tokens_details":{"reasoning_tokens":3068}},"tokens_in":506,"tokens_out":3128,"duration_ms":21535,"temperature":1.0,"reasoning_tokens":3068,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T17:18:41.519199+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small additive instance with integer weights, run Algorithm 1, and compute the true minimal subsidy for its output via Theorem 3.5 (longest paths in the weighted envy graph). If any agent's minimal subsidy exceeds $w_i V$, or the total exceeds $(W-w_1)V$, the main general-additive theorem is false; comparing the original and modified-valuation longest-path costs also directly tests Proposition 3.14.","supporting_citations":[{"cited_title":"Fair division with subs idy","cited_arxiv_id":null,"evidence_quote":"Supplies the unweighted characterization of envy-freeable allocations and the subsidy bounds that this paper generalizes to weighted entitlements, and the example that the weighted version no longer matches the welfare-maximization condition."},{"cited_title":"One dollar each eliminates envy","cited_arxiv_id":null,"evidence_quote":"Provides the iterated maximum matching algorithm and the one-dollar-per-agent subsidy bound that Algorithm 1 generalizes to a one-to-many weighted matching."},{"cited_title":"A general framework for fair allocation under matroid rank valuations","cited_arxiv_id":null,"evidence_quote":"Provides the General Yankee Swap transfer-path framework, gain function, and non-redundancy guarantee on which Algorithm 3 is based."},{"cited_title":"Weighted fairness notions for indivisible items revisited","cited_arxiv_id":null,"evidence_quote":"Defines the WEF(x,y) bounded-envy notion used to prove the path-cost bounds in Theorems 3.7 and to certify that Algorithms 2 and 3 produce WEF(0,1) allocations."},{"cited_title":"Finding minimum- cost circulations by canceling negative cycles","cited_arxiv_id":null,"evidence_quote":"Gives the polynomial-time minimum-cost flow algorithm used to implement each matching round of Algorithm 1."},{"cited_title":"Network flow algorithm","cited_arxiv_id":null,"evidence_quote":"Gives the network-flow reduction by which the one-to-many maximum-value matching problem is solved as an integral min-cost flow."}],"review_version":1}