{"id":"91d47f0d-6879-4502-a582-cc7ff26ad874","arxiv_id":"2607.23367","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For two agents with strictly increasing valuations, EF1 and Pareto optimality are always compatible up to seven goods, and an eight-good submodular counterexample shows this is tight.","lead":"This paper shows that strictly positive marginal values do not guarantee fair-and-efficient allocation of indivisible goods between two agents: EF1 and Pareto optimality can fail exactly when there are eight or more goods. It also proves that any two-agent instance with at most seven goods always admits such an allocation, and it strengthens related NP-hardness results for three agents.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader accepted with high confidence, and I find no reason to disturb that. The most fragile-looking step is Lemma 4.3; I traced each case. In the q=1 case, the argument that T1⊆T2\\{x} leads to S1=S2∪{x}∈F2 disjoint from every T1\\{g} is correct because S1∩T1=∅. The lower bound |M|=p+q+r+s≥8 is tight only if all inequalities hold. The sufficiency direction is also correct. The counterexample's tables were spot-checked: EF1 splits match σ≥0 cells, and each EF1 split has a strict two-coordinate improvement. The hardness reduction's inequalities are consistent (e.g., 3L>n+1 forces c1=m,c2=0). The only external citation, balanced vertex cover, is standard and the reduction's equivalence remark is valid. The duplicated paragraph in Theorem 4.4's proof is an editorial redundancy, not a correctness defect. Therefore the ACCEPT verdict stands unchanged.","tokens_in":13131,"tokens_out":19756,"duration_ms":170344,"concrete_test":"Exhaustively enumerate all bipartitions of a 7-element set with |T_i|≥2 and all choices of S_i,T_i (up to symmetry) and confirm that F(S_1,T_1) and F(S_2,T_2) are never cross-intersecting; equivalently confirm the (p,q,r,s) necessary condition of Lemma 4.3 for every cell-count tuple summing to 7. This directly tests the step on which Theorem 4.4 collapses if wrong.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The positive half of the threshold (Theorem 4.4) rests on Lemma 4.3: with |T_i|≥2, cross-intersecting families F(S_i,T_i) force |M|≥8. I scrutinized the cell-count proof. For s≤2, choosing g,h so that T1∩T2⊆{g,h} gives disjoint (T1\\{g})∩(T2\\{h}); for p=0, two distinct goods in T1∩T2 give disjoint (S1∪{g}) and (S2∪{h}); for q=0, one such x gives disjoint (S1∪{x}) and (T2\\{x}); for q=1, the structure forces S1=S2∪{x}∈F2 to be disjoint from every T1\\{g}∈F1. The sufficiency direction checks the four set-type intersections using p≥1, q≥2, r≥2, s≥3. No gap. The subsequent threshold argument is sound: if no disjoint U1,U2 pair existed, F1,F2 would be cross-intersecting, contradicting |M|≤7; the resulting allocation above both thresholds is EF1, and Pareto-maximizing within the dominating set preserves the threshold. I also re-derived the EF1 classification and strict dominations in Section 3 from tables (1)–(2); the σ arrays in Appendix B agree with the four EF1 splits and the displayed dominating utility pairs. The hardness reduction's dependence on balanced vertex cover is a citation to [11, Lemma 1]; the paper's own remark that 'at most n/2' and 'exactly n/2' are equivalent is correct for even n. No load-bearing concern identified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies whether strictly positive marginal values guarantee the existence of EF1 and PO allocations for two agents. It proves a tight threshold: every two-agent instance with at most seven goods and strictly increasing valuations admits an EF1+PO allocation (Theorem 4.4), while an eight-good instance with normalized, integer-valued, strictly increasing, submodular valuations has every EF1 allocation strictly Pareto dominated (Theorem 3.1). It also strengthens a three-agent NP-hardness result by confining all zero marginals to eight fixed agent–good pairs involving a single agent (Theorem 5.1). The proofs are combinatorial and self-contained, with explicit tables and appendices.","tokens_in":13472,"tokens_out":23817,"duration_ms":186182,"significance":"The main result resolves an open problem of Chandramouleeswaran and Nimbhorkar and gives the exact threshold in the number of goods. This is a clean and significant contribution to the fair-division literature. The paper is unusually checkable: the counterexample provides full marginal arrays, the EF1 splits are classified by explicit σ tables, the strict Pareto dominations are displayed, and the counting lemma (Lemma 4.3) is verified by a short cell-count argument. The NP-hardness strengthening is a substantial additional contribution. I found the proofs consistent, with no load-bearing gaps.","major_comments":[],"minor_comments":[{"comment":"The paragraph beginning “It remains to impose Pareto optimality without crossing either threshold” appears twice, with two different arguments (one by Pareto maximality, one by sum maximization). Please delete one version and keep a single, coherent argument.","section":"Section 4, Theorem 4.4 proof"},{"comment":"There are spacing/formatting artifacts such as “uptoonegood” and “Paretooptimality”. These should be corrected.","section":"Abstract"},{"comment":"The phrase “coreEF1 differences” is missing a space; it should read “core EF1 differences”.","section":"Section 5, core fact (C1)"},{"comment":"In the first sentence of the PO enhancement, “we impose Pareto optimality without crossing either threshold” is slightly misleading: the subsequent argument maximizes within the set of allocations that stay above the thresholds. Consider rephrasing for clarity.","section":"Section 4, proof of Theorem 4.4"}],"recommendation":"minor_revision","confidential_remarks":"The paper is technically sound and the appendices make the claims easy to verify. The only issue is an editorial duplicate in Section 4; after a minor revision fixing that and the formatting artifacts, I would support acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Know this: the paper answers a recently posed open problem with a tight two-agent threshold. Seven goods always admit an EF1+PO allocation; eight goods can fail, even with strictly positive marginals and submodularity. The main new piece is the positive theorem, and it holds up. The proof uses a nice counting lemma: two structured set families that block disjoint bundles force at least eight goods. I checked the cell-size case analysis and the cross-intersection argument; no gap.\n\nThe eight-good counterexample is a perturbed version of the Mackenzie–Suzuki instance. That could have been a problem, but the paper re-verifies every property directly from the integer tables, so it stands on its own. The reported EF1 splits and the four strict Pareto dominations check out. I also spot-checked the marginal arrays for positivity and coordinatewise monotonicity, and the numbers are consistent. The hardness strengthening is real but modest: all zero marginals are confined to eight fixed agent–good pairs on one agent, improving the earlier reduction where those pairs grew with the input. The reduction itself is a standard balanced vertex cover construction, and the key inequalities (L = n+2, 3L > n+1) are correct.\n\nSoft spots are minor. There is a duplicated paragraph near the end of the Theorem 4.4 proof; one version is enough. The paper leaves open whether NP-hardness persists when all three agents have strictly increasing valuations, but that is stated honestly as a limitation, not a flaw. The positive existence proof is non-constructive, but that is not a deficiency for an existence theorem. The citation pattern is fine: the paper relies on recent preprints, but it re-derives the needed parts rather than blindly importing them, and balanced vertex cover is cited correctly.\n\nWho is this for: anyone working on EF1/PO compatibility or threshold phenomena in fair division. I would send it to a serious referee and expect acceptance after fixing the duplicate and a light editorial pass. I would also cite it.","headline":"A tight two-agent threshold for EF1+PO under strictly increasing valuations, with a clean combinatorial proof and a verified submodular counterexample; only minor presentation blemishes.","tokens_in":13958,"tokens_out":2642,"would_cite":true,"duration_ms":25447,"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":"For two agents with strictly increasing valuations, seven goods always admit an EF1 and Pareto-optimal allocation, while an eight-good submodular counterexample shows eight is the exact threshold.","keywords":["fair division","EF1","Pareto optimality","strictly increasing valuations","submodular valuations","indivisible goods","two-agent threshold","NP-hardness"],"falsifier":"A brute-force search over all two-agent, seven-good instances with normalized, integer-valued, strictly increasing valuations (e.g., count-based tables) looking for an instance with no EF1+PO allocation would settle the threshold; the paper's theorem predicts none exists.","tokens_in":12992,"feed_emoji":"⚖️","tokens_out":10523,"duration_ms":87971,"temperature":0.7,"pith_summary":"The paper settles an open question by showing that strictly positive marginal values do not guarantee the existence of an allocation that is both envy-free up to one good (EF1) and Pareto optimal (PO). It establishes that the exact two-agent threshold is eight goods: every instance with at most seven goods and strictly increasing valuations admits an EF1+PO allocation, regardless of submodularity, while an eight-good instance with normalized, integer-valued, strictly increasing, submodular valuations has none—every EF1 allocation there is strictly Pareto dominated. The positive proof is a combinatorial argument built around a counting lemma on cross-intersecting bundle families, and the counterexample is a perturbation of a known submodular construction. A separate result tightens the computational hardness of the three-agent problem, confining all zero marginal values to eight fixed agent-good pairs involving a single agent.","feed_headline":"Seven goods guarantee EF1+PO; eight can fail","feed_subtitle":"Positive marginal values still allow a two-agent counterexample—but only at eight goods, settling an open question.","key_machinery":"The argument runs on two instruments. First, a perturbation of a known submodular counterexample: the paper scales a known example by 12 and adds |S| to every bundle value, making every marginal strictly positive while preserving the structure of EF1 violations and Pareto improvements. The resulting instance is count-based—three A-goods and five B-goods—and its marginal arrays are all positive and nonincreasing, which certifies strict increase and submodularity. Second, the positive side uses a violation-threshold method: for each agent, identify the family of EF1-violating bundles, take the maximum value τ among them, and consider bundles of value above τ; bundles derived from a worst viola","core_discovery":"The paper's central discovery is that, for two agents with strictly increasing valuations, EF1 and PO compatibility fails exactly when the number of goods reaches eight. It constructs an eight-good, normalized, integer-valued, strictly increasing, submodular instance in which every EF1 allocation is strictly Pareto dominated, and it proves that no such incompatibility can occur with seven or fewer goods for any strictly increasing valuations. The open question of whether strictly positive marginals restore EF1+PO is therefore answered in the negative, but the threshold is tight: the construction is minimal. The paper further strengthens a known NP-hardness result to the case where all zero m","pith_inferences":["The counting-lemma technique used for up to seven goods may generalize to k-agent instances, suggesting that the minimum number of goods for incompatibility grows with the number of agents; the paper leaves this open.","The perturbation recipe—adding |S| to a known zero-marginal counterexample—could be applied to other fair-division constructions to convert them into strictly increasing instances, potentially revealing whether positive marginals ever restore compatibility in larger settings.","Because the counterexample uses only two types of goods (count-based valuations), it hints that the obstruction is a matter of count structure rather than item-specific interactions; one could test whether every two-agent, eight-good incompatibility instance can be represented in this count-based form.","The NP-hardness result with a constant-size zero-marginal core suggests a natural next question: whether hardness persists when every valuation is strictly increasing, as the paper notes."],"forward_implications":["The open problem is closed: strictly positive marginal values do not in general restore compatibility of EF1 and PO, even for two agents.","For two agents, the sharp number of goods is eight: seven or fewer always admit an EF1+PO allocation, and eight can fail.","The positive result holds without submodularity—any strictly increasing valuations over at most seven goods are covered.","The three-agent existence problem is NP-hard even when zero marginals are limited to eight fixed agent-good pairs, all involving one agent.","Because the counterexample also violates weak Pareto optimality for every EF1 allocation, the incompatibility is robust to the choice of PO variant."],"fun_headline_variants":["Two-agent EF1+PO fails at 8 goods, not 7","Strictly increasing valuations: tight EF1+PO threshold at 8 goods","EF1+PO for two agents always up to 7 goods, never at 8","Eight goods break fair division compatibility for two agents","Exact threshold: two-agent EF1+PO possible up to 7 goods"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The positive theorem rests on the counting claim that the two agents' threshold-exceeding 'add-or-delete-one-good' families cannot be pairwise intersecting on fewer than eight goods, and the hardness theorem relies on a cited NP-hardness result for balanced vertex cover; should either fail, the corresponding result collapses.","fun_headline_variants_meta":{"raw":{"variants":["Two-agent EF1+PO fails at 8 goods, not 7","Strictly increasing valuations: tight EF1+PO threshold at 8 goods","EF1+PO for two agents always up to 7 goods, never at 8","Eight goods break fair division compatibility for two agents","Exact threshold: two-agent EF1+PO possible up to 7 goods"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000236,"raw_usage":{"total_tokens":1315,"prompt_tokens":694,"completion_tokens":621,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":438,"completion_tokens_details":{"reasoning_tokens":521}},"tokens_in":438,"tokens_out":621,"duration_ms":4829,"temperature":1.0,"reasoning_tokens":521,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T23:39:04.962954+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A brute-force search over all two-agent, seven-good instances with normalized, integer-valued, strictly increasing valuations (e.g., count-based tables) looking for an instance with no EF1+PO allocation would settle the threshold; the paper's theorem predicts none exists.","supporting_citations":[],"review_version":1}