{"id":"999e72cc-6f6c-434d-8d37-3e9da78b6197","arxiv_id":"2502.09006","paper_version":5,"verdict":"REJECT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper extends envy-free allocation with subsidies to weighted entitlements, proving worst-case subsidy bounds and polynomial-time algorithms for monotone, superadditive, additive, binary, matroidal, and identical-item valuations.","lead":"This paper studies fairly dividing indivisible items among agents with different entitlement weights, using cash subsidies to prevent envy. It gives polynomial-time algorithms with provable worst-case subsidy budgets for several valuation classes, and shows that previous unweighted techniques fail when weights differ.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 5.7 is false: original weighted subsidy can exceed the modified unit-weight subsidy, so Theorem 5.9's additive bound is unproven.","rationale":"The reader's strongest claim identifies exactly the invalid Proposition 5.7, and my independent check confirms it with a concrete counterexample. The reader's weakest_assumption focuses on integrality of weights, which is a secondary issue; even with integer weights, the proof of the additive subsidy bound fails. The paper has genuinely interesting results in Sections 3-4 and 6-9, but the headline additive-valuation guarantee (Theorem 5.9) is not established by the given proof. Since this is the core contribution advertised in the abstract and Table 1, the verdict should remain rejection unless the proof is repaired. I therefore do not change the reader's verdict, though I would state the reason as the false Proposition 5.7 rather than the integrality assumption.","tokens_in":40458,"tokens_out":7946,"duration_ms":72701,"concrete_test":"Run Algorithm 1 on the explicit 2-agent, 3-item instance with w=(1,2), v1(o1)=100, v1(o2)=v1(o3)=0, v2(o1)=60, v2(o2)=v2(o3)=1, and compute both the original weighted minimal subsidy vector and the modified unit-weight minimal subsidy vector via Theorem 3.5. If the original subsidy for agent 2 (118) exceeds the modified subsidy (59), Proposition 5.7 is refuted. Independently, re-derive Proposition 5.7's inequality symbolically: from Observation 5.5 the best obtainable relation is \\ell^{\\bar{v}}_i \\ge \\ell^{v}_i, which yields p^v_i \\le w_i p^{\\bar{v}}_i, not p^v_i \\le p^{\\bar{v}}_i.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing flaw is Proposition 5.7, used to carry the subsidy bound from modified valuations back to the original additive valuations. It claims that for Algorithm 1's allocation X, the subsidy required under v with weights w is at most the subsidy required under the modified profile \\bar{v} with unit weights. The proof notes that each modified edge cost is at least the original weighted edge cost, which implies only \\ell^{\\bar{v}}_i \\ge \\ell^{v}_i. From this, the original subsidy is p^v_i = w_i \\ell^{v}_i \\le w_i \\ell^{\\bar{v}}_i, not p^v_i \\le \\ell^{\\bar{v}}_i. When w_i > 1, the claimed inequality has the wrong factor. This is not a mere technical gap: for T=1 the modified valuations reduce exactly to v_i(X_j)/w_j, so \\ell^{\\bar{v}}_i = \\ell^{v}_i, and Proposition 5.7 would assert w_i \\ell_i \\le \\ell_i, which fails whenever \\ell_i > 0 and w_i > 1. Concretely, with n=2, w=(1,2), m=3, v1(o1)=100, v1(o2)=v1(o3)=0, v2(o1)=60, v2(o2)=v2(o3)=1, Algorithm 1 (single round) returns X1={o1}, X2={o2,o3}. The maximum-cost path from agent 2 has cost 59, so the original weighted subsidy is p^v_2 = 2*59 = 118, whereas the modified unit-weight subsidy is 59. Thus Proposition 5.7 is false, and the proof of Theorem 5.9 collapses at this step. Proposition 5.8 also appears to mix unit weights with the original weights when invoking Lemma 5.4, compounding the same issue.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies weighted envy-free (WEF) allocation of indivisible items with monetary subsidies under unequal entitlements. It provides a characterization of WEF-able allocations via weighted reassignment-stability and the absence of positive-cost cycles in a weighted envy graph (Theorem 3.3), then gives polynomial-time algorithms with worst-case subsidy bounds for general monotone, superadditive, supermodular, additive, identical-additive, binary-additive, matroidal, and identical-item settings, plus an algorithm for limited subsidy budgets that is new even for the unweighted case (Section 9). The headline additive-valuation result (Theorem 5.9) claims that for integer weights, Algorithm 1 computes a WEF-able allocation with per-agent subsidy at most w_i V and total subsidy at most (W - w_min)V.","tokens_in":40859,"tokens_out":31224,"duration_ms":252363,"significance":"If correct, the results substantially extend the unweighted subsidy literature (Halpern and Shah 2019; Brustle et al. 2020) to weighted entitlements, with tight worst-case bounds for several valuation classes and efficient constructions. The paper's strengths include the clean characterization of WEF-ability in Theorem 3.3, the novel MWEF algorithm in Section 9 that is new even in the unweighted setting, the tight lower-bound constructions, and the preliminary experiments comparing the algorithms with an ILP baseline. The main weakness is that a load-bearing step in the additive-valuation proof (Proposition 5.7) is false, so the central additive bound is not established as written; however, the flaw appears locally fixable.","major_comments":[{"comment":"Proposition 5.7 is false as stated. With n=2, w=(1,2), and three items with v1(o1)=100, v1(o2)=v1(o3)=0, v2(o1)=60, v2(o2)=v2(o3)=1, Algorithm 1 has a single round and returns X1={o1}, X2={o2,o3}. The maximum-cost path from agent 2 has cost 59, so the minimal WEF subsidy under the original valuations is p^v_2 = 2*59 = 118, while the modified unit-weight subsidy is p^{\\bar{v}}_2 = 59. The proposition asserts 118 ≤ 59, a contradiction. The proof only establishes that the modified path cost is at least the original path cost, which implies ℓ^{\\bar{v}}_i ≥ ℓ^v_i; this yields p^v_i = w_i ℓ^v_i ≤ w_i ℓ^{\\bar{v}}_i = w_i p^{\\bar{v}}_i, not p^v_i ≤ p^{\\bar{v}}_i. Since Theorem 5.9 relies on Proposition 5.7 to transfer the modified-valuation bound back to the original valuations, the proof of the additive bound collapses at this step. The correct inequality p^v_i ≤ w_i p^{\\bar{v}}_i, together with a corrected bound on p^{\\bar{v}}_i, would repair the argument, but the theorem is unproven as written.","section":"Proposition 5.7"},{"comment":"Proposition 5.8 misapplies Lemma 5.4. The modified envy graph is explicitly stated to have unit weights (Proposition 5.6), so applying Lemma 5.4 with z=V gives each agent a modified subsidy of at most V, not w_i V. The written statement 'the subsidy to each agent is at most w_i V for the modified valuation profile \\bar{v}' is only true because weights are normalized to be at least 1 in the integer-weight setting, but the proof as written invokes Lemma 5.4 with the original w_i as if they were the graph weights. This compounds the error in Proposition 5.7 and should be corrected so that the modified subsidy bound is stated as ℓ^{\\bar{v}}_i ≤ V, after which the corrected Proposition 5.7 gives p^v_i ≤ w_i V.","section":"Proposition 5.8"}],"minor_comments":[{"comment":"The sentence 'Agent 2 gets the first turn and gets o' is duplicated; one occurrence should be removed.","section":"Example 5.15"},{"comment":"The lower-bound proof for identical items contains several typos: 'The smallest weight wn is an integer' should likely be w1, and the displayed formulas for m2, m3, and mi have misplaced indices (e.g., 'w3/wn' appears to be a typo for w3/w1). These should be corrected for readability.","section":"Theorem 8.2"},{"comment":"In the random allocation B^t construction, step 1 says 'for each agent 1≤j≤k−1', but the subsequent algebra treats the last edge (i_{k-1}, i_k) using only i_{k-1}'s future bundle, not a transfer from i_k. Changing the loop to 1≤j≤k−2 makes the expected-change calculation consistent with the path cost; as written, the proof contains an apparent index error.","section":"Proposition 5.6, Case 3"},{"comment":"The paper clearly states that the additive bound requires integer weights (or integer ratios), and leaves the non-integer-ratio case open. This is a transparent limitation, not an error, but it would help to state explicitly in the abstract or introduction that the m-independent additive bound is conditional on integrality of the weight ratios.","section":"Section 5, integer-weight assumption"}],"recommendation":"major_revision","confidential_remarks":"The false Proposition 5.7 is a serious flaw in the proof of the main additive result, but it is a local factor error that can be repaired by restating the proposition as p^v_i ≤ w_i p^{\\bar{v}}_i and correcting the bound in Proposition 5.8. I do not see grounds for rejection: the other sections appear coherent, and the corrected argument would establish the stated additive bound. I recommend major revision, with the understanding that the additive-valuation section must be reproven and the corrected propositions verified."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper genuinely extends the subsidy-for-envy-freeness literature to weighted entitlements and contains several correct, nontrivial results: the tight bound for general monotone valuations, the superadditive MSW/VCG results, the binary-additive bound via an adapted Yankee Swap, the identical-items tight bounds, and the limited-budget MWEF procedure that is new even in the unweighted case. Second, the headline additive-valuation bound in Theorem 5.9 is unproven, and the error is not a stylistic gap but a false statement. Proposition 5.7 claims the original weighted subsidy is at most the unit-weight subsidy under modified valuations. That fails because path costs in the modified graph are lower bounds on the original weighted path costs, so you only get p_i = w_i * ell_i <= w_i * ell_bar_i, not p_i <= ell_bar_i. The counterexample is simple: n=2, weights (1,2), three items with v1(o1)=100, v1(o2)=v1(o3)=0, v2(o1)=60, v2(o2)=v2(o3)=1. Algorithm 1 returns X1={o1}, X2={o2,o3}; the max path from agent 2 has cost 59, so the true weighted subsidy is 118, while the modified unit-weight subsidy is 59. So Proposition 5.7 as stated is false, and Theorem 5.9's bound does not follow. Proposition 5.8 has the same flavor of mixing unit weights with original weights; it may be repairable, but the current proof does not work.\n\nWhat the paper does well: the negative examples showing that permutation EF-ability and iterated maximum matching break with weights are useful and motivate the new algorithms. The characterization via weighted reassignment-stability and positive cycles is clean and computationally usable. The general monotone bound is tight and simple. The binary and identical-additive sections look coherent, as does the MWEF limited-budget algorithm. The experiments are preliminary but honest.\n\nWhere it is soft beyond the main flaw: the additive algorithm only works when weights have integer ratios, and the text acknowledges this but leaves arbitrary real weights without any bound independent of m. That limitation would be fine if the theorem worked for the integer case; right now the integer case is also unproven. The paper merges two companion papers, and the self-citations are just provenance, so no circularity worry.\n\nWho it is for: anyone working on fair division with subsidies will want to know the weighted results, but they should read Section 5 with suspicion. The rest of the paper deserves a serious referee. A serious editor should send it out; the main additive theorem needs a corrected proof or a withdrawal of that claim until it is fixed.","headline":"Useful weighted fair-division results, but the advertised additive subsidy bound rests on a false proposition and needs a real proof before anyone should rely on it.","tokens_in":41417,"tokens_out":3504,"would_cite":false,"duration_ms":33657,"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":"Polynomial-time algorithms make weighted envy-free allocation with bounded subsidy possible, with tight worst-case bounds for monotone, additive, binary, and identical-item valuations.","keywords":["weighted envy-freeness","subsidy","indivisible items","fair division","entitlements","monotone valuations","additive valuations","envy graph"],"falsifier":"Take any concrete additive instance with integer weights, run Algorithm 1, and compute the exact minimum subsidy of its output by solving for the longest paths in the weighted envy graph; if the total exceeds $(W-w_{\\min})V/\\gcd(w)$ for that instance, the paper's main additive bound is false. The same test can be run as an integer program over all allocations to check whether the claimed bound is even achievable.","tokens_in":40283,"feed_emoji":"💰","tokens_out":9791,"duration_ms":89258,"temperature":0.7,"pith_summary":"Fairly dividing indivisible goods among agents with unequal claims generally cannot be done without money, so the paper asks how large a third-party subsidy is needed to make an allocation weighted envy-free (WEF): after adding subsidies, no agent prefers another's bundle relative to the other's entitlement. The paper shows that a WEF-able allocation always exists and, for arbitrary monotone valuations, can be found in polynomial time with total subsidy at most $(W/w_{\\min}-1)mV$, a bound that is tight in the worst case. For additive valuations with integer entitlements, it gives a polynomial-time algorithm whose total subsidy is at most $(W-w_{\\min})V/\\gcd(w)$, so the subsidy does not grow with the number of items. It also supplies algorithms and matching or near-matching bounds for identical additive, binary additive, matroidal, and identical-item valuations, and a procedure that uses any limited subsidy budget without creating new envy. The overall message is that unequal entitlements make fair division strictly harder than equal entitlements, but still feasible with bounded compensation.","feed_headline":"Unequal shares can be made envy-free with bounded subsidies","feed_subtitle":"For integer entitlements, the guaranteed subsidy does not grow with item count; worst-case bounds are tight.","key_machinery":"The machinery is the weighted envy graph $G_{X,w}$, a complete directed graph whose edge $i\\to j$ carries cost $v_i(X_j)/w_j - v_i(X_i)/w_i$. An allocation is WEF-able exactly when every directed cycle has non-positive cost, and the componentwise-minimal subsidy vector is $p_i = w_i\\ell_i(X)$, where $\\ell_i(X)$ is the maximum cost of any path starting at $i$; this reduces subsidy bounds to path-cost bounds. For integer-weight additive instances, Algorithm 1 uses minimum-cost flow to compute, round by round, a one-to-many maximum-value matching in which agent $i$ receives exactly $w_i$ items, and a modified valuation profile is used to show every edge cost is at least $-V$, yielding the $w_i V$ per-agent subsidy. For binary additive valuations, the adapted General Yankee Swap uses the gain function $w_i/(v_i(X_i)+1)$ to choose which agent receives the next item, and non-redundancy of the resulting allocation is what makes the subsidy bound $w_i/w_{\\min}$ possible.","core_discovery":"The central claim is that weighted envy-freeability is exactly the absence of positive-cost cycles in the weighted envy graph, and this characterization supports polynomial-time subsidy guarantees. Under arbitrary monotone valuations, the allocation that gives all items to the agent who values the whole set most is WEF-able, and the minimal subsidy it requires can reach $(W/w_{\\min}-1)mV$, so the upper bound is tight. For additive valuations with integer weights, the paper's one-to-many matching algorithm produces a WEF-able allocation in which each agent needs at most $w_i V/\\gcd(w)$, hence at most $(W-w_{\\min})V/\\gcd(w)$ total. For superadditive valuations, every welfare-maximizing allocation is WEF-able, which lets the paper combine WEF with Pareto efficiency and truthfulness through a VCG mechanism with upfront per-entitlement subsidies. The paper extends the same framework to binary, identical, matroidal, and identical-item additive cases, and to the limited-budget setting where subsidies are paid only to agents whom nobody envies.","pith_inferences":["A natural next step is to test whether rounding arbitrary real entitlements to rational ratios preserves the additive bound; if it does, the integer-weight restriction is an artifact of the algorithm rather than of the problem.","The $\\Omega(n^2V)$ lower bound for nearly equal weights with identical items suggests that the subsidy cost is driven by the ratios of entitlements, so even small differences among many partners can be expensive in practice.","The MWEF algorithm implies a practical policy for limited-budget dissolutions: concentrate cash on agents who are currently envied by no one, and check on real estate or inheritance instances whether this reduces envy more than equal per-capita cash transfers."],"forward_implications":["For monotone valuations, an allocation can be made weighted envy-free with a bounded subsidy in polynomial time, so unequal entitlements alone never make fair division impossible with money.","For superadditive valuations, one can simultaneously obtain weighted envy-freeness, Pareto efficiency, and truthfulness, since any welfare-maximizing allocation is WEF-able.","For additive valuations with integer entitlements, the needed total subsidy is independent of the number of items, bounded by $(W-w_{\\min})V/\\gcd(w)$.","For binary additive valuations, the total subsidy bound $W/w_{\\min}-1$ is independent of $m$, and the computed allocation is also WEF(0,1), a relaxation of weighted envy-freeness without money.","Even when the available subsidy is below the WEF requirement, the MWEF procedure guarantees that money is given only to agents whom nobody envies, so a small budget cannot create new envy; this is new even for equal entitlements."],"supporting_citations":[{"why":"Supplies the unweighted envy-freeability characterization, the $(n-1)mV$ subsidy bound, and the NP-hardness result that the weighted results extend.","marker":"Halpern and Shah (2019)"},{"why":"Provides iterated maximum matching and the one-dollar-each bound that Algorithm 1 extends to weighted entitlements.","marker":"Brustle et al. (2020)"},{"why":"Defines weighted envy-freeness and the Weighted Picking Sequence Protocol, and supplies the WEF(1,0) and adjusted-winner ideas used in Section 5.1.","marker":"Chakraborty et al. (2021a)"},{"why":"Defines the WEF(x,y) relaxation that the paper shows is incompatible with WEF-ability for x+y<2 and compatible for (1,1) with two agents.","marker":"Chakraborty et al. (2022)"},{"why":"Provides the General Yankee Swap, transfer paths, and non-redundancy arguments that Algorithm 3 adapts for binary additive valuations.","marker":"Viswanathan and Zick (2023a)"},{"why":"Gives the minimum-cost flow algorithm whose polynomial runtime makes the additive-valuation Algorithm 1 polynomial.","marker":"Goldberg and Tarjan (1989)"}],"fun_headline_variants":["Bounded subsidies achieve weighted envy-free","Weighted envy-free: subsidy bounds are tight","Polynomial-time weighted envy-free via subsidies","Money fixes weighted envy, within bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main additive-valuation result assumes every entitlement is an integer (or has integer ratios), because Algorithm 1 allocates exactly $w_i$ items to agent $i$ in each round; if the weights are arbitrary real numbers, the paper gives no subsidy bound independent of $m$.","fun_headline_variants_meta":{"raw":{"variants":["Bounded subsidies achieve weighted envy-free","Weighted envy-free: subsidy bounds are tight","Polynomial-time weighted envy-free via subsidies","Money fixes weighted envy, within bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000409,"raw_usage":{"total_tokens":2113,"prompt_tokens":925,"completion_tokens":1188,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":541,"completion_tokens_details":{"reasoning_tokens":1134}},"tokens_in":541,"tokens_out":1188,"duration_ms":13482,"temperature":1.0,"reasoning_tokens":1134,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T22:58:06.296868+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take any concrete additive instance with integer weights, run Algorithm 1, and compute the exact minimum subsidy of its output by solving for the longest paths in the weighted envy graph; if the total exceeds $(W-w_{\\min})V/\\gcd(w)$ for that instance, the paper's main additive bound is false. The same test can be run as an integer program over all allocations to check whether the claimed bound is even achievable.","supporting_citations":[],"review_version":1}