{"id":"6409385d-2a7d-4f58-960a-5025ad7a6031","arxiv_id":"2501.06799","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For mixtures of goods and chores, equitability up to one item can fail or be NP-hard, yet it always exists and is efficiently computable for symmetric {-1,1} and {-1,0,1} normalized valuations.","lead":"This paper studies how to split indivisible items fairly when some people like an item and others see it as a chore. It proves that fair splits can be impossible or hard to find in general, but gives fast algorithms for common simplified preference types and shows when fairness can be combined with efficiency.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.1 rests on Lemma B.1, whose transfer argument is not fully specified; the |P|≤|R| contradiction case relies on informal counting that does not account for non-contributing pairs and leaves the EQ1 invariant unverified.","rationale":"The reader's conditional verdict already focuses on the Theorem 4.1 proof via Lemma B.1 and on the claim that the partial allocation can be kept EQ1 after each transfer. This stress-test agrees with that focus and sharpens it: the algorithm's transfer descriptions and the terminal contradiction case are not rigorous enough to certify correctness. The concern is about proof completeness, not about a demonstrated counterexample. The result may well be true, and the exhaustive small-instance test would provide strong computational evidence either way. Because the reader already assigned CONDITIONAL on essentially this basis, the appropriate verdict is unchanged.","tokens_in":28308,"tokens_out":15984,"duration_ms":171050,"concrete_test":"Enumerate all normalized {-1,1} instances with n≤4 and m≤8, i.e., all valuation tables in which every agent has exactly k1 entries +1 and k2 entries -1 for some common k1,k2 and no column is unanimously +1 or unanimously -1, and run Algorithm 1 under all tie-breaking orders. Check that every run terminates and that the output is EQX at every step. A single violation identifies the exact transfer at which the k/k+1 invariant fails and disproves the algorithm as stated; if no violation exists, the remaining check is to formalize Lemma B.1 in a proof assistant to close the proof gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The headline theorem (Theorem 4.1) is proved by first computing a partial EQ1 allocation of O± (Lemma B.1) and then invoking the Completion Lemma. Lemma B.1 is therefore load-bearing, and its proof is incomplete. The transfer phase assumes a standing invariant that all agents have utility either k or k+1, so that EQ1/EQX coincide with a gap of one, but this invariant is never stated or proved. The four transfers are described qualitatively, and the step \"the remaining item o ... has a potential owner, and the algorithm makes progress by allocating o to that agent\" does not specify which of the two swapped agents receives the item; for a P-R transfer, giving the unallocated good to the newly rich poor agent would raise its utility to k+2 and break EQ1, so extra reasoning is required. In the terminal case |P|≤|R|, the proof asserts a contradiction to normalization by counting items valued at +1 by a poor agent. The counting starts with \"even if p values every good in every other poor agent's bundle at 1, then only |P|k ... are accounted for,\" but a poor bundle with utility k can contain more than k goods (offset by chores); the subsequent non-contributing-pair argument is informal and does not establish the required upper bound. If the contradiction is not valid, the algorithm could stall with no feasible transfer and |P|≤|R|, in which case Algorithm 1 is not correct. This does not show the theorem is false, but it means the central algorithmic claim is not yet established by the text.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies equitability up to one item (EQ1) and equitability up to any item (EQX) for additive valuations over mixed goods and chores. Its results are: (i) a two-agent two-item example where no EQ1 allocation exists, together with a weak NP-completeness theorem for deciding EQ1 existence for arbitrary instances (Example 1.1, Theorem 3.1); (ii) a polynomial-time EQ1 algorithm for objective valuations and a Completion Lemma for extending partial EQ1 allocations (Proposition 3.2, Lemma 3.4); (iii) a polynomial-time EQX algorithm for symmetric bi-valued ({-1,1}) normalized valuations (Theorem 4.1), an EQ1 algorithm for symmetric tri-valued ({-1,0,1}) normalized valuations (Theorem 4.3), and a two-agent type-normalized algorithm (Theorem 4.6); (iv) non-existence and strong NP-hardness results for EQ1+PO allocations, together with an algorithm that decides and finds an EQ1+PO allocation for ternary valuations when one exists (Example 5.1, Theorems 5.2 and 5.3); and (v) a pseudo-polynomial-time dynamic program for welfare-maximizing EQX allocations (Theorem 6.1). The algorithmic results for normalized subjective valuations are proved through iterative transfer arguments, and the correctness of the central theorem depends on a counting lemma (Lemma B.1) whose proof is not complete as written.","tokens_in":28654,"tokens_out":50475,"duration_ms":438665,"significance":"If established, the headline claim is a substantial advance: a polynomial-time EQX guarantee for subjective valuations with any number of agents over the normalized {-1,1} domain, where prior work covered only two agents or objective valuations, with hardness known elsewhere. The paper has real strengths that should be credited: all algorithms are concrete constructions with no fitted parameters or invented entities; the correctness arguments invoke external lemmas (Nash optimality for binary valuations and Freeman et al.'s Lemma 5.5) as black boxes rather than assuming the target results; the claims are falsifiable existence statements and the counterexamples (Examples 1.1, 3.3, 4.2, 4.4, 4.5, 5.1) are explicit and checkable; and Table 1 provides a useful landscape of the EQ1 and EQ1+PO results. The non-existence and hardness results for general mixtures (Theorem 3.1 and Theorem 5.2) and the Completion Lemma stand on their own. However, the proof of the main theorem is incomplete at a load-bearing point, and Theorem 4.3 is asserted without a proof, so the central algorithmic claims are conditional until the appendix is repaired.","major_comments":[{"comment":"The contradiction argument for the terminal case |P| <= |R| is not valid as written. (i) The statement that 'even if p values every good in every other poor agent's bundle at 1, then also only |P|k out of |R|(k+1)+1 such items are accounted for' assumes that each poor bundle contains exactly k goods. A poor agent with utility k can hold k+t goods and t chores (for instance, a rich agent that receives a chore in the greedy phase and later enters P after transfers), so the number of allocated items valued at +1 by p is not bounded by |P|k. (ii) The claim that p values none of the rich agents' items at +1 excludes only the |R|(k+1) goods inside rich bundles; a chore inside a rich bundle can be valued at +1 by p without triggering any of the four transfers, so p's +1-valued items are again undercounted. (iii) The closing paragraph does not produce the promised contradiction: 'if any rich agent values c at 1, then ... the process of compensating for the deficit does not terminate' is not a contradiction, and 'otherwise, v_r(c) = -1, but this is a contradiction to the fact that c in O±' is a non sequitur, since an item in O± may be valued at -1 by a rich agent; the relevant violated condition would be the no-P-R-transfer bullet 'every r values every chore in A_p at 1', which the proof does not invoke. (iv) The proof refers to 'Case (2b)' (Table 6) although no such case label appears in the proof text, which defines only cases 1 and 2. Because this terminal case is exactly the situation in which the algorithm would otherwise stall with no feasible transfer, Lemma B.1, and with it Theorem 4.1, is not established.","section":"Appendix B, Lemma B.1, case |P| <= |R|"},{"comment":"The pseudocode in Algorithm 1 is inconsistent with the proof text. Lines 14-19 use a loop bound 'for j in [t]' that is never defined, and the operation A_{r_j} := A_{r_j} minus {o : v_{r_j}(o) = 1} removes all +1-valued items from each rich agent's bundle, changing utilities by more than one unit and potentially violating EQ1/EQX, whereas the proof sketch and the surrounding text describe moving a single good from each rich agent to a distinct poor agent. The transfer phase is also under-specified: the sentence 'the remaining item o ... has a potential owner, and the algorithm makes progress by allocating o to that agent' does not say which of the two swapped agents receives o, nor does it verify that the resulting partial allocation is EQ1. After a Poor-Rich transfer the newly rich agent still values the unallocated item o at -1, so the feared scenario of raising that agent to k+2 does not arise if the item is assigned to the right agent, but the text never identifies that agent. Finally, the case analysis in Lemma B.1 assumes 'v_r(A_r) = k+1 and v_p(A_p) = k for some constant k' without stating or proving the invariant that all utilities lie in {k, k+1}; for {-1,1} valuations that invariant is equivalent to EQ1, so its preservation under each transfer and the subsequent allocation of o must be checked explicitly.","section":"Section 4.1 and Algorithm 1"},{"comment":"Theorem 4.3 is not proved. The appendix's entire proof is the sentence 'With the above set of transfers, it is easy to verify that the analogous argument as in Theorem 4.1 holds true in this setting as well.' This is not a proof, and the analogy is not sound in the respects that matter: with zero-valued items, EQ1 does not coincide with a utility gap of at most one (removing a 0-valued item provides no relaxation), so each of the eight transfer types must be verified against the full two-sided EQ1 definition; moreover, the normalization-based counting in Lemma B.1 cannot be reused because the reduced O± instance is not normalized in the {-1,0,1} case, as Example 4.2 demonstrates directly. Since Theorem 4.3 is advertised in the abstract and in Table 1 as the EQ1 result for symmetric tri-valued normalized valuations, a complete proof is required.","section":"Appendix B, Theorem 4.3"},{"comment":"The 'only if' direction of Algorithm 2's correctness rests on an informal AM-GM argument claiming that the restriction of any EQ1+PO complete allocation A* would have strictly larger Nash welfare than the Nash optimal partial allocation A'. The step 'by AM-GM inequality, it follows that ...' (leading to Eq. (7)) is not a proof: the poor/rich/violator partitions (P,R,S) and (P*,R*,S*) differ between the two allocations, and Eqs. (4)-(5) bound only the total excess above the respective 'rich' levels, which does not by itself establish that the utility vector of A* is more balanced than that of A'. A rigorous majorization or other argument showing NW(A*) > NW(A') is needed, or the impossibility claim must be proved by different means.","section":"Appendix C, Theorem 5.3, Eqs. (4)-(7)"}],"minor_comments":[{"comment":"The contributions section cites 'Theorem 4.3' for the bi-valued {-1,1} EQX result, but the body states that result as Theorem 4.1, while Theorem 4.3 in the body is the tri-valued EQ1 result; the cross-references should be corrected.","section":"Section 1.1"},{"comment":"In the second bullet of the reverse direction, the claim that a1 and a2 'even if they choose to ignore any item, they fall short of the utility derived by a3 (which is 2T)' is false for an agent holding all set items plus one dummy, whose utility after removing the dummy equals 2T exactly; the bullet's conclusion still holds, but it must be argued by splitting the set items between a1 and a2 rather than by the stated sentence.","section":"Section 3, proof of Theorem 3.1"},{"comment":"The condition for the Rich-Poor transfer reads 'v_r(o) = 1 = v_p(w)'; the symbol w should be o.","section":"Section 4.1, transfer 2"},{"comment":"The definition of 'rich' uses a strict inequality, yet the proof of Lemma B.1's case |P| > |R| concludes that a poor agent p' 'makes him one of the rich agents' when all agents are tied at the same utility; the tie convention needs to be stated explicitly.","section":"Section 2 and Lemma B.1"},{"comment":"The dynamic programming recurrence has presentation errors: in Eq. (3) the term 'v_i + v_i(o_k)' has the wrong sign when o_k is a chore (it should be v_i - v_i(o_k), as in Eq. (1)), and the expression 'g in union_{r in [k-1]} o_r' is typeset incoherently and should be written as a union over item indices.","section":"Section 6, Eqs. (1)-(3)"},{"comment":"The text contains a duplicated sentence: 'Follow-up work has studied equitability in various contexts: when items lie on a path, Follow-up work has studied equitability in various contexts: when items lie on a path, ...'.","section":"Section 1.2, Related Work"},{"comment":"The caption of Table 6 refers to 'Case (2b) in the proof of Lemma B.1', but the proof text defines only cases 1 and 2 (|P| > |R| and |P| <= |R|); the table appears to be a remnant of a longer version of the proof and should either be integrated into the text or removed.","section":"Appendix B, Table 6"},{"comment":"The text states that Barman et al. [2024] show computing an EQX allocation is strongly NP-hard and hard 'for non-objective normalized valuations, even for two agents', which appears to be in tension with Theorem 4.1 (a polynomial-time EQX algorithm for all {-1,1} normalized valuations, including non-objective instances, for any number of agents); the paper should state the exact valuation class for which the hardness result applies so that the novelty claim is unambiguous.","section":"Sections 1.1 and 1.2"}],"recommendation":"major_revision","confidential_remarks":"The central risk is the appendix proof of Lemma B.1: the counting argument for the |P| <= |R| case is genuinely incomplete, and repairing it may require substantial reworking rather than a local fix; if the authors cannot supply a correct counting argument, the status of Theorem 4.1 is open. I would also ask the authors to provide a real proof of Theorem 4.3 instead of the 'analogous argument' sentence, and to reconcile the statements about Barman et al. [2024] with Theorem 4.1 by specifying the exact valuation domain of that hardness result. These concerns do not affect the non-existence and hardness results (Theorem 3.1, Theorem 5.2) or the Completion Lemma, which appear sound. The manuscript itself reads as well structured and appropriately discloses its limitations and the relation to Bilo et al. [2025]; I see no citation-pattern or novelty-disclosure problems beyond the scope issue noted above."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth a serious referee's time. The headline claim—polynomial-time EQX allocations for {−1,1} normalized subjective valuations with any number of agents—is a genuine step beyond the prior 2-agent objective-valuation results of Barman et al. [2024], and the EQ1+PO impossibility/hardness results add useful structure to the mixed-mana landscape. The Completion Lemma (Lemma 3.4) is a clean and reusable tool, and the examples (1.1, 4.2, 4.4) are well chosen to explain why normalization and the transfer machinery are needed. The writing is clear and the related-work placement is honest, including the acknowledgment that the objective-valuations result was anticipated by Bilò et al.\n\nThe soft spots are real, but they are soft in different ways. The proof of Theorem 4.3 is only a gesture: the appendix says the argument is analogous to Theorem 4.1, which is not a proof of a new theorem. That must be written out. More importantly, Lemma B.1—the load-bearing lemma for Theorem 4.1—has gaps. The invariant that all agents' utilities are k or k+1 is never stated or proved, and the contradicting counting in the |P|≤|R| case relies on informal talk of \"non-contributing pairs\" without a rigorous upper bound. The argument may well be correct, but the text does not yet establish it. On the other hand, the stress-test's specific complaint about the P-R transfer is misaimed: after that transfer, the newly rich poor agent values the unallocated item at −1, so giving it that item restores the invariant rather than breaking it. The broader concern about unspecified transfer choices and the missing invariant is still valid. The proof of Theorem 3.1 contains a sloppy sentence (the \"maximum utility of a1 and a2 is negative\" line in the second case is wrong for an agent holding all set items), but the reduction itself can be patched and the NP-completeness claim looks sound.\n\nMy honest overall read: the results are probably true and the paper makes a real contribution, but the proof appendix is not yet rigorous enough for the theorems to be taken as established. The paper deserves peer review, and a referee should insist on a full rewrite of Lemma B.1, a real proof of Theorem 4.3, and a cleanup of Theorem 3.1. I would bring it to a reading group only if someone there wants to work on completing the proof.","headline":"Likely-true headline results in a serious paper, but the proof of the main theorem is not complete in the text and Theorem 4.3 is essentially unproved; this needs major revision before the results are established.","tokens_in":29175,"tokens_out":3722,"would_cite":false,"duration_ms":38537,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"For normalized $\\{-1,1\\}$ valuations, an EQX allocation of mixed goods and chores always exists and can be computed in polynomial time for any number of agents.","keywords":["fair division","equitability","EQ1","EQX","mixed manna","goods and chores","normalized valuations","Pareto optimality"],"falsifier":"Enumerate every allocation of a small normalized $\\{-1,1\\}$ instance with, say, three agents and six subjective items where each agent values exactly two items at $+1$ and four at $-1$; the paper's Theorem 4.1 predicts that every such instance has an EQX allocation, so finding even one without one refutes the theorem. Running Algorithm 1 on random instances of the same type and checking that the output is EQX would provide the same test computationally.","tokens_in":28131,"feed_emoji":"⚖️","tokens_out":9077,"duration_ms":78688,"temperature":0.7,"pith_summary":"Equitable division asks that all agents derive equal value from their bundles; with indivisible items, the natural relaxation is EQ1/EQX, where inequality can be erased by removing one item. This paper shows that in a mixture of goods and chores, even EQ1 can fail and detecting it is NP-complete for general additive $\\{-1,1\\}$ valuations. The paper's positive center is a normalized domain: if every agent values the entire set of items equally, then for symmetric bi-valued $\\{-1,1\\}$ valuations an EQX allocation always exists and can be computed in polynomial time for any number of agents. It also gives polynomial algorithms for EQ1 under $\\{-1,0,1\\}$ normalized valuations, for objective valuations, and for two agents with type-normalized valuations, plus pseudo-polynomial algorithms for welfare-maximizing EQX allocations.","feed_headline":"Fair split of mixed goods and chores exists for any number of agents","feed_subtitle":"New algorithms guarantee up-to-any-item fairness for subjective valuations, beyond two-agent cases known before.","key_machinery":"The poor-rich transfer algorithm (Algorithm 1). Starting from the empty allocation, the algorithm repeatedly gives a good to a poor agent, then a chore to a rich agent, until the only unallocated subjective items are chores for every poor agent and goods for every rich agent. To make progress it executes one of four transfers (rich-to-rich, rich-to-poor, poor-to-rich, poor-to-poor) that convert at least one poor or rich agent into a potential owner of an unallocated item while preserving EQ1. Normalization is what makes the counting argument work: in the reduced subjective instance every agent values exactly $k_1$ items at $+1$ and exactly $k_2$ items at $-1$; this counting rules out the case where no transfer is feasible, and the Completion Lemma then allocates the remaining objective items.","core_discovery":"The central discovery is that the obstruction to equitability is not the mixture of goods and chores itself but the disparity in agents' total values: with two agents and two items, if one agent values both items at $-1$ and the other values both at $+1$, no EQ1 allocation exists, and deciding existence is weakly NP-complete. Once values are normalized so every agent assigns the same total value to the grand bundle, the landscape changes. The main theorem (Theorem 4.1) claims that for symmetric bi-valued normalized valuations, every instance admits an EQX allocation and Algorithm 1 computes one in polynomial time. The proof first produces a partial EQ1 allocation of all subjective items via poor/rich transfers and then completes it with objective goods and chores using the Completion Lemma, preserving EQ1 throughout.","pith_inferences":["Editorial inference: the normalized/type-normalized distinction is likely the right boundary, since non-normalized two-agent instances can fail EQ1 entirely, so any broader guarantee must either weaken the fairness notion or add structural restrictions.","Editorial inference: the Completion Lemma suggests a modular design principle: future algorithms for richer valuation classes only need to solve the subjective core, because objective leftovers can be appended without breaking EQ1.","Editorial inference: a small exhaustive search over normalized $\\{-1,1\\}$ profiles would confirm the existential theorem independently of the transfer proof and could reveal whether the guarantee extends to asymmetric $\\{-a,b\\}$ valuations, which the paper leaves open."],"forward_implications":["For any number of agents, every normalized $\\{-1,1\\}$ instance has an EQX allocation, so the previous two-agent/objective barrier is removed.","Normalized $\\{-1,0,1\\}$ instances always admit an EQ1 allocation and one can be found in polynomial time, although EQX is not guaranteed in that setting.","Objective mixed instances, even without normalization, always admit an EQ1 allocation computable in polynomial time.","Two-agent type-normalized instances always admit EQ1; with $\\{-1,0,1\\}$ type-normalized values, an EQ1+PO allocation exists and is efficiently computable.","For a fixed number of agents, welfare-maximizing EQX allocations can be computed in pseudo-polynomial time."],"supporting_citations":[{"why":"Established EQX existence for two agents with objective valuations and hardness for non-objective valuations; the paper's Theorem 4.1 extends existence to any number of agents under normalized subjective valuations.","marker":"[Barman et al., 2024]"},{"why":"Established EQ1 existence and efficient computation for indivisible goods; the objective-valuation algorithm and Completion Lemma follow this template.","marker":"[Freeman et al., 2019a]"},{"why":"Established EQ1 existence for indivisible chores; the chores phase of Proposition 3.2 and Lemma 3.4 relies on the same rich-agent-receives-chore idea.","marker":"[Freeman et al., 2020]"},{"why":"Gives the polynomial-time Nash optimal allocation for binary valuations used in Algorithm 2 for EQ1+PO.","marker":"[Barman et al., 2018b]"},{"why":"Supplies the dynamic-programming state representation that Theorem 6.1 extends to welfare-maximizing EQX allocations for mixed instances.","marker":"[Aziz et al., 2023a]"},{"why":"Lemma 22 (for binary valuations, if any EQ1+PO allocation exists then every Nash optimal allocation is EQ1) is the key engine of Theorem 5.3.","marker":"[Freeman et al., 2019b]"}],"fun_headline_variants":["Normalized total value makes fair mixed-item allocation possible","Aligning agent totals yields equitable split of goods and chores","New algorithm ensures fairness when valuations share a total sum","Equal bundle values break the deadlock in mixed-item division","Fair split of pros and cons via normalized valuations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that all agents value the entire collection of items equally, which forces every agent to see the same number of liked and disliked items among the contested items; if that equality of total value fails, the transfer argument stalls and EQ1 may not even exist.","fun_headline_variants_meta":{"raw":{"variants":["Normalized total value makes fair mixed-item allocation possible","Aligning agent totals yields equitable split of goods and chores","New algorithm ensures fairness when valuations share a total sum","Equal bundle values break the deadlock in mixed-item division","Fair split of pros and cons via normalized valuations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000901,"raw_usage":{"total_tokens":3889,"prompt_tokens":967,"completion_tokens":2922,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":583,"completion_tokens_details":{"reasoning_tokens":2845}},"tokens_in":583,"tokens_out":2922,"duration_ms":23432,"temperature":1.0,"reasoning_tokens":2845,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T20:50:17.690246+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate every allocation of a small normalized $\\{-1,1\\}$ instance with, say, three agents and six subjective items where each agent values exactly two items at $+1$ and four at $-1$; the paper's Theorem 4.1 predicts that every such instance has an EQX allocation, so finding even one without one refutes the theorem. Running Algorithm 1 on random instances of the same type and checking that the output is EQX would provide the same test computationally.","supporting_citations":[],"review_version":1}