{"id":"65141162-5a0c-4cc6-9f6c-7e23f6205524","arxiv_id":"1908.01669","paper_version":3,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"For generic additive valuations, the paper claims a polynomial-time algorithm for a fair, fractionally Pareto-optimal division with the minimum number of shared objects, and NP-hardness for degenerate valuations.","lead":"The paper proposes minimizing how many objects must be shared in order to achieve a fair and efficient division of goods and bads. It claims a polynomial-time algorithm for generic instances, but a central graph characterization used in the proof fails for mixed goods and bads.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.1 is false for mixed-sign valuations: an fPO allocation can contain a negative-product directed cycle, so the fPO test and graph enumeration are unsound.","rationale":"The paper is clearly written and the high-level enumeration idea is attractive, but this is a demonstrated false lemma rather than a missing edge case in one proof. The positive theorem depends on enumerating exactly the fPO consumption graphs and on testing candidate graphs with Lemma 2.2; the proposed fPO test is invalid on a three-agent mixed-sign instance, so the polynomial-time guarantee is unsupported. The reader's weakest assumption identifies the same load-bearing defect, and the verdict of REJECT is appropriate. I also credit the accompanying experiments and the apparent soundness of the NP-hardness construction, but these do not repair the proof of Theorem 3.6(a). A corrected fPO characterization or an alternative enumeration argument would be needed before the central claim could be accepted.","tokens_in":24923,"tokens_out":15405,"duration_ms":159229,"concrete_test":"Run the negative-cycle fPO test from Lemma 2.2 on the 3x3 instance above: values v_A=(-1/2,1,1), v_B=(1,-1/2,1), v_C=(1,1,-1/2); allocation z_A=(0,1/2,1/2), z_B=(1/2,0,1/2), z_C=(1/2,1/2,0). First certify fPO by noting that λ=(1,1,1) makes every object go to its maximizers of λ_i v_i,o. Then compute the directed cycle A→x→B→y→C→z→A: 0.5*1*0.5*1*0.5*1 = 0.125 < 1. If the test outputs 'not fPO', Lemma 2.1 is false as stated and the enumeration filter in Lemma 3.10 can discard a valid fPO support graph. A direct LP search for a dominating allocation can be used as an independent confirmation that the allocation is fPO.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 2.1's 'only if' direction fails for mixed goods and bads. In Definition 2.2, an edge i→o is created not only when i consumes a good that i_{k+1} also values positively, but also when v_i,o<0 and z_i,o<1, i.e., when i does not consume o at all. Appendix A's proof handles only the all-positive case and the all-negative case, omitting mixed-sign edges. Concretely, take n=m=3 with valuation columns x=(-1/2,1,1), y=(1,-1/2,1), z=(1,1,-1/2), and give each object half to each of its two positive-valued agents: z_A=(0,1/2,1/2), z_B=(1/2,0,1/2), z_C=(1/2,1/2,0). With λ=(1,1,1), every object is allocated to agents maximizing λ_i v_i,o, so z is fPO. Yet the directed graph contains the cycle A→x→B→y→C→z→A with edge weights 1/2,1,1/2,1,1/2,1 and product 1/8<1. Thus the cycle condition of Lemma 2.1 rejects a genuinely fPO allocation. Since Lemma 2.2 uses this condition to test fPO and Lemma 3.10 uses that test to prune the enumerated graph set, Proposition 3.8 and Theorem 3.6(a) lack a valid derivation: the enumeration step can discard the optimal fPO graph. The NP-hardness direction (b) is not affected by this counterexample.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a sharing-minimization approach to fair division of divisible objects that may be goods or bads. For a fixed number of agents, it develops an algorithm that, for valuations with low 'degree of degeneracy' (in particular, generic valuations), finds a proportional or envy-free fractionally Pareto-optimal allocation with the minimum number of sharings in polynomial time. For highly degenerate valuations, it claims NP-hardness. The algorithm enumerates all consumption graphs of fPO allocations and solves a small LP for each graph. The theoretical results are complemented by experiments on data from the Spliddit platform.","tokens_in":25284,"tokens_out":13868,"duration_ms":123684,"significance":"If the main theorem were correct, the paper would be a valuable contribution: a tractability result for an optimization problem in fair division, with a clean dichotomy based on a natural measure of degeneracy, plus an implemented algorithm with real-data experiments. The paper also contains useful building blocks, including a dynamic-programming enumeration of fPO graphs and a connection to Fisher markets and prior algorithms for pure goods or pure bads. However, the central characterization of fractional Pareto-optimality via directed consumption graphs is false for mixed-sign valuations, and this invalidates the correctness proof of the main positive result.","major_comments":[{"comment":"The 'only if' direction of the cycle characterization in Lemma 2.1 is false for mixed-sign valuations. The proof in Appendix A assumes that for every edge i_k->o_k in a cycle, either agent i_k consumes o_k and both i_k and i_{k+1} value o_k positively, or agent i_{k+1} consumes o_k and both value o_k negatively. However, the definition of the directed consumption graph also creates an edge i_k->o_k when z_{i_k,o_k}<1 and v_{i_k,o_k}<0, and an edge o_k->i_{k+1} when z_{i_{k+1},o_k}<1 and v_{i_{k+1},o_k}>0. In this mixed-sign case, neither of the transfers described in the proof is feasible: i_k does not own o_k, and i_{k+1} values o_k positively. A concrete counterexample is n=m=3 with valuation columns x=(-1/2,1,1), y=(1,-1/2,1), z=(1,1,-1/2) and allocation z_A=(0,1/2,1/2), z_B=(1/2,0,1/2), z_C=(1/2,1/2,0). This allocation maximizes the unweighted sum of utilities and is therefore fPO, yet the directed graph contains the cycle A->x->B->y->C->z->A with product 1/8<1. Thus the cycle condition is not necessary for fPO. A variant with z_A=(0,1/2,1/2), z_B=(1,0,1/2), z_C=(0,1/2,0) is also fPO, has exactly n-1=2 sharings, and contains the mixed-sign cycle A->x->C->y->A with product 1/2<1, showing that the flaw directly affects allocations within the n-1 sharing bound.","section":"Lemma 2.1 and Appendix A"},{"comment":"Because Lemma 2.2 is derived from Lemma 2.1, the negative-cycle test can produce false negatives for fPO allocations with mixed-sign edges. The counterexample above would be classified as non-fPO by this test. Since Lemma 3.10 uses Lemma 2.2 to filter the enumerated graph set on the way to G_v, the enumeration in Proposition 3.8 can discard valid fPO consumption graphs, including the graph of an optimal fair allocation. Consequently, the correctness proof of Theorem 3.6(a) is unsupported: the algorithm may fail to find a fair fPO allocation with the minimum number of sharings. This is not a minor gap but a failure of the central characterization on which the main algorithmic claim rests.","section":"Lemma 2.2 and Theorem 3.6(a)"},{"comment":"The proof of Lemma 2.5 asserts that the allocation z* obtained after eliminating all cycles with pi(C)<=1 is fractionally Pareto-optimal by Lemma 2.1. Since Lemma 2.1 is false for mixed valuations, this assertion is not justified. Although Lemma 2.5 might be true by other arguments (e.g., from known results for goods/bads and convexity of the utility possibility set), the proof as written is invalid. Lemma 2.5 is used in the main algorithm (step 1 of the second phase in Theorem 3.6) to justify restricting attention to graphs with at most n-1 sharings, so this compounds the effect of the first two comments.","section":"Appendix B and Lemma 2.5"}],"minor_comments":[{"comment":"The definition of the weighted directed consumption graph is intricate, and the proof of Lemma 2.1 would be easier to verify if the authors explicitly enumerated the four cases that can give rise to an edge i->o and an edge o->j, rather than only the two cases where agents agree on the sign of the object.","section":"Section 2.2"},{"comment":"The experimental section implements the algorithm only for pure goods, so the mixed-valuation case, which is the source of the theoretical difficulty, is not validated computationally. This is a limitation, though a minor one relative to the correctness issue.","section":"Section 4"}],"recommendation":"reject","confidential_remarks":"The paper addresses an interesting and timely problem, and the proposed dichotomy based on the degree of degeneracy is appealing. However, the central lemma characterizing fPO via directed cycles is false for mixed valuations, and the provided counterexample directly invalidates the fPO test and the graph-enumeration step. Since the main positive result (Theorem 3.6(a)) relies on this characterization, the manuscript cannot be accepted in its current form. The error is not a presentation issue; it requires reworking the graph definition or restricting the model, which would likely change the main claims. The NP-hardness direction (Theorem 3.6(b)) and the two-agent results for pure goods appear unaffected, but the overall contribution as stated is not established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper has a good question and promising-looking machinery, but the central characterization does not hold for mixed valuations. I agree with the stress-test counterexample. Lemma 2.1 is false as stated, and the main positive theorem leans on it.\n\nWhat is actually new: the sharing-minimization objective, the degeneracy-based complexity dichotomy, and the dynamic-programming enumeration of fPO graphs. The writing is clear, related work is broad, and the authors are upfront that mixed valuations make the graph construction tricky. The public Python implementation and Spliddit experiments are a genuine plus, even if they cannot rescue an unproven algorithm. The citation pattern looks honest; prior results are used as building blocks, not as the conclusion.\n\nWhere it breaks: the \"only if\" direction of Lemma 2.1 assumes that each edge i→o in the weighted graph comes from either a consumed good or an object bad to both agents. But the graph definition also creates i→o when v_i,o < 0 and z_i,o < 1, i.e., when i does not consume o and the next agent values o positively. The stress-test example is correct: with the three-agent valuation matrix x=(-1/2,1,1), y=(1,-1/2,1), z=(1,1,-1/2) and the allocation giving each object half to each positive agent, λ=(1,1,1) shows the allocation maximizes weighted sum, hence is fPO by Lemma 2.3, yet the cycle A→x→B→y→C→z→A has product 1/8 < 1. So the cycle condition is not necessary. Because Lemma 2.2 uses this condition to test fPO, and Lemma 3.10 uses that test to prune enumerated graphs, the enumeration can discard the optimal fPO graph. This is a load-bearing flaw, not a minor bug.\n\nThe NP-hardness direction (b) seems unaffected, and the two-agent non-degenerate case might be salvaged with a corrected test. A repair is plausible—maybe a different edge-weight convention or an extra condition for mixed edges—but the onus is on the authors.\n\nWho this is for: people working on fair division with mixed manna and on exact tractability boundaries. I would send it to referees rather than desk-reject; the flaw is sharp and the question deserves a serious answer, but acceptance should wait for a correct characterization.","headline":"The central cycle characterization is false for mixed valuations—the stress-test counterexample is correct—so the main positive algorithm is unproven, but the question is good and the NP-hardness half looks sound.","tokens_in":25759,"tokens_out":7223,"would_cite":false,"duration_ms":70742,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"For a fixed number of agents, fair efficient divisions minimizing shared objects are polynomial for generic valuations, and NP-hard when valuation ratios align.","keywords":["fair division","sharing minimization","fractional Pareto optimality","envy-freeness","proportionality","mixed valuations","degeneracy","goods and bads"],"falsifier":"Take a specific three-agent mixed goods-and-bads instance, compute an fPO allocation, and check whether the paper's weighted directed consumption graph contains a cycle with product less than 1; if such a cycle appears, Lemma 2.1 and the enumeration step that depends on it are refuted. Alternatively, run the algorithm on a small constructed instance and compare its output against brute-force search over all allocations for small $m$.","tokens_in":24693,"feed_emoji":"⚖️","tokens_out":7356,"duration_ms":70790,"temperature":0.7,"pith_summary":"This paper asks: when a collection of goods and bads must be divided fairly and efficiently, how many objects really have to be shared among agents? It shows that for a fixed number of agents and generic valuation data, a fair and fractionally Pareto-optimal allocation with the minimum possible number of shared objects can be computed in polynomial time in the number of objects. For degenerate instances, where many objects have the same value ratios between agents, the same problem becomes NP-hard even for two agents. The practical upshot is that the difficult cases are exactly those in which agents' tastes are aligned, rather than the typical case of diverse preferences.","feed_headline":"Minimizing shared objects is easy when tastes differ","feed_subtitle":"Fair efficient division with fewest sharings is polynomial for generic preferences; aligned valuations make it NP-hard.","key_machinery":"The central object is the weighted directed consumption graph $\\overrightarrow{CG}_z$ of an allocation $z$: an edge from agent $i$ to object $o$ appears when $i$ consumes $o$ and values it non-negatively (weight $v_{i,o}$) or when $i$ does not fully consume $o$ and values it negatively (weight $|v_{i,o}|$); reverse edges are defined symmetrically. The load-bearing identity is Lemma 2.1: $z$ is fractionally Pareto-optimal if and only if it is non-malicious and no directed cycle $C$ has product of edge weights $\\pi(C) < 1$. This reduces fPO-checking to negative-cycle detection (Lemma 2.2) and lets the algorithm enumerate all candidate fPO consumption graphs, first for two agents via ratio thresholds (Lemma 3.9) and then by adding agents one at a time (Lemma 3.10), before solving a constant-size linear program per graph for the fairness constraint. The degree of degeneracy $D_v$ controls how many graphs exist: the count is at most $3^{(1+D_v)n(n-1)/2} m^{n(n-1)/2}$.","core_discovery":"The paper's central claim is a complexity dichotomy for sharing-minimization. For a fixed number of agents $n$ and a valuation matrix $v$ over $m$ objects, let $D_v$ be the degree of degeneracy, the largest number of excess objects on which any two agents share the same value ratio. Theorem 3.6(a) states that an allocation minimizing the number of sharings subject to fractional Pareto-optimality and proportionality or envy-freeness can be computed in $O(3^{n(n-1)D_v/2} m^{n(n-1)/2+2})$ operations, which is strongly polynomial whenever $D_v = O(\\log m)$; for generic instances $D_v = 0$ with probability 1. Theorem 3.6(b) states that checking the existence of a fair fractionally Pareto-optimal allocation with zero sharings is NP-hard when $D_v \\ge C m^\\alpha$, so the hardness comes precisely from aligned valuations.","pith_inferences":["One can test how often real preference data fall in the strongly-polynomial regime by computing $D_v$ on collected valuation matrices; the paper's experiments suggest practical instances are often easy, but a systematic distributional study is left open.","The graph-enumeration recipe is transferable: any fair-division problem whose Pareto frontier has a polynomially sized graph representation could be solved by the same 'enumerate graphs, then solve a small LP' pattern, for example rent division or consensus halving with sharing costs.","The contrast with discrete Pareto-optimality suggests that fractional Pareto-optimality, not fairness, is the feature that buys algorithmic tractability; one could try replacing fairness notions like EF1 with fPO to see whether other sharing-minimization variants become polynomial."],"forward_implications":["For fixed $n$ and typical (non-degenerate) valuations, the minimal number of sharings can be computed exactly in polynomial time, so sharing minimization becomes a practical exact tool rather than a heuristic.","When $D_v = O(\\log m)$, the run time is strongly polynomial; since $D_v=0$ generically, almost all instances drawn from a continuous distribution are easy.","The same enumeration can handle other fairness constraints that are linear in the allocation (weighted envy-freeness, weighted proportionality) and other sharing objectives, because the LP size depends only on $n$.","Dropping fractional Pareto-optimality makes the problem NP-hard even for non-degenerate valuations (Remark 3.4), so efficiency is not an obstacle but the source of tractability."],"supporting_citations":[{"why":"Supplies the worst-case bound that an envy-free fractionally Pareto-optimal allocation with at most n-1 sharings always exists for pure goods or bads, used to restrict the search.","marker":"Bogomolnaia et al. 2016"},{"why":"Provides the fPO characterization for bads and algorithms for competitive allocations that the paper extends to mixed valuations.","marker":"Branzei and Sandomirskiy 2019"},{"why":"Establishes existence of envy-free fractionally Pareto-optimal allocations for mixed manna, used in Corollary 2.6.","marker":"Bogomolnaia et al. 2017"},{"why":"Gives the negative-cycle detection algorithm used by Lemma 2.2 to check fractional Pareto-optimality in the enumeration step.","marker":"Cherkassky and Goldberg 1999"},{"why":"Shows that random large instances admit zero-share fair allocations with high probability, motivating the sharing-minimization objective.","marker":"Dickerson et al. 2014"},{"why":"Documents hardness of discrete Pareto-optimality, providing the contrast that makes the new fractional-PO polynomial results nontrivial.","marker":"de Keijzer et al. 2009"}],"fun_headline_variants":["Fair sharing: easy when tastes differ, hard when aligned","Minimal sharing in fair division is easy for generic tastes","Fewest shared objects: polynomial unless valuations align","Fair efficient division: simple for diverse tastes, hard for aligned","Divide with minimal sharing: trivial generically, tough for aligned"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the graph criterion that an allocation is fractionally Pareto-optimal exactly when its weighted trade graph has no cycle whose product of edge weights is less than 1; if that criterion fails for goods-and-bads instances, the enumeration can skip the true optimum.","fun_headline_variants_meta":{"raw":{"variants":["Fair sharing: easy when tastes differ, hard when aligned","Minimal sharing in fair division is easy for generic tastes","Fewest shared objects: polynomial unless valuations align","Fair efficient division: simple for diverse tastes, hard for aligned","Divide with minimal sharing: trivial generically, tough for aligned"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000474,"raw_usage":{"total_tokens":2330,"prompt_tokens":896,"completion_tokens":1434,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":512,"completion_tokens_details":{"reasoning_tokens":1353}},"tokens_in":512,"tokens_out":1434,"duration_ms":11324,"temperature":1.0,"reasoning_tokens":1353,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:08:52.731634+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a specific three-agent mixed goods-and-bads instance, compute an fPO allocation, and check whether the paper's weighted directed consumption graph contains a cycle with product less than 1; if such a cycle appears, Lemma 2.1 and the enumeration step that depends on it are refuted. Alternatively, run the algorithm on a small constructed instance and compare its output against brute-force search over all allocations for small $m$.","supporting_citations":[],"review_version":1}