{"id":"210535d9-814f-471c-a7d2-fe8aeeb4a9cf","arxiv_id":"2505.23251","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"The authors derive near-tight subsidy bounds for equitable allocations, characterize allocations that achieve both equitability and envy-freeness with the same payments, and provide approximation algorithms for welfare guarantees.","lead":"This paper asks how much money must be added to an allocation of indivisible items so that all agents value their own bundle equally (equitability). It gives bounds on this subsidy for goods, chores, and mixed items, plus algorithms and a characterization for combining equitability with envy-freeness.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 2's mixed-items lower bound is false: for n=3, m=3 with one +1 good and two -1 chores, minimum subsidy is 1 < max{2,3}, so the claimed tight bound fails.","rationale":"The reader's CONDITIONAL verdict was based on a suspected proof gap in Proposition 2 and on the normalization issue in the Preliminaries. I find a stronger, more load-bearing problem: the mixed-items lower bound in Proposition 2 is false, not merely underproved. The counterexample above uses the paper's own definitions and even satisfies the objective-valuation restriction, so it invalidates the claimed matching lower bound and the tightness statement in Table 1. The normalization concern is real and worth fixing, but it is secondary: the counterexample holds under the paper's stated normalization. Agreement with the reader is partial because the reader flagged Proposition 2 as incorrect but expected the lower bound to be true and fixable; my check shows that expectation is wrong. Since the abstract and Table 1 advertise these lower bounds as part of the main contribution, the current version should not be accepted as is; the mixed lower bound must be removed or corrected and all downstream tightness claims revised accordingly.","tokens_in":21043,"tokens_out":13278,"duration_ms":145630,"concrete_test":"Enumerate all 3^3 allocations for the instance n=3, m=3 with identical additive valuations v(e1)=1, v(e2)=v(e3)=-1, and compute the minimum total subsidy as n * max_i v_i(A_i) - sum_i v_i(A_i) per Lemma 1. The minimum is 1, not max{2,3}=3. If this enumeration confirms 1, Proposition 2's mixed lower bound is refuted and Table 1's tightness claim must be revised.","verdict_should_be":"REJECT","load_bearing_attack":"Proposition 2's mixed-items lower bound max{n-1,m} is false under the paper's own normalization. Consider n=3, m=3 with identical additive valuations v(e1)=1, v(e2)=v(e3)=-1. This instance is objective (e1 is a good, e2/e3 are chores for every agent) and satisfies |Delta| <= 1. Allocate all three items to agent 1; bundle values are (-1,0,0). Lemma 1 gives payments p=(1,0,0), so (A,p) is EQ with total subsidy 1. No allocation can be EQ with zero subsidy: for identical additive valuations, every complete allocation has value sum 1-2=-1, so three equal bundle values would have to be integers t with 3t=-1, impossible. Thus the minimum subsidy is 1, strictly below max{n-1,m}=max{2,3}=3. Because this instance is objective, it also contradicts the paper's own objective upper bound (n-1)=2 for mixed items. The claimed matching lower bound in Table 1 and the 'tight' characterization therefore fail; this is not merely a gap in a proof but a false statement.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies equitability (EQ) with monetary subsidies for the allocation of indivisible items. It gives algorithms that compute allocations with bounded subsidy while achieving EQ (or EQ1), lower-bound constructions for goods, chores, and mixed items, a characterization of allocations that are simultaneously equitable-convertible and envy-freeable, and efficiency guarantees for utilitarian social welfare and Nash welfare under normalized additive, subadditive, and matroid-rank valuations. The main claims are summarized in Tables 1 and 2.","tokens_in":21306,"tokens_out":18900,"duration_ms":208302,"significance":"If correct, the paper would contribute clean subsidy bounds for equitability and a useful EQ+EF characterization, together with polynomial-time constructive algorithms. The EQ+EF characterization in Lemma 2 is simple and appears correct, the goods and chores upper/lower bounds are well supported, and the paper makes appropriate use of external results such as Benabbou et al. for matroid-rank USW and Viswanathan-Zick for max-NSW. However, two formal claims are false as stated: the mixed-items lower bound in Proposition 2 and the Nash-welfare upper bound in Proposition 6. These are not mere proof gaps but incorrect theorem statements, so the claimed tightness of the main results is not established.","major_comments":[{"comment":"The mixed-items lower bound of Proposition 2 is false. Consider n=3, m=3 with identical additive valuations v(e1)=1 and v(e2)=v(e3)=-1. This instance is objective and satisfies |Delta_i(S,e)| <= 1. The allocation A=(M, empty, empty) gives bundle values (-1,0,0), so by Lemma 1 the payments p=(1,0,0) achieve EQ with total subsidy 1. No zero-subsidy EQ allocation exists because all bundle values are integers summing to -1, so three equal integer bundle values cannot sum to -1. Thus the minimum subsidy is 1, not max{n-1,m}=3. Consequently the claimed matching lower bound in Table 1 and the 'tight' characterization for mixed items are invalid; the proof's statement that agent 1's bundle should be empty is also garbled, since all agents in the constructed instance are identical.","section":"Section 3.2, Proposition 2; Table 1"},{"comment":"The claim that scaling each agent's valuation so that |Delta_i(S,e)| <= 1 is W.L.O.G. is not correct for equitability with subsidy. Payments are in common monetary units, and the equations v_i(A_i)+p_i = v_j(A_j)+p_j are not invariant under independent per-agent rescaling. For example, with one good valued 100 by agent 1 and 1 by agent 2, per-agent scaling to unit marginals would turn the true minimum subsidy of 99 into 1. The bounds in Theorems 1 and 5 and the related lower bounds are therefore results about a normalized valuation model, not about general valuations as the 'W.L.O.G.' wording suggests. This should be declared as a model assumption, or justified by a single global rescaling, and the dependence of the bounds on the chosen normalization should be discussed.","section":"Section 2, Preliminaries (normalization assumption)"},{"comment":"The claimed upper bound on EQ1 Nash welfare for two normalized additive agents is not established by the Table 4 construction. For the EQ1 allocation described in the proof (e1 to agent 1, e2 and e3 to agent 2), the ratio to maximum Nash welfare is sqrt((1/3 + epsilon/2)/(1/3 + 2 epsilon)), which is strictly greater than sqrt(3)/2 for every epsilon in (0,1/12) and tends to 1 as epsilon tends to 0. Thus the exhibited allocation itself satisfies the sqrt(3)/2-max-NSW guarantee, so the instance does not show that no EQ1 allocation achieves it. The proposition and its use as an upper complement to Theorem 4 require a different argument or a corrected statement.","section":"Section 5.1, Proposition 6"}],"minor_comments":[{"comment":"Several references to 'Theorem 2' (e.g., in Proposition 4, Proposition 7, and Proposition 8) should instead refer to Lemma 2, which is the characterization being invoked.","section":"Section 4 and Section 5.2"},{"comment":"In Case 2 of the Balanced-Packing proof, the inequality '> 1/3' should be '>= 1/3' when |N^-| = 1, since 1 - 2(n-1)/(3n-3) equals 1/3.","section":"Section 5.1, proof of Theorem 2"},{"comment":"The phrase 'for some e in t' uses a lowercase 't' where the set T is meant; this is a typo.","section":"Algorithm 3, line 9"},{"comment":"The table's footnote states two different upper-bound assumptions for the mixed-items row, but the lower-bound column does not state its valuation assumption; in light of the false lower bound, the entire row needs to be revised.","section":"Table 1"}],"recommendation":"reject","confidential_remarks":"The paper contains several valid components, but the advertised mixed-items tight lower bound is false and the Nash-welfare upper bound of Proposition 6 is also not supported. These are load-bearing errors in the main contribution. I would be open to seeing a corrected version that either proves correct lower bounds or explicitly removes the false tightness claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is the first paper to take exact equitability with subsidy seriously, and the EQ+EF characterization in Lemma 2 is a genuinely useful structural result. But the claimed mixed-items lower bound is false as stated, and the normalization \"W.L.O.G.\" is not without loss for equitability. The paper needs a major revision before its Table 1 can be trusted.\n\nWhat is new: the paper moves subsidy from EF to EQ, gives upper bounds via the Squeeze Algorithm, characterizes allocations that are simultaneously equitable-convertible and envy-freeable with one payment vector (Lemma 2: v_j(A_j) >= v_i(A_j) for all i,j), and gives polynomial algorithms with efficiency guarantees for matroid-rank and normalized subadditive valuations. Those are real contributions.\n\nWhere it is soft: Proposition 2 claims a mixed-items lower bound of max{n-1,m}. This is false. Take n=3,m=3 with identical additive valuations v(e1)=1, v(e2)=v(e3)=-1. This is an objective instance satisfying |Delta|<=1. Allocate all three items to agent 1. Bundle values are (-1,0,0), and Lemma 1 gives payments (1,0,0), total subsidy 1. No zero-subsidy EQ allocation exists because the three bundle values would have to be equal integers summing to -1. So the minimum subsidy is 1, not 3. The proof of Proposition 2 is also garbled: it says agent 1 values all items positively when the instance has m-1 chores, and the formulas around max_j v_j(A_j) have typos. This is not a cosmetic issue; it breaks the \"tight\" claim in Table 1 for mixed items. The upper bounds in Theorem 1 may still be fine, but the matching lower bound does not hold.\n\nThe second issue is the normalization. The paper says W.L.O.G. each valuation is scaled so every marginal has magnitude at most 1. For subsidy problems, per-agent scaling is not without loss: the equalization equations change if you rescale agents independently, and the subsidy amounts are in common units. So the bounds are only for valuations that are already normalized; they do not automatically extend to arbitrary additive valuations. This should be stated as an assumption, not W.L.O.G.\n\nAlso minor: Corollary 1 and Proposition 4 refer to \"Theorem 2\" when they mean Lemma 2.\n\nNet: the goods/chores results and the EQ+EF characterization look solid; the mixed-items tightness story is wrong; the normalization needs fixing. I would send this to a serious referee, because the topic is new and the good parts are worth salvaging, but I would not cite the mixed lower bound until it is corrected.","headline":"First systematic treatment of exact equitability with subsidy, with a genuinely useful EQ+EF characterization, but the mixed-items lower bound is false and the normalization is not W.L.O.G.","tokens_in":21817,"tokens_out":5142,"would_cite":true,"duration_ms":53682,"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 proves tight worst-case subsidy bounds for making indivisible-item allocations equitable, characterizes when the same payments also buy envy-freeness, and gives polynomial-time algorithms that preserve welfare guarantees.","keywords":["equitability with subsidy","fair division","indivisible items","goods and chores","envy-freeness","utilitarian social welfare","Nash welfare","matroid rank valuations"],"falsifier":"Compute the true minimum subsidy by enumerating all allocations and using Lemma 1's payment rule for small goods and chores instances with normalized additive valuations; any instance whose minimum exceeds $n-1$ would contradict Theorem 1. For mixed additive instances, the same enumeration would show whether the bound $n+m-2$ is tight or whether the lower bound $\\max\\{n-1,m\\}$ is the true answer, and checking the inequalities $v_j(A_j) \\ge v_i(A_j)$ against feasibility of the EQ-plus-EF payment equations would test Lemma 2.","tokens_in":20823,"feed_emoji":"💰","tokens_out":12411,"duration_ms":131693,"temperature":0.7,"pith_summary":"This paper asks how much monetary compensation is needed to turn a division of indivisible items into one that is equitable, meaning every agent values her own bundle equally. For goods and for chores, it proves that a total subsidy of $n-1$ (in units where no single item moves any agent's value by more than 1) always suffices, that this bound cannot be improved, and that it is achieved in polynomial time by the Squeeze Algorithm. For mixed goods-and-chores instances the same algorithm gives at most $n+m-2$ subsidy for additive valuations and $n-1$ for objective valuations, leaving a gap to the lower bound $\\max\\{n-1,m\\}$. The paper also characterizes exactly when one payment vector can deliver both equitability and envy-freeness, and it studies how much utilitarian or Nash welfare can be preserved when the subsidy is held at its optimal bound.","feed_headline":"n−1 dollars of subsidy buys exact equitability","feed_subtitle":"For goods or chores, a fast algorithm matches the lower bound; mixed items and welfare trade-offs are mapped too.","key_machinery":"The load-bearing object is the Squeeze Algorithm (Algorithm 1), which repeatedly gives the current highest-valued agent an item with non-positive marginal value, or the current lowest-valued agent an item with non-negative marginal value, and thereby preserves the invariant that all bundle values lie within 1 of each other. The companion Lemma 1 pins down the optimal payment vector: to achieve EQ with minimum total subsidy, pay each agent exactly $\\max_j v_j(A_j) - v_i(A_i)$. Since an EQ1 allocation under the unit-marginal normalization has max-min gap at most 1, the algorithm's invariant converts directly into the subsidy bound. A second mechanism is the characterization of simultaneous EQ and EF via the inequalities $v_j(A_j) \\ge v_i(A_j)$, which reduces the search for EQ-and-EF allocations to finding allocations in which every owner values her own bundle at least as much as anyone else does.","core_discovery":"The central result is that equitability is cheap once an allocation is equitable up to one item (EQ1): because each agent's marginal values are normalized to at most 1, an EQ1 allocation has value gap at most 1 between any two bundles, and the optimal payment vector of Lemma 1 — paying each agent $\\max_j v_j(A_j) - v_i(A_i)$ — then costs at most $n-1$ in total. Algorithm 1 maintains the EQ1 invariant while allocating all items, which yields the tight $n-1$ bound for goods, chores, and objective mixed valuations, and $n+m-2$ for additive mixed valuations. For the combined fairness requirement, the paper proves that an allocation admits one payment vector making it both EQ and EF if and only if $v_j(A_j) \\ge v_i(A_j)$ for every pair of agents $i,j$; this is the exact condition under which the same subsidies buy both fairness notions. On the efficiency side, with normalized valuations the paper shows EQ1 allocations can guarantee $O(1/n)$-max-USW for subadditive valuations, and for two agents $1/3$-max-NSW (subadditive) and $1/\\sqrt{2}$-max-NSW (additive), while with plain additive valuations and subsidy capped at $n-1$ no positive welfare approximation is possible.","pith_inferences":["Editorial inference: the $n-1$ bound is meaningful only after rescaling each agent's valuation so that every marginal contribution lies in $[-1,1]$; in applications the subsidy should be read in units of each agent's largest marginal value, and the independent rescalings are not interchangeable.","Editorial inference: the condition $v_j(A_j) \\ge v_i(A_j)$ suggests viewing each bundle as owned by its top valuer, turning the EQ-and-EF problem into a search over allocations that respect this ownership condition; maximum-USW allocations satisfy it in the additive case, which is why that efficiency benchmark is compatible with both fairness notions.","Editorial extension: brute-force enumeration for small mixed additive instances could determine whether the true minimum subsidy is $\\max\\{n-1,m\\}$ or rises with $m$, and similar experiments could test whether the two-agent $1/\\sqrt{2}$ Nash-welfare bound is tight."],"forward_implications":["For goods or chores, the subsidy needed for exact equitability does not grow with the number of items: $n-1$ is both the worst-case lower bound and the guarantee of a polynomial-time algorithm.","Mixed additive instances are the remaining loose end, since the paper's upper bound $n+m-2$ sits above the lower bound $\\max\\{n-1,m\\}$; closing this gap is the concrete open step.","An allocation can be made both equitable and envy-free with the same payments exactly when $v_j(A_j) \\ge v_i(A_j)$ for every pair of agents, so the search for such allocations can target this owner-values-own-bundle condition.","Under normalized valuations, EQ1 is compatible with meaningful efficiency: $O(1/n)$-max-USW for subadditive valuations, and $1/3$-max-NSW or $1/\\sqrt{2}$-max-NSW for two agents, all achievable with at most $n-1$ subsidy.","For additive valuations, capping subsidy at $n-1$ rules out any positive welfare approximation, and requiring EQ plus EF rules out any Nash-welfare guarantee, although maximum-USW allocations are always EQ-and-EF convertible."],"supporting_citations":[{"why":"Defines equitability up to one item (EQ1), the relaxation whose bounded value-gap property Proposition 3 and Algorithm 1 rely on.","marker":"Freeman et al. [2019]"},{"why":"Establishes the envy-freeable allocation framework and the $(n-1)m$ subsidy bound that the paper's EQ-and-EF results parallel and extend.","marker":"Halpern and Shah [2019]"},{"why":"Supplies the definition of objective valuations and the EQX existence context that Theorem 1's mixed-item result builds on.","marker":"Barman et al. [2024]"},{"why":"Shows checking for EQ allocations is NP-hard, motivating the paper's choice of a computable allocation with bounded subsidy rather than exact minimization.","marker":"Bouveret and Lang [2008]"},{"why":"Provides the upper bound showing no EQ1 allocation can beat $O(1/n)$-max-USW under normalized additive valuations, making Algorithm 2 asymptotically tight.","marker":"Sun et al. [2023]"},{"why":"Proves maximum Nash welfare allocations are envy-free up to one item, the property Algorithm 4 depends on for its $1/\\sqrt{2}$ guarantee.","marker":"Caragiannis et al. [2019]"},{"why":"Supplies the polynomial-time clean maximum-USW allocation for matroid rank valuations that Theorem 5 converts into an EQ-and-EF allocation.","marker":"Benabbou et al. [2021]"},{"why":"Provides the General Yankee Swap algorithm whose clean maximum-Nash-welfare output is used to build the EQ-and-EF allocation under matroid rank valuations.","marker":"Viswanathan and Zick [2023]"}],"fun_headline_variants":["n-1 dollars buys exact equitability for goods, chores, and mixed","Equitability via n-1 subsidy: tight lower bound matched","Joint EQ and EF: one subsidy works under a simple condition","Subsidy bounds for equitability: n-1 tight, plus welfare limits","Worst-case subsidy to achieve equitability is exactly n-1"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every agent's valuations have been rescaled so that no single item can change that agent's value by more than 1, and for the welfare results that every agent values the entire item set at exactly 1; if those rescalings are not part of the application, the subsidy bounds do not transfer unchanged.","fun_headline_variants_meta":{"raw":{"variants":["n-1 dollars buys exact equitability for goods, chores, and mixed","Equitability via n-1 subsidy: tight lower bound matched","Joint EQ and EF: one subsidy works under a simple condition","Subsidy bounds for equitability: n-1 tight, plus welfare limits","Worst-case subsidy to achieve equitability is exactly n-1"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000892,"raw_usage":{"total_tokens":3843,"prompt_tokens":940,"completion_tokens":2903,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":556,"completion_tokens_details":{"reasoning_tokens":2809}},"tokens_in":556,"tokens_out":2903,"duration_ms":27310,"temperature":1.0,"reasoning_tokens":2809,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:56:06.040237+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the true minimum subsidy by enumerating all allocations and using Lemma 1's payment rule for small goods and chores instances with normalized additive valuations; any instance whose minimum exceeds $n-1$ would contradict Theorem 1. For mixed additive instances, the same enumeration would show whether the bound $n+m-2$ is tight or whether the lower bound $\\max\\{n-1,m\\}$ is the true answer, and checking the inequalities $v_j(A_j) \\ge v_i(A_j)$ against feasibility of the EQ-plus-EF payment equations would test Lemma 2.","supporting_citations":[{"cited_title":"Equitable allocations of indivisible goods","cited_arxiv_id":null,"evidence_quote":"Defines equitability up to one item (EQ1), the relaxation whose bounded value-gap property Proposition 3 and Algorithm 1 rely on."},{"cited_title":"Fair division with subsidy","cited_arxiv_id":null,"evidence_quote":"Establishes the envy-freeable allocation framework and the $(n-1)m$ subsidy bound that the paper's EQ-and-EF results parallel and extend."},{"cited_title":"Nearly equitable allocations beyond additivity and monotonicity","cited_arxiv_id":null,"evidence_quote":"Supplies the definition of objective valuations and the EQX existence context that Theorem 1's mixed-item result builds on."},{"cited_title":"Efficiency and envy-freeness in fair division of indivisible goods: Logical representation and complexity","cited_arxiv_id":null,"evidence_quote":"Shows checking for EQ allocations is NP-hard, motivating the paper's choice of a computable allocation with bounded subsidy rather than exact minimization."},{"cited_title":"Equitability and welfare maximization for allocating indivisible items","cited_arxiv_id":null,"evidence_quote":"Provides the upper bound showing no EQ1 allocation can beat $O(1/n)$-max-USW under normalized additive valuations, making Algorithm 2 asymptotically tight."},{"cited_title":"The unreasonable fairness of maximum nash welfare","cited_arxiv_id":null,"evidence_quote":"Proves maximum Nash welfare allocations are envy-free up to one item, the property Algorithm 4 depends on for its $1/\\sqrt{2}$ guarantee."},{"cited_title":"Finding fair and efficient allocations for matroid rank valuations","cited_arxiv_id":null,"evidence_quote":"Supplies the polynomial-time clean maximum-USW allocation for matroid rank valuations that Theorem 5 converts into an EQ-and-EF allocation."},{"cited_title":"A general framework for fair allocation under matroid rank valuations","cited_arxiv_id":null,"evidence_quote":"Provides the General Yankee Swap algorithm whose clean maximum-Nash-welfare output is used to build the EQ-and-EF allocation under matroid rank valuations."}],"review_version":1}