{"id":"d4d9649f-c872-457c-929a-5dd328014108","arxiv_id":"2607.18220","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An explicit unweighted-coverage example shows that EF1 and Pareto optimality can be incompatible for submodular valuations, with an NP-hardness reduction for three agents.","lead":"This paper gives a two-agent, six-item counterexample to the long-open question of whether EF1 and Pareto-optimal allocations always exist for submodular valuations, plus an NP-hardness companion for three agents. The central goods example is correct, though the write-up leaves several verification steps to the reader.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's PO characterization is asserted, not proven; if incomplete, an EF1+PO allocation could slip through. Need an exhaustive enumeration or a domination argument.","rationale":"The reader identified the same weakest assumption: the PO characterization in Theorem 1 is asserted rather than derived. My own quick analysis suggests the theorem is true because any allocation without a 7-valued bundle is Pareto-dominated by one of the two exhibited allocations, and both are not EF1. However, this domination argument is missing from the paper, so the proof is incomplete as written. The central claim depends on this step, and the NP-hardness proof explicitly reuses it. I also note a possible parity issue in Theorem 3 (for odd n, a graph with minimum vertex cover (n+1)/2 may admit an EF1+PO allocation using a (5,7) M-pattern and a vertex cover of size (n+1)/2, which would violate Claim 5.3 as stated), but since the central contribution is the nonexistence result, the PO-characterization gap is the single most load-bearing concern. The reader's CONDITIONAL verdict is appropriate: the result is plausible and likely correct, but the paper should supply an exhaustive verification or a formal domination proof before being accepted.","tokens_in":10132,"tokens_out":27436,"duration_ms":221762,"concrete_test":"Write an exhaustive checker for the 6-item, 2-agent instance: enumerate all 64 allocations, compute (v1(X1), v2(X2)), keep only Pareto-undominated pairs, and test each for EF1. Confirm the undominated set is exactly {(7,5), (5,7)} and neither is EF1. Also verify the valuations match the indicator formulas in §3 to catch any transcription error.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1 rules out an allocation with values (6,6) and shows that if one agent gets a 7-valued bundle the other gets at most 5, but then jumps to 'the only Pareto optimal allocations should assign a bundle of value 7 to one agent and a bundle of value 5 to another agent' without ruling out, e.g., utility pairs (6,5) or (5,6). Such pairs would be Pareto dominated by the (7,5)/(5,7) allocations, but the paper does not supply that argument or an exhaustive enumeration. If the PO-set were incomplete and some overlooked PO allocation satisfied EF1, the main claim would fail. The NP-hardness reduction in Section 5 inherits this same PO characterization, so the gap propagates to Theorem 3.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses the open question of whether EF1 and Pareto-optimal allocations of indivisible goods always exist when agents have monotone submodular valuations. It proposes a negative answer via a two-agent, six-item instance with unweighted coverage valuations for which no EF1+PO allocation is claimed to exist (Theorem 1), a chores analogue (Theorem 2), and an NP-hardness result for deciding EF1+PO existence with three agents (Theorem 3). The central construction is explicit and directly checkable; the main weaknesses are in the proof of the Pareto-optimal frontier and in the NP-hardness reduction.","tokens_in":10322,"tokens_out":40861,"duration_ms":355978,"significance":"If correct, this settles a longstanding open problem and strengthens the nonexistence frontier from monotone subadditive valuations to unweighted coverage valuations, a strict subclass of monotone submodular valuations. The explicit two-agent example is a valuable, falsifiable construction, and the NP-hardness companion is a natural further contribution. However, acceptance requires a rigorous derivation of the Pareto frontier; the current text contains a false enumeration of value-7 bundles, an unsupported PO-characterization step, and the stated reduction has an odd-n issue. These problems appear fixable, but they are load-bearing as written.","major_comments":[{"comment":"The statement \"for agent1, the only bundles of value 7 are {p1,p2,p3,r}, {p1,p2,p3,r1}, and {p1,p2,q,r1}\" is false. Using the displayed formula for v1, the bundle {p1,p2,r,r1} satisfies all seven indicator terms: p1 and p2 are present, the p3∨r1 term is true, the r∨r1 term is true, and all three r-containing terms are true. Hence v1({p1,p2,r,r1})=7. This omitted case is not covered by the subsequent list of complements, and the conclusion that the only PO allocations are (i) and (ii) rests on this list. The theorem may still be true, but a correct derivation of the PO frontier must be supplied.","section":"§3, proof of Theorem 1"},{"comment":"The inference \"Hence the only Pareto optimal allocations should assign a bundle of value 7 to one agent and a bundle of value 5 to another agent\" is not justified. Claims 3.1–3.2 rule out a (6,6) utility pair and bound complements of 7-bundles, but they do not rule out allocations with utility pairs such as (6,5), (5,6), (7,4), or (4,7), nor do they argue that every such pair is Pareto dominated by (7,5) or (5,7). A complete proof can be obtained by enumerating the 64 allocations or by an explicit domination argument; the text currently supplies neither.","section":"§3, proof of Theorem 1 (after Claims 3.1–3.2)"},{"comment":"The assertion \"any allocation X where |X1∩P| > n/2 is not EF1 as a3 EF1-envies a1\" is false for odd n. For n=2k+1 and |X1∩P|=k+1, agent 3 holds k P-items, and after removing one P-item from X1 the value to a3 is k, so agent 3 does not EF1-envy a1. The actual EF1 condition for a3 is |S|-1 ≤ n-|S|, i.e., |S| ≤ (n+1)/2. The reduction therefore needs to restrict Balanced Vertex Cover to even n, or state an appropriate threshold; otherwise Claim 5.3 is incorrect as stated.","section":"§5, Claim 5.3"},{"comment":"The Pareto-optimality arguments in the reduction are asserted rather than proved. In particular, the sentence \"From Theorem 1, X2 is the best possible bundle for a2, and there is no Pareto dominating allocation of items in M\" does not establish full PO, because a full allocation can also reallocate P-items between a1 and a3, and agent 3's valuation is zero on M; such reallocations are not analyzed. Similarly, the claims that every PO allocation must give a2 no P-items and a1 no strict superset of a vertex cover require proofs that rule out compensating trades involving M-items. Without these arguments, the correctness of the reduction is not established.","section":"§5, Claims 5.2–5.3"}],"minor_comments":[{"comment":"In the EF1-check for allocation (i), the text writes \"v2(X2\\{g})=6 for any g∈X1\"; this should be \"v2(X1\\{g})=6\" (or similar), since the item removed should be from the envied bundle X1.","section":"§3, proof of Theorem 1"},{"comment":"Balanced Vertex Cover is stated as \"vertex cover of size at most n/2\" without specifying whether n is even. Since the proof has a parity-sensitive step, the definition should say \"n even\" or \"at most floor(n/2)\" and the reduction should be adjusted accordingly.","section":"§5, Definition 5.1"},{"comment":"The rendering of Table 1 makes the coverage sets hard to verify. It would be clearer to list each item's covered universe explicitly, e.g., p1={u1,u5}, p2={u2,u6}, p3={u3,u7}, q={u5,u6,u7}, r={u4,u5,u6,u7}, r1={u3,u4}, as in the formulas.","section":"Table 1"},{"comment":"The chores proof is dense and the PO-frontier is assembled informally. A compact table of the Pareto frontier, or an explicit statement that the listed disutility pairs are exhaustive and attained, would make the proof much easier to verify.","section":"§4, Claims 4.1–4.3"}],"recommendation":"major_revision","confidential_remarks":"The central two-agent counterexample appears to be correct, and the overall direction is significant. The main barriers are proof rigor: the false enumeration of value-7 bundles, the unsupported PO-frontier claim in Theorem 1, and the reduction's parity and PO-handling issues. These are fixable but require real work, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know: the main claim is likely correct. The six-item coverage instance in Table 1 genuinely admits no EF1+PO allocation for monotone submodular valuations. The reader's enumeration checks out: the only PO utility pairs are (7,5) and (5,7), and both fail EF1 because removing any item from the value-7 bundle leaves value 6. That is a real counterexample, and it moves the nonexistence frontier from subadditive to unweighted coverage valuations.\n\nWhat's new: the explicit 2-agent 6-item instance; the corollary for chores (prior work already had chores nonexistence, but this is a cleaner coverage example); and the NP-hardness reduction for 3 agents. The construction is simple and the paper is honest about related work.\n\nThe main weakness is the proof of Theorem 1. The paper shows no (6,6), and that a 7-valued bundle leaves the other agent at most 5, but then jumps to \"hence the only PO allocations are ...\" without spelling out why (6,5) or (5,6) can't be PO. They are dominated by the exhibited (7,5)/(5,7) allocations, but the text needs to say that. It's a short missing argument, not a hole in the result. Claim 5.3 says \"a3 EF1-envies a1\" in allocation (i); the envier is a2, as in Theorem 1. The NP-hardness reduction also assumes Balanced Vertex Cover with n even; the paper doesn't say so, and the proof's |X1∩P| > n/2 step uses that. The chores section is terse and hard to follow, but the claims seem plausible.\n\nIf I were refereeing, I'd ask for the missing domination argument, a correction of the envier label, and a note on the parity assumption. None of these should sink the paper.\n\nBottom line: this is a good paper for the fair division crowd. It deserves a serious referee. I would bring it to reading group and would cite the main theorem once it's publicly vetted.","headline":"The 2-agent coverage counterexample is real and settles the open problem if the write-up is tightened; the NP-hardness section has loose ends but nothing that smells fatal.","tokens_in":10765,"tokens_out":23177,"would_cite":true,"duration_ms":191375,"reading_group":"yes","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":"The paper constructs a two-agent, six-item instance with unweighted coverage valuations in which no allocation is simultaneously envy-free up to one item and Pareto optimal, settling the submodular case negatively, and proves that deciding","keywords":["fair division","EF1","Pareto optimality","submodular valuations","unweighted coverage valuations","NP-hardness","chores","indivisible goods"],"falsifier":"Enumerate all 64 allocations of the six items in Table 1 and test each for EF1 and Pareto optimality under the two coverage valuations; in particular, check whether any Pareto-optimal allocation with utility pair (6,5) or (5,6) exists, since the proof does not explicitly rule those out. A single EF1+PO allocation would disprove Theorem 1.","tokens_in":9999,"feed_emoji":"⚖️","tokens_out":8003,"duration_ms":74829,"temperature":0.7,"pith_summary":"This paper tries to establish that the longstanding open problem of whether fair-and-efficient allocations always exist under monotone submodular valuations has a negative answer. It presents a two-agent, six-item example, where each agent's valuation counts how many coverage elements its items cover, and proves that no allocation is both envy-free up to one item (EF1) and Pareto optimal (PO). The same six-item table also works when items are chores rather than goods. The paper further proves that deciding whether an EF1+PO allocation exists is NP-hard for three agents with monotone submodular valuations. If correct, this pins the existence frontier between matroid-rank valuations, where EF1+PO always exists, and broader subadditive valuations, where it can already fail.","feed_headline":"Six items end fair-and-efficient guarantee for submodular valuations","feed_subtitle":"A two-agent coverage instance has no EF1+PO allocation; with three agents, deciding existence is NP-hard.","key_machinery":"Unweighted coverage valuations — each item is a set of elements and a bundle's value is the number of distinct elements covered — form the central mechanism: they are monotone submodular but simpler than general submodular functions. The six-item table is engineered so that value 7 is attainable only with p1 and p2 together, and the proof uses indicator-variable formulas for the two valuations to argue that the only Pareto-optimal allocations are the two displayed. For NP-hardness, the reduction attaches one item per graph vertex and makes agent 1's value combine the coverage table with the number of edges covered by chosen vertices, forcing a balanced vertex cover.","core_discovery":"The core claim is Theorem 1: the two-agent, six-item coverage-valuation instance in Table 1 has no EF1+PO allocation. The proof characterizes Pareto-optimal allocations as those giving one agent value 7 and the other value 5, lists the two candidate allocations, and observes that in each case removing any good from the 7-bundle leaves the other agent's envy. The paper extends the same table to chores (Theorem 2) and uses a reduction from balanced vertex cover to prove NP-hardness for three-agent instances (Theorem 3).","pith_inferences":["The proof as written leaves an enumeration gap: it asserts, rather than derives, that the only Pareto-optimal utility pairs are (7,5) and (5,7), skipping the (6,5) and (5,6) cases; this is a proof-level gap, not a counterexample, and a brute-force check would close it.","Because the NP-hardness reduction embeds the two-agent counterexample, any revision that weakens Theorem 1 would also destabilize Theorem 3; conversely, if Theorem 1 holds, the hardness persists under a very constrained valuation class.","The chores result is essentially a byproduct of the symmetry between the two valuations; one can test whether small perturbations, such as giving each item a private coverage element, restore existence, which would align with the paper's open problem."],"forward_implications":["If the main theorem stands, EF1+PO is not guaranteed for any valuation class that contains unweighted coverage valuations, so positive results for additive and matroid-rank valuations cannot be extended further in that direction.","The same example shows nonexistence for chores with unweighted coverage costs, ruling out a positive guarantee in that setting as well.","Deciding existence of EF1+PO becomes NP-hard with three agents even under monotone submodular valuations, so no efficient universal detection algorithm exists unless P=NP.","The paper records that identical monotone submodular valuations still always admit EF1+PO via leximin allocations, so the obstruction is genuinely about heterogeneous preferences.","The paper's open question about positive marginal values suggests a possible recovery: if every good adds positive value to every partial bundle, EF1+PO may exist even when coverage valuations fail."],"fun_headline_variants":["No fair and efficient allocation for submodular valuations","EF1+PO fails for submodular valuations, even coverage","Two-agent coverage instance kills EF1+PO hope","Submodular valuations: EF1+PO allocations don't exist","Deciding EF1+PO existence is NP-hard for submodular"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof asserts, without a full derivation, that the only Pareto-optimal allocations in the six-item instance are the two listed; if a Pareto-optimal allocation with utilities (6,5) or (5,6) existed, the EF1 check would be incomplete.","fun_headline_variants_meta":{"raw":{"variants":["No fair and efficient allocation for submodular valuations","EF1+PO fails for submodular valuations, even coverage","Two-agent coverage instance kills EF1+PO hope","Submodular valuations: EF1+PO allocations don't exist","Deciding EF1+PO existence is NP-hard for submodular"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000793,"raw_usage":{"total_tokens":3325,"prompt_tokens":735,"completion_tokens":2590,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":479,"completion_tokens_details":{"reasoning_tokens":2504}},"tokens_in":479,"tokens_out":2590,"duration_ms":19783,"temperature":1.0,"reasoning_tokens":2504,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T15:43:57.390096+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all 64 allocations of the six items in Table 1 and test each for EF1 and Pareto optimality under the two coverage valuations; in particular, check whether any Pareto-optimal allocation with utility pair (6,5) or (5,6) exists, since the proof does not explicitly rule those out. A single EF1+PO allocation would disprove Theorem 1.","supporting_citations":[],"review_version":1}