REVIEW 4 major objections 8 minor 2 cited by
Equitable Allocations of Mixtures of Goods and Chores
T0 review · 4 major / 8 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (4)
- [Appendix B, Lemma B.1, case |P| <= |R|] 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 4.1 and Algorithm 1] 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.
- [Appendix B, Theorem 4.3] 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.
- [Appendix C, Theorem 5.3, Eqs. (4)-(7)] 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.
minor comments (8)
- [Section 1.1] 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 3, proof of Theorem 3.1] 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 4.1, transfer 2] The condition for the Rich-Poor transfer reads 'v_r(o) = 1 = v_p(w)'; the symbol w should be o.
- [Section 2 and Lemma B.1] 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 6, Eqs. (1)-(3)] 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 1.2, Related Work] 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, ...'.
- [Appendix B, Table 6] 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.
- [Sections 1.1 and 1.2] 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.
Circularity Check
No significant circularity; the EQX algorithm is a construction against the definitions, with only non-load-bearing self-citations.
full rationale
The paper's central derivation is a constructive algorithm against the EQ1/EQX definitions, not a fit or a renaming. Theorem 4.1 is reduced to Lemma B.1 (existence of a partial EQ1 allocation exhausting O±) plus Lemma 3.4 (completion with objective items). Lemma B.1's four transfers are defined directly from valuation patterns; the subsequent counting argument uses only the normalization assumption and the absence of feasible transfers to derive a contradiction. No parameter in the proof is fitted to the target allocation, and no equation identifies the constructed allocation with an input quantity. The external ingredients (Nash optimality for binary valuations, Freeman et al. Lemma 5.5) are cited as black boxes and are not authored by the present authors in a load-bearing way; self-citations (Hosseini et al. 2023a,b; Bhaskar et al. 2023) appear only in related-work context. The appendix proof of Lemma B.1 is informal and leaves some proof obligations open (e.g., the |P|≤|R| normalization-counting contradiction and the claim that each transfer preserves the EQ1 invariant), but those are correctness gaps, not circularity: they do not assume the theorem's conclusion, and the transfers are not defined in terms of the desired EQ1 outcome. Hence no circular step is exhibited.
Assumptions & free parameters
assumptions (6)
- domain assumption Valuations are additive: vi(S) = sum of vi(o) over o in S.
- domain assumption Normalized instances: vi(O) is constant across agents.
- domain assumption Type-normalized instances: all goods sum to g and all chores sum to c for every agent.
- standard math Nash optimal allocation for binary valuations can be computed in polynomial time (Barman et al. 2018b).
- standard math Lemma 5.5 from Freeman et al. 2019b: if a binary instance admits an EQ1+PO allocation, every Nash optimal allocation satisfies EQ1.
- standard math 3-Partition is strongly NP-hard.
Cite this review
Pith. "Pith review of Equitable Allocations of Mixtures of Goods and Chores." pith.science (2026). https://pith.science/paper/4KXLO4CZ
@misc{pith2026250106799,
author = {Pith},
title = {Pith review of: Equitable Allocations of Mixtures of Goods and Chores},
year = {2026},
howpublished = {\url{https://pith.science/paper/4KXLO4CZ}},
note = {Machine review of arXiv:2501.06799}
}
abstract
Equitable allocation of indivisible items involves partitioning the items among agents such that everyone derives (almost) equal utility. We consider the approximate notion of \textit{equitability up to one item} (EQ1) and focus on the settings containing mixtures of items (goods and chores), where an agent may derive positive, negative, or zero utility from an item. We first show that -- in stark contrast to the goods-only and chores-only settings -- an EQ1 allocation may not exist even for additive $\{-1,1\}$ bivalued instances, and its corresponding decision problem is computationally intractable. We focus on a natural domain of normalized valuations where the value of the entire set of items is constant for all agents. On the algorithmic side, we show that an EQ1 allocation can be computed efficiently for (i) $\{-1, 0, 1\}$ normalized valuations, (ii) objective but non-normalized valuations, (iii) two agents with type-normalized valuations. Previously, EQX allocations were known to exist only for 2 agents and objective valuations, while the case of subjective valuations remained computationally intractable even with two agents. We make progress by presenting an efficient algorithm that outputs an EQX allocation for $\{-1,1\}$ normalized subjective valuations for any number of agents. We complement our study by providing a comprehensive picture of achieving EQ1 allocations in conjunction with economic efficiency notions such as Pareto optimality and social welfare.
Forward citations
Cited by 2 Pith papers
-
Best of Both Worlds Guarantees for Equitable Allocations
Ex ante equitable, ex post EQ1 randomized allocations always exist for two agents, but may not exist for three or more agents and their existence decision is NP-complete.
-
Achieving Equitability with Subsidy
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 welfar...
Reference graph
Works this paper leans on
-
[1]
If∃ r, r′∈ R and o∈ Ar : vr(o) =1 and vr′ (o) =−1, transfer o from Ar to Ar′
Rich-Rich Transfer (R-R). If∃ r, r′∈ R and o∈ Ar : vr(o) =1 and vr′ (o) =−1, transfer o from Ar to Ar′. This makes both r and r′ poor agents and potential owners of o∈ U
-
[2]
If∃ r∈ R, p∈ P and o∈ Ar : vr(o) =1 = vp(w), transfer o from Ar to Ap
Rich-Poor Transfer (R-P). If∃ r∈ R, p∈ P and o∈ Ar : vr(o) =1 = vp(w), transfer o from Ar to Ap. This makes r a poor agent and p a rich agent. Consequently, both of them become a potential owner of o∈ U
-
[3]
If∃ r∈ R, p∈ P and o∈ Ap : vp(o) =−1 = vr(o), transfer o from Ap to Ar
Poor-Rich Transfer (P-R). If∃ r∈ R, p∈ P and o∈ Ap : vp(o) =−1 = vr(o), transfer o from Ap to Ar. This makes r a poor agent and p a rich agent. Consequently, both of them become a potential owner of o∈ U
-
[4]
If∃ p, p′∈ P and o∈ Ap : vp(o) =−1 & vp′ (o) = 1, transfer o from Ap to Ap′
Poor-Poor Transfer (P-P). If∃ p, p′∈ P and o∈ Ap : vp(o) =−1 & vp′ (o) = 1, transfer o from Ap to Ap′. This makes both p and p′ rich agents and potential owners of o∈ U. We execute one of the transfers at a time, thereby converting at least one poor (rich) agent to rich (poor). Now, the remaining item o, which was earlier a chore for all the poor agents a...
-
[9]
With these valuations at hand, we are now ready to prove Lemma B.1
Every p values every chore in Ap′ at−1. With these valuations at hand, we are now ready to prove Lemma B.1. Proof of Lemma B.1. We start with the greedy allocation, executing the transfers one by one, allo- cating at least one unassigned item after every transfer, and then argue that until an unassigned good remains, one of the transfers can be executed. ...
-
[10]
If|P| >|R|, then we take a good (1-valued item) from Ar and allocate it to p who necessarily values it at−1 (else, there is an R-P transfer). We do this for |R| disjoint pairs of a rich and a poor agent, thereby decreasing the utility of all these pairs by −1. But since|P| >|R|, we have a poor agent p′ whose value remains intact, which in turn, makes him ...
-
[11]
Suppose|P|≤| R|. We will argue that this assumption leads to a contradiction to normaliza- tion, thereby settling the claim. Suppose under the partial EQ1 allocation A, we have vr(Ar) =k + 1 and vp(Ap) =k for some constant k. Since every rich agent r values every good in the bundle Ar′ of any other rich agent r′ at 1, we have that there are at least |R|(k...
-
[12]
If∃ r, r′∈ R and o∈ Ar : (vr(o), vr′ (o))∈{ (1, 0), (0,−1), (1,−1)}, transfer o from Ar to Ar′
Rich-Rich Transfer (R-R). If∃ r, r′∈ R and o∈ Ar : (vr(o), vr′ (o))∈{ (1, 0), (0,−1), (1,−1)}, transfer o from Ar to Ar′
Show all 16 references
-
[13]
If∃ r∈ R, p∈ P and o∈ Ar : (vr(o), vp(o))∈{ (1, 1), (1, 0), (0, 1)}, transfer o from Ar to Ap
Rich-Poor Transfer (R-P). If∃ r∈ R, p∈ P and o∈ Ar : (vr(o), vp(o))∈{ (1, 1), (1, 0), (0, 1)}, transfer o from Ar to Ap
-
[14]
If∃ r∈ R, p∈ P and o∈ Ap : (vp(o), vr(o))∈{ (−1, 0), (−1,−1), (0,−1)}, transfer o from Ap to Ar
Poor-Rich Transfer (P-R). If∃ r∈ R, p∈ P and o∈ Ap : (vp(o), vr(o))∈{ (−1, 0), (−1,−1), (0,−1)}, transfer o from Ap to Ar
-
[15]
If∃ p, p′∈ P and o∈ Ap : (vp(o), vp′ (o))∈{ (−1, 1), (0, 1), (−1, 0)}, transfer o from Ap to Ap′
Poor-Poor Transfer (P-P). If∃ p, p′∈ P and o∈ Ap : (vp(o), vp′ (o))∈{ (−1, 1), (0, 1), (−1, 0)}, transfer o from Ap to Ap′. Note that we execute one of the transfers at a time, thereby converting at least one poor (rich) agent to rich (poor). Now, the remaining item o, which w...
-
[16]
Every r values every good in Ar′ at 1
-
[17]
Every p values every good in Ar at−1
-
[18]
Every r values every chore in Ap at 1
-
[19]
Proof of Theorem 4.3
Every p values every chore in Ap′ at−1. Proof of Theorem 4.3. 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. Starting with a greedy allocation, executing the transfers one by one, allocati...
-
[2023]
Martin Aleksandrov and Toby Walsh
URL http://ceur-ws.org/Vol-3527/. Martin Aleksandrov and Toby Walsh. Two algorithms for additive and fair division of mixed manna. In KI 2020: Advances in Artificial Intelligence: 43rd German Conference on AI, Bamberg, Germany, September 21–25, 2020, Proceedings, page 3–17, Be...
2020
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.