{"id":"fde4f53d-ddd5-4643-9816-7bd217e9ae9d","arxiv_id":"1909.00740","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For mixed goods and chores, a weighted Pareto-optimal allocation that is proportional up to one item always exists and is computable in strongly polynomial time.","lead":"This paper presents a fast algorithm that always finds a fair-enough and efficient way to split indivisible items among people, even when some items are good for some and bad for others. It settles an open problem in fair division theory and gives a practical method for allocating mixed goods and chores.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The theorem's strong-polynomial claim rests on the unproved external Lemma 2.5 of [14]; without it, only a weakly polynomial self-contained Algorithm 2 is established.","rationale":"I agree with the reader's weakest_assumption. I checked the internal rounding proof for hidden fatal gaps: the zero-item preprocessing is safe because fPO implies all sharers of such an item have equal weighted utility; the at most-one-predecessor argument survives under the natural reading of the breadth-first exploration over agents sharing items; and the fPO preservation via G_x* being a subgraph of G_x is valid under Varian's supporting-weights theorem. The only unresolved load-bearing assumption is the external subroutine from [14]. The paper states this dependency openly, and the conditional verdict is appropriate. No verdict change is needed.","tokens_in":8487,"tokens_out":22307,"duration_ms":234648,"concrete_test":"Verify Lemma 2.5 of [14] in full: (1) confirm it applies to the specific proportional fractional allocation xprop with arbitrary agent weights b_i; (2) confirm the returned allocation x is fPO, Pareto-dominates xprop, and has an acyclic consumption graph; and (3) confirm the O(n^2 m^2(n+m)) bound counts arithmetic operations independently of the bit lengths of the utility values. If any of the three fails, restate Theorem 1 with only the weakly polynomial guarantee of Algorithm 2, or supply a new strongly polynomial proof of Step 2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's own rounding argument is internally convincing: acyclicity of the consumption graph limits each agent to at most one predecessor, so weighted PROP1 survives rounding, and the subgraph containment argument preserves fPO via Varian's supporting-weights characterization. The load-bearing gap is Step 2 of Algorithm 1: the existence and strong-polynomial bound of Theorem 1 depend on a subroutine from Sandomirskiy and Segal-Halevi [14] that, given the proportional equal-share allocation xprop, returns an fPO fractional Pareto improvement x with an acyclic consumption graph in O(n^2 m^2(n+m)) time. This lemma is not proved in the present paper. The self-contained alternative, Algorithm 2, solves a linear program in each iteration and is explicitly acknowledged by the authors to be only weakly polynomial. If Lemma 2.5 of [14] is not strongly polynomial, or if its acyclicity and Pareto-dominance guarantees fail for the arbitrary mixed-utility setting used here, then Theorem 1's strong-polynomial-time claim does not follow, although the existence result might still survive through the weakly polynomial Algorithm 2. The authors themselves flag this dependency in Section 4 when they write that one may wonder whether a conceptually simpler self-contained algorithm exists, so the concern is real and acknowledged rather than manufactured.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers fair allocation of indivisible items with additive utilities that may be positive, negative, or zero (mixed utilities). It claims that for any number of agents with positive weights, there always exists an integral allocation that is both fractionally Pareto optimal (fPO) and weighted proportional up to one item (weighted PROP1), and that such an allocation can be computed in strongly polynomial time. The proposed method first forms the equal-share fractional allocation, then uses an algorithm from Sandomirskiy and Segal-Halevi [14] to obtain an fPO Pareto-dominating fractional allocation with an acyclic consumption graph, and finally rounds this allocation through a queue-based tree exploration. The rounding is shown to preserve fPO and to guarantee weighted PROP1 because acyclicity implies each agent can have at most one predecessor, so each agent loses at most one good or gains at most one chore. The paper also provides a self-contained linear-programming-based Algorithm 2 that achieves the same existence result in weakly polynomial time, and it gives examples showing that strict strengthenings of PROP1 or PO do not hold.","tokens_in":8751,"tokens_out":14146,"duration_ms":128130,"significance":"If the main theorem is correct, it resolves an open problem in fair division for mixed utilities, unifying and extending previous results that were limited to goods, chores, or a fixed number of agents/items. The rounding argument is elegant and largely self-contained: the proof that acyclicity limits each agent to one predecessor is convincing, and the preservation of fPO via Varian's supporting-weights characterization is sound. The paper also provides a self-contained (though only weakly polynomial) algorithm, which would already establish the existence of fPO+weighted-PROP1 allocations. However, the strong-polynomial-time claim of Theorem 1 rests on an external lemma that is neither proved nor reproduced in this manuscript, and even the weakly polynomial Algorithm 2 depends on a supporting 'cyclic trade' argument cited from the same external source. These dependencies must be addressed before the central claim can be considered fully verified.","major_comments":[{"comment":"The strong-polynomial-time guarantee of Theorem 1 is not established within the paper. Step 2 of Algorithm 1 relies entirely on Lemma 2.5 of Sandomirskiy and Segal-Halevi [14], which asserts that, given the proportional fractional allocation, one can compute in strongly polynomial time an fPO fractional Pareto improvement with an acyclic consumption graph. This lemma is not proved in the present manuscript, and the paper does not reproduce its statement. In Section 4, the authors explicitly acknowledge that their self-contained Algorithm 2 is only weakly polynomial because it solves linear programs. Consequently, as written, the existence of a strongly polynomial algorithm does not follow from the arguments in this paper. The authors should either prove the needed lemma in an appendix, provide a peer-reviewed reference with a full proof, or clearly state Theorem 1 as conditional on [14] and state the strongest unconditional result separately.","section":"Section 3, Algorithm 1 Step 2; Theorem 1"},{"comment":"The correctness of Algorithm 2, offered as a self-contained alternative, also depends on an unproved external result. The algorithm argues that if the interim allocation has a cycle, there exists another allocation with the same utilities and a consumption graph that is a subgraph but omits some edge of the cycle; this is justified by a 'cyclic trade' argument 'as in the proof of Lemma 2.5 from [14]'. Since this cyclic-trade existence is not proved here, the acyclicity guarantee of Algorithm 2 is not fully supported. To make the paper self-contained, the authors should include a proof of this cyclic-trade claim, or, if it is considered standard, provide a complete citation to a published proof.","section":"Section 4, Algorithm 2"}],"minor_comments":[{"comment":"The footnote claims that the outer while-cycle takes an agent who shares exactly one item and that such an agent exists by acyclicity whenever at least one item is shared. This is false: in the acyclic path with items A, B, C and agents 1, 2, with edges (1,A), (1,B), (2,B), (2,C), every agent shares at least two items. The main algorithm text correctly says 'an agent i sharing at least one item', so the footnote should be corrected or removed.","section":"Algorithm 1 footnote (tie-breaking conventions)"},{"comment":"The informal description in the Introduction says PROP1 holds if an agent reaches her proportional guarantee after losing her biggest chore or obtaining the biggest good allocated to another agent, but the formal definition in Section 2 uses an existential 'some o' without requiring extremeness. Please align the two descriptions.","section":"Introduction and Section 2 (definition of PROP1)"},{"comment":"The examples are difficult to follow because the tables do not clearly mark which cells correspond to the allocation; the 'squares' mentioned in the text are not visible in the typeset version. Use explicit symbols (e.g., boldface or asterisks) to indicate the allocation.","section":"Appendix A, Examples 2 and 3"},{"comment":"The paper states that Algorithm 2 is weakly polynomial but does not provide a bound on the number of iterations. Since each iteration removes at least one edge from a cycle, the number of iterations is at most O(nm), and each LP can be solved in weakly polynomial time; stating this would make the complexity claim more precise.","section":"Section 4, Algorithm 2 complexity"}],"recommendation":"major_revision","confidential_remarks":"The central result is plausible and the rounding technique is valuable, but the strong-polynomial-time theorem depends on an external lemma that is not proved in the manuscript. Even the self-contained Algorithm 2 relies on a cited cyclic-trade argument. The authors should be asked to close this gap, either by proving the necessary lemma in an appendix or by presenting the contribution as conditional on a published source. In addition, the false footnote about the existence of an agent sharing exactly one item should be corrected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick read of Aziz–Moulin–Sandomirskiy (1909.00740). Verdict: this is a real result, and the main technique deserves attention. The paper proves existence of fPO and weighted PROP1 for mixed utilities with arbitrary numbers of agents and weights, and gives an algorithm claimed to be strongly polynomial. The rounding step is genuinely novel: starting from a fractional fPO allocation with acyclic consumption graph, it rounds without using competitive equilibrium prices. Each agent gets at most one predecessor in the tree, so she loses at most one good or gains at most one chore—that's exactly PROP1. fPO is preserved because the final consumption graph is a subgraph and Varian's supporting weights carry over. The proof is clean and the examples are helpful, especially the one showing PROPX can fail.\n\nThe soft spot is Step 2. The strong-polynomial-time input—an fPO fractional allocation that Pareto dominates the proportional one and has an acyclic graph—is imported, not proved here. It's Lemma 2.5 of Sandomirskiy–Segal-Halevi [14], a preprint by one of the present authors. If that lemma doesn't hold for all mixed-utility instances, the strong-polynomial claim collapses. But the existence result and a weakly polynomial algorithm survive via their Algorithm 2, which they honestly describe. So the dependency is explicit and the authors don't hide it. Still, a referee should verify [14] before signing off on the main theorem's complexity.\n\nWould I publish? Yes, conditionally. The result is important and the technique is a genuine contribution. The missing piece is verification of the external lemma, which is a standard refereeing task.\n\nRecommendation: send it out. The paper deserves serious referee time.","headline":"Genuinely new rounding algorithm resolves a real open problem, but the strong-polynomial claim rests on an unproved external lemma.","tokens_in":9232,"tokens_out":3450,"would_cite":true,"duration_ms":64407,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that weighted PROP1 and fractional Pareto optimality are simultaneously achievable for all mixed-utility instances, via a strongly polynomial algorithm based on acyclic rounding.","keywords":["fair division","indivisible items","mixed utilities","weighted PROP1","fractional Pareto optimality","strongly polynomial-time algorithm","acyclic consumption graph","proportionality up to one item"],"falsifier":"Search for a mixed-utility instance in which every fPO proportional fractional allocation Pareto-dominating equal division has a cyclic consumption graph, or in which no integral allocation is simultaneously weighted PROP1 and fPO; either would refute Theorem 1. Alternatively, show that the LP subroutine in the self-contained version cannot be solved in strongly polynomial time, which would remove the time guarantee.","tokens_in":8231,"feed_emoji":"⚖️","tokens_out":4669,"duration_ms":47903,"temperature":0.7,"pith_summary":"This paper proves that for any number of agents, any number of indivisible items, and additive utilities that may be positive, negative, or zero, there is always an integral allocation that is both fractionally Pareto optimal and weighted proportional up to one item (PROP1). The proof is constructive: a strongly polynomial-time algorithm exhibits such an allocation. This settles an open problem about mixed utilities, where items may be goods for some agents and chores for others, and covers asymmetric weights. The result also recovers known PROP1-and-Pareto-optimality theorems for goods-only and chores-only instances as special cases.","feed_headline":"Fair, efficient splits exist for mixed goods and chores","feed_subtitle":"New algorithm reaches weighted PROP1 and Pareto optimality in strongly polynomial time, for any number of agents.","key_machinery":"The central object is the consumption graph of a fractional allocation: a bipartite graph whose edges connect an agent to an item when the agent receives a positive fraction of it. The algorithm first obtains an fPO proportional fractional allocation with an acyclic consumption graph, so the graph decomposes into trees. The rounding step performs a breadth-first exploration of these trees, giving each active agent all shared goods and passing shared chores to a neighbor; acyclicity ensures each agent is worsened by at most one shared item, and the known characterization of fPO as weighted-welfare maximization ensures the rounded allocation remains fPO.","core_discovery":"The central discovery is that mixed-utility instances always admit an integral allocation that is simultaneously weighted PROP1 and fPO, a property stronger than ordinary Pareto optimality. The algorithm starts from the equal-division fractional allocation, computes an fPO fractional Pareto improvement whose consumption graph is acyclic, and then rounds this fractional allocation to an integral one by traversing the resulting forest of trees. Rounding preserves fPO because the final consumption graph remains a subgraph of a welfare-maximizing fractional allocation, and acyclicity guarantees that no agent loses two goods or gains two chores, which is exactly the weighted PROP1 guarantee.","pith_inferences":["The rounding scheme is modular: any method that produces an fPO proportional fractional allocation with an acyclic consumption graph would plug into the same PROP1-preserving rounding, so the hard part is isolated to a single subroutine.","The flexibility noted in the paper suggests one could randomize or optimize the choice of root agents and tie-breaking to select among many different PROP1-plus-fPO allocations, which may be useful for secondary objectives.","If the strongly polynomial subroutine for acyclic improvements were ever replaced by a weaker oracle, the existence result could still survive even while the strong time guarantee would not."],"forward_implications":["Weighted PROP1 and fPO allocations exist for every mixed-utility instance, closing the existence question for this fairness/efficiency pair.","The algorithm runs in strongly polynomial time in the number of agents and items, independent of the magnitudes of utilities.","Recent results for goods-only instances, chores-only instances, and the two-agent mixed case follow as corollaries.","The result is tight in several directions: strengthening PROP1 to EF1 or PROPX can break existence, and finding a utilitarian-optimal allocation among PROP1 allocations is NP-hard."],"supporting_citations":[{"why":"Supplies the Step-2 subroutine that computes an fPO fractional Pareto improvement with an acyclic consumption graph; the main theorem's strong polynomial-time guarantee relies on it.","marker":"[14]"},{"why":"Provides the characterization of fractional Pareto optimality as weighted welfare maximization, which the proof uses to show rounding preserves fPO.","marker":"[15]"},{"why":"Establishes the goods-only analog of PROP1 plus PO in strongly polynomial time, a result the paper generalizes.","marker":"[6]"},{"why":"Establishes the chores-only weighted PROP1 plus PO result for fixed n or m, which the paper extends to mixed utilities.","marker":"[7]"},{"why":"Proves the prior two-agent mixed-utility PO plus PROP1 result that Theorem 1 generalizes to any number of agents.","marker":"[2]"},{"why":"Posed the complexity of computing a PROP1 and PO allocation as an open problem, which the new algorithm answers.","marker":"[9]"}],"fun_headline_variants":["Always fair and efficient: polynomial algorithm for mixed utilities","Proportional and Pareto-optimal allocation in polynomial time","Mixed goods and chores: fair and efficient split in polynomial time","New algorithm guarantees weighted PROP1 and Pareto optimality"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument leans on a previously proven lemma that, from any proportional fractional allocation, one can find in strongly polynomial time a fractional Pareto improvement with an acyclic consumption graph; if that lemma fails, the strong time guarantee, and possibly the existence claim for all mixed instances, would not follow from this paper alone.","fun_headline_variants_meta":{"raw":{"variants":["Always fair and efficient: polynomial algorithm for mixed utilities","Proportional and Pareto-optimal allocation in polynomial time","Mixed goods and chores: fair and efficient split in polynomial time","New algorithm guarantees weighted PROP1 and Pareto optimality"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000247,"raw_usage":{"total_tokens":1442,"prompt_tokens":743,"completion_tokens":699,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":359,"completion_tokens_details":{"reasoning_tokens":634}},"tokens_in":359,"tokens_out":699,"duration_ms":7440,"temperature":1.0,"reasoning_tokens":634,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:38:58.402522+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search for a mixed-utility instance in which every fPO proportional fractional allocation Pareto-dominating equal division has a cyclic consumption graph, or in which no integral allocation is simultaneously weighted PROP1 and fPO; either would refute Theorem 1. Alternatively, show that the LP subroutine in the self-contained version cannot be solved in strongly polynomial time, which would remove the time guarantee.","supporting_citations":[{"cited_title":"Efficient Fair Division with Minimal Sharing","cited_arxiv_id":"1908.01669","evidence_quote":"Supplies the Step-2 subroutine that computes an fPO fractional Pareto improvement with an acyclic consumption graph; the main theorem's strong polynomial-time guarantee relies on it."},{"cited_title":"R., 1976","cited_arxiv_id":null,"evidence_quote":"Provides the characterization of fractional Pareto optimality as weighted welfare maximization, which the proof uses to show rounding preserves fPO."},{"cited_title":"K., 2019","cited_arxiv_id":null,"evidence_quote":"Establishes the goods-only analog of PROP1 plus PO in strongly polynomial time, a result the paper generalizes."},{"cited_title":"Fair allocatio n of combinations of indivisible goods and chores","cited_arxiv_id":null,"evidence_quote":"Proves the prior two-agent mixed-utility PO plus PROP1 result that Theorem 1 generalizes to any number of agents."},{"cited_title":"Fair public decision makin g","cited_arxiv_id":null,"evidence_quote":"Posed the complexity of computing a PROP1 and PO allocation as an open problem, which the new algorithm answers."}],"review_version":1}