{"id":"aab33817-715e-4a30-a3cd-9be9ed0d4f8e","arxiv_id":"2607.17811","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"For submodular valuations, a two-agent, eight-good instance exists in which every EF1 allocation is Pareto-dominated, so EF1 and Pareto optimality are incompatible.","lead":"A two-agent example with eight goods shows that two standard goals in fair division, no one envies another after dropping one item (EF1) and no waste (Pareto optimality), cannot always be achieved together when preferences have diminishing returns. This settles an open question from Caragiannis et al. and maps how far the incompatibility extends.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Core counterexample is valid; Theorem 4.4's final leximin-optimality step has a repairable disjointness gap.","rationale":"The reader's stated weakest assumption was that the marginal grids in Appendix A.4 might contain an error, making the submodularity check fail. I recomputed all ΔA and ΔB entries for the two tables; for ε=1/6 every entry is nonnegative and every row and column is nonincreasing, so the central counterexample is fully valid. The EF1 characterization (the four balanced splits) and the domination table also verify correctly. Thus the main theorem that settles the open problem is not the weak point. The actual load-bearing concern is in the proof of Theorem 4.4, as the reader's rationale also notes: the final leximin-optimality argument forms a certificate allocation Q by replacing only P*_i with a certificate T_i from B_i, which can create overlapping bundles because T_i may contain goods from P*_j for j≠i. This invalidates the contradiction as written. The gap is easily repaired by choosing certificates from every B_k, since the B_k are disjoint, so the theorem is likely true but the submitted proof is incomplete. This leaves the paper's negative results fully established and the positive common-envelope result in need of a corrected proof, matching the reader's CONDITIONAL verdict.","tokens_in":24484,"tokens_out":20339,"duration_ms":150100,"concrete_test":"Analytical check of the final paragraph of Theorem 4.4: on a small common-envelope instance (e.g., two agents, three goods, C_i=2^M, g(S)=|S|), exhibit a complete allocation B that lexicographically dominates the constructed eA and for which the proof's single-agent replacement Q_i=T_i, Q_j=P*_j is not disjoint. Then verify that the simultaneous replacement Q_k=argmax_{T⊆B_k, T∈C_k} g(T) for every k yields a valid disjoint certificate allocation whose utility vector equals B's. This distinguishes a harmless proof repair from an actual false theorem.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3.1, the central negative result, is correct. Recomputing Appendix A.4's marginal grids for ε=1/6 confirms all entries are nonnegative with nonincreasing rows and columns, so the constructed valuations are monotone submodular. The EF1 grid and the domination table also check out, so the claimed EF1+PO incompatibility for submodular valuations and the α>23/24 quantitative strengthening are sound. The load-bearing concern is in the positive common-envelope theorem. In the proof of Theorem 4.4 (Section 4.2, final paragraph), the authors suppose a complete allocation B lexicographically dominates the constructed eA, pick one agent i with v_i(B_i)>v_i(P*_i), extract a certificate T_i⊆B_i, and form Q by replacing only P*_i with T_i while leaving all other P*_j unchanged. This Q need not be a valid certificate allocation: T_i can intersect P*_j, since P*_j is not assumed to lie inside B_j. Without disjointness, Q is not a partial allocation and cannot contradict the leximin-optimality of P*. The gap is readily repaired by taking, for every agent k, a certificate T_k⊆B_k attaining v_k(B_k); because B is a partition, these T_k are automatically disjoint, and the resulting certificate allocation has utility vector exactly (v_k(B_k)), which leximin-dominates P*. As written, however, the proof is incomplete. This gap does not affect Theorem 3.1, but it does leave the paper's positive Theorem 1.2 formally unsupported until the repair is made explicit.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses a central open problem in discrete fair division: whether an envy-free-up-to-one-good (EF1) allocation that is also Pareto optimal always exists for submodular valuations. It constructs a two-agent, eight-good instance with monotone submodular valuations, verifies by explicit tables that EF1 holds only at four balanced splits, and shows that each such split is strictly Pareto dominated, thereby establishing that EF1 and weak Pareto optimality are incompatible for submodular valuations. A quantitative version shows that, for this instance, no EF1 allocation is α-PO for any α > 23/24. The paper then proves that common-weight matroid-rank valuations can fail EF1 together with fractional Pareto optimality, which blocks weighted-welfare and Fisher-market approaches; introduces a common-envelope condition and claims an EF1+PO existence theorem under it, yielding a positive result for common-weight matroid-rank valuations; and gives subadditive constructions showing that the best universal approximate-PO threshold for two agents is at most 1/√2, matching a known lower bound, with extensions to larger numbers of agents.","tokens_in":24783,"tokens_out":17438,"duration_ms":145096,"significance":"If the proofs are completed, the paper settles a long-standing open question in a striking direction: the compatibility of EF1 and PO breaks down already for two agents with monotone submodular valuations. The core counterexample is concrete and self-contained, and the paper supplies explicit marginal grids, a complete EF1 case check, and a domination table; we independently rechecked these finite computations for the critical case ε = 1/6 and found them correct. The quantitative strengthening to α-PO for α > 23/24 is valuable because it rules out even approximate efficiency. The negative fPO results for common-weight matroid-rank valuations and for mixed manna clarify why standard market-based and weighted-welfare techniques cannot be extended in a black-box way. The common-envelope theorem, once its proof is repaired, would be a useful structural positive result. However, the proof of Theorem 4.4 as written has a genuine gap in its final leximin-optimality step, so the positive Theorem 1.2 is not yet formally supported; the gap is localized and appears to be readily repairable.","major_comments":[{"comment":"The argument that the completed allocation eA is leximin-optimal is incomplete. The proof takes an allocation B that lexicographically dominates eA, chooses one agent i with v_i(B_i) > v_i(P*_i), extracts a certificate T_i ⊆ B_i, and forms Q by replacing only P*_i with T_i while leaving all other P*_j unchanged. This Q need not be a certificate allocation, because T_i can intersect P*_j for j ≠ i; the sets P*_j are not assumed to lie inside B_j. The repair is to choose, for every agent k, a certificate T_k ⊆ B_k attaining v_k(B_k). Since B is a partition, the T_k are pairwise disjoint, and the resulting certificate allocation has utility vector exactly (v_k(B_k)), whose leximin order contradicts the leximin-optimality of P*. Until this repair is written into the proof, Theorem 1.2, via Corollary 4.5, is not formally established.","section":"Section 4.2, Theorem 4.4 proof, final paragraph"}],"minor_comments":[{"comment":"The EF1 grid in the proof is stated as the outcome of the deletion tests, but the underlying inequality comparisons are not displayed. Because the grid is a finite computation, a short appendix table of the critical comparisons, or an explicit statement that the check is exhaustive over all (x, y), would improve verifiability; our independent check of the grid for ε = 1/6 found it correct.","section":"Section 3, Theorem 3.1 proof"},{"comment":"The expressions such as '1√2' in the statements and surrounding prose appear to have a missing slash; they should read '1/√2'. This is a typesetting issue, but it occurs in a load-bearing threshold result and should be corrected.","section":"Section 5, Theorems 5.1 and 5.2"},{"comment":"The claimed n-agent NSW approximation factor of 2^{-(1-1/n)} for the modified Complete Set Growing algorithm is stated with only a one-sentence justification. Since this claim motivates Conjecture 5.3 but is not used to prove a theorem, it should either be proved in the appendix or explicitly marked as a conjecture.","section":"Section 5, paragraph after Theorem 5.2"},{"comment":"The statement defines valuations vi(S) = max{g(T) : T ⊆ S, T ∈ Ci} and then assumes each vi is submodular. It would be helpful to state explicitly that monotonicity of g and downward closure of Ci imply each vi is monotone, and to give a brief discussion of when the submodularity assumption holds beyond the provided common-weight matroid-rank example.","section":"Section 4.2, Theorem 4.4 statement"}],"recommendation":"major_revision","confidential_remarks":"The core negative theorem, Theorem 3.1, is correct and is a significant contribution. The remaining issue is the proof gap in Theorem 4.4, which is load-bearing for the paper's main positive result, Theorem 1.2. The proposed repair is straightforward and does not change the structure of the argument, so I would recommend asking the authors to fix that step and to add the small clarifications listed in the minor comments, rather than rejecting the paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline result holds. The two-agent, eight-good submodular counterexample is real, and the paper correctly claims to settle the EF1+PO compatibility question that Caragiannis et al. left open. The marginal grids in Appendix A.4 verify monotone submodularity, the EF1 split table checks out, and the domination table is clean. I also checked the epsilon scaling: for epsilon = 1/6, the 24/23 factor is right. This is a strong paper, and the main theorem alone is worth a serious referee.\n\nWhat is genuinely new: the counterexample itself; the fact that no EF1 allocation is alpha-PO for alpha > 23/24; the fPO incompatibility for common-weight matroid rank; the common-envelope positive framework; and the tight 1/sqrt(2) barrier for two-agent subadditive valuations. The authors give explicit tables and finite checks, not just existential claims. The AI disclosure is refreshing, and the citation pattern looks normal—the tightness claims rely on Barman–Suzuki [3], which is an independent published SODA paper, not fitted in this manuscript.\n\nThe soft spot is the proof of Theorem 4.4, the common-envelope positive theorem. The final step, as your stress-test note says, builds a certificate allocation Q from a single improved certificate T_i while leaving all other P*_j unchanged; T_i can intersect those P*_j, so Q may not be a partial allocation. That is a real gap. I see a second, more serious problem in the same proof, a few paragraphs earlier. In the EF1 part, after finding e' in P*_j with positive marginal for i, the paper claims v_j(P*_j\\{e'}) = g(P*_j\\{e'}) >= v_i(P*_j\\{e'}). The inequality need not hold: agent i's value for P*_j\\{e'} is the maximum over her own certificate family, which may exceed the envelope value that agent j realizes. And even if that inequality held, the comparison only shows j's new value is above i's old value; j could still be worse off than before, so the claim that the new certificate allocation lexicographically dominates P* is not established. Both of these issues are likely fixable—the fix for the disjointness gap is to take certificates for all agents from the dominating allocation B simultaneously—but as written, Theorem 1.2 and Corollary 4.5 are not formally supported.\n\nNone of this affects Theorem 3.1 or the subadditive results. The reader's conditional verdict is appropriate, though I might lower confidence in Theorem 4.4 from 'repairable gap' to 'needs real work.' Still, this is a paper to engage with, and it deserves peer review.","headline":"Main counterexample is real and settles the EF1/PO question for submodular valuations; the positive common-envelope theorem has a pair of genuine proof gaps that need repair.","tokens_in":25341,"tokens_out":4983,"would_cite":true,"duration_ms":41077,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32","05B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that with just two agents and eight goods, monotone submodular valuations can make fairness (EF1) and Pareto optimality mutually incompatible, and even approximate efficiency is impossible beyond a constant factor.","keywords":["fair division","EF1","envy-freeness up to one good","Pareto optimality","submodular valuations","subadditive valuations","weighted matroid rank","Nash social welfare"],"falsifier":"Set ε=1/6, reconstruct the two count valuations on the eight goods, and run two explicit checks: (a) compute all A- and B-marginal values and verify every entry is nonnegative with each row and column nonincreasing; (b) enumerate all 256 allocations and confirm the EF1 allocations are exactly the four balanced splits and that each is strictly Pareto-dominated by the displayed unbalanced split. Any violated inequality in (a) or any extra or missing EF1 split in (b) refutes the construction.","tokens_in":24238,"feed_emoji":"⚖️","tokens_out":9157,"duration_ms":71919,"temperature":0.7,"pith_summary":"In fair division of indivisible goods, the benchmark fairness notion of envy-freeness up to one good (EF1) is always attainable, and for additive valuations it can always be combined with Pareto optimality (PO). This paper answers the long-standing open question of whether that compatibility survives when valuations are submodular, the discrete analogue of diminishing returns. It shows the answer is no: there is a two-agent instance with only eight goods and monotone submodular valuations in which every EF1 allocation is Pareto-dominated, so no allocation is both EF1 and PO. In fact, the obstruction is quantitative: for ε=1/6, every EF1 allocation can be improved for both agents by a factor of 24/23, meaning no EF1 allocation is even α-Pareto optimal for any α>23/24. The paper goes on to map the boundary of this impossibility, showing that a market/weighted-welfare route fails even for weighted matroid rank valuations while a common-envelope condition restores EF1+PO, and proving a tight 1/√2 threshold for two-agent subadditive instances.","feed_headline":"Eight goods break fairness and efficiency together","feed_subtitle":"Under submodular tastes, every envy-free-up-to-one-goods allocation leaves both agents worse off.","key_machinery":"The driving object is a pair of type-symmetric valuation tables on 3 A-goods and 5 B-goods, with a small parameter ε. The tables are engineered so that the values rise quickly and flatten: any four goods are worth at least 3, and no bundle exceeds 3+6ε. The ε-terms are arranged with opposite symmetries in the two agents' tables, so the EF1 condition selects exactly the four balanced splits, while the same ε-terms make each balanced split strictly dominated by an unbalanced split. For the positive side, the central object is the common-envelope condition: a common monotone set function g and agent-specific downward-closed certificate families C_i, with v_i(S)=max{g(T): T⊆S, T∈C_i}; the proof selects a leximin-optimal disjoint certificate allocation and then assigns residual goods along acyclic envy graph edges, preserving EF1 and leximin optimality.","core_discovery":"The central discovery is that EF1 and Pareto optimality are not compatible for monotone submodular valuations, even with two agents and eight goods. Concretely, the paper constructs an instance with three A-goods and five B-goods, where both agents are indifferent among goods of the same type, so valuations reduce to two 4×6 tables parameterized by ε∈(0,1/6]. In any EF1 allocation, each agent must receive exactly four goods—the only four balanced splits are EF1—but each of those splits is strictly dominated by an unbalanced allocation, with both agents gaining by at least the factor (3+6ε)/(3+5ε). Setting ε=1/6 makes that factor 24/23, so for every α>23/24 no EF1 allocation is α-Pareto optimal. Because every submodular valuation is subadditive, the same construction strengthens the known subadditive incompatibility, ruling out EF1 with approximate efficiency instead of merely with exact weak-PO. The paper then proves that the obstruction is methodological: for common-weight matroid rank valuations, EF1 and fractional Pareto optimality are incompatible, so positive-welfare-weight and Fisher-market approaches cannot work in a black-box way, yet a common-envelope condition (certificates under a common monotone envelope) guarantees EF1+PO for any number of agents.","pith_inferences":["Because the domination and envy gaps in the eight-good instance are bounded away from zero by multiples of ε, the incompatibility is robust: sufficiently small perturbations of the two valuation tables should preserve the failure of EF1+α-PO for α>23/24, though the paper does not state this robustness for the submodular instance.","The same count-table mechanism—fairness enforces balance, balance is Pareto-dominated by imbalance—may translate to other fairness relaxations (e.g., EFX or maximin share) or to submodular instances with goods and chores, since only the type-symmetric structure is used.","The tight 1/√2 threshold for two-agent subadditive instances and its connection to Nash social welfare suggest that the worst-case EF1+α-PO frontier coincides with the EF1+NSW approximation frontier; testing this on random subadditive instances would be a quick computational check of the paper's conjectured n-agent threshold.","If the conjecture that all weighted matroid rank valuations admit EF1+PO is true, the common-envelope condition is not necessary for existence, and a counterexample inside weighted matroid rank would require a more expressive common scale than an additive envelope; the leximin-certificate algorithm is a natural starting point for searching such a counterexample."],"forward_implications":["For submodular valuations, the additive-result compatibility EF1+PO breaks down already with two agents, so any positive existence theorem must restrict a proper subclass of submodular or use a different fairness notion.","The same eight-good construction is a subadditive counterexample where no EF1 allocation is α-PO for α>23/24, which is stronger than the earlier subadditive incompatibility that still admitted weak-PO.","For two-agent subadditive instances, the threshold is exactly 1/√2: for every α>1/√2 there is an instance with no EF1 α-PO allocation, matching the known EF1+1/√2-PO guarantee; for n≥3 the same bound holds for every α>1/√2, and the paper conjectures the optimal n-agent threshold is 2^{-(1-1/n)}.","In common-weight matroid rank settings, EF1+fPO is impossible, so any algorithm that outputs a positive weighted-welfare maximizer (including Fisher market equilibria) cannot guarantee fairness in general, ruling out black-box transfer of the additive machinery.","Under the common-envelope condition, EF1+PO allocations exist lexicographically optimal for any number of agents, and this covers common-weight matroid rank valuations as well as shared-submodular-g valuations of the form v_i(S)=g(S∩E_i)."],"supporting_citations":[{"why":"Shows EF1 and PO are always compatible for additive valuations and poses the submodular question this paper answers negatively; also supplies the weaker subadditive incompatibility that the new instance strengthens.","marker":"[12]"},{"why":"Introduces EF1 and proves an EF1 allocation exists for arbitrary monotone valuations, making EF1 the fairness benchmark whose conflict with PO is studied here.","marker":"[27]"},{"why":"Proves every two-agent subadditive instance admits an EF1 allocation with 1/√2-approximate Nash welfare (hence 1/√2-PO), making the paper's 1/√2 threshold tight, and provides the n-agent 2^{-(1-1/n)}-PO guarantee the paper conjectures to be optimal.","marker":"[3]"},{"why":"Gives the pseudo-polynomial market-based algorithm for EF1+fPO under additive valuations, the black-box approach the fPO incompatibility rules out for common-weight matroid rank.","marker":"[5]"},{"why":"Establishes that gross-substitutes valuations form a subclass of submodular valuations, placing the constructed valuations inside the class where the impossibility is claimed.","marker":"[22, 23]"},{"why":"Shows weighted matroid rank valuations are a subclass of gross substitutes/submodular valuations, grounding both the fPO obstruction and the common-weight positive result.","marker":"[34]"}],"fun_headline_variants":["Submodular valuations: no EF1 allocation is Pareto optimal","Two agents, eight goods: fairness and efficiency incompatible","EF1 and PO can't coexist for submodular preferences","Fair division fails: EF1 and Pareto optimality incompatible"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The counterexample assumes the two 4×6 valuation tables in Section 3 are monotone submodular, a fact the paper verifies only by the finite marginal grids in Appendix A.4; if any of those grid entries is negative or increases along a row or column, the instance is not submodular and the theorem does not resolve the open question.","fun_headline_variants_meta":{"raw":{"variants":["Submodular valuations: no EF1 allocation is Pareto optimal","Two agents, eight goods: fairness and efficiency incompatible","EF1 and PO can't coexist for submodular preferences","Fair division fails: EF1 and Pareto optimality incompatible"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000227,"raw_usage":{"total_tokens":1594,"prompt_tokens":1193,"completion_tokens":401,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":809,"completion_tokens_details":{"reasoning_tokens":333}},"tokens_in":809,"tokens_out":401,"duration_ms":3941,"temperature":1.0,"reasoning_tokens":333,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:37:16.778643+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Set ε=1/6, reconstruct the two count valuations on the eight goods, and run two explicit checks: (a) compute all A- and B-marginal values and verify every entry is nonnegative with each row and column nonincreasing; (b) enumerate all 256 allocations and confirm the EF1 allocations are exactly the four balanced splits and that each is strictly Pareto-dominated by the displayed unbalanced split. Any violated inequality in (a) or any extra or missing EF1 split in (b) refutes the construction.","supporting_citations":[{"cited_title":"Combinatorial auctions with decreasing marginal utilities.Games and Economic Behavior, 55(2):270–296, 2006","cited_arxiv_id":null,"evidence_quote":"Introduces EF1 and proves an EF1 allocation exists for arbitrary monotone valuations, making EF1 the fairness benchmark whose conflict with PO is studied here."},{"cited_title":"Springer, 2003","cited_arxiv_id":null,"evidence_quote":"Shows weighted matroid rank valuations are a subclass of gross substitutes/submodular valuations, grounding both the fPO obstruction and the common-weight positive result."}],"review_version":2}