{"id":"bdb85a96-07c0-4cd0-9335-ea2001ff2e6b","arxiv_id":"2608.10397","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"EFX∨MMS allocations can fail for three agents with submodular goods (8 items) or chores (7 items), but always exist for additive mixed items with at most three valuation types when one type is a singleton.","lead":"This paper introduces an agent-wise disjunction of two fairness criteria, EFX or MMS, and shows that even this flexible notion fails for three agents with eight submodular goods or seven submodular chores, while succeeding for certain structured additive instances. It maps a new frontier in fair division where combining two fairness certificates neither guarantees fairness universally nor is empty.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorems 1 and 2 rest on exhaustive but unaudited case tables; a single missed case or erroneous table entry would invalidate both central impossibility results.","rationale":"I read the paper in good faith. The counterexample constructions are clever, and the reduction to safe-pair and safe-triple tables is a reasonable way to make computer-assisted checks human-verifiable. The structure of the proof is sound: the smallest bundle in any allocation must be a safe pair; the tables cover all completions; and the order-preserving rank transform preserves the strict comparisons needed for the EFX and MMS witnesses. I do not see an internal logical contradiction in the main theorems. The reason for conditional acceptance is precisely that the tables are large, unaudited, and load-bearing. The reader's weakest assumption identifies the same issue, and I agree. If the tables check out, the central claim should be accepted; if not, it collapses. The positive results (Theorem 4) seem to have a separate, smaller concern: Algorithm 2's pseudocode condition '∃g∈A_j s.t. v(A_i) < v(A_j∖{g})' does not explicitly require that g is a good, which is essential in mixed-item instances. The proof of Lemma 1 uses v(g) > 0 for the good case, so the intended algorithm is correct, but the pseudocode should be clarified. This issue is not as load-bearing as the tables, and it does not affect Theorems 1 and 2.","tokens_in":29012,"tokens_out":23901,"duration_ms":225346,"concrete_test":"Independently verify the case tables by enumerating all 3^8 = 6561 complete allocations for the goods instance with the valuation tables in Figure 2, computing each agent's MMS value as the max over partitions of the minimum bundle value and its EFX status under the paper's definitions, and checking that every allocation contains an agent failing both certificates. Repeat for chores with the 3^7 = 2187 allocations using the cost functions in Figure 1. This directly confirms the exhaustiveness and correctness of Table 3 and Table 6, including the 'surviving bundles' columns and the witnesses listed there. A small script can rerun the same verification, and the Z3 search file, if released, should reproduce the original rational values before scaling.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central contribution is the nonexistence of EFX∨MMS allocations in the three-agent submodular goods instance (Theorem 1) and three-agent submodular chores instance (Theorem 2). Both proofs are reduced to exhaustive human-checkable case tables: Table 3 enumerates 36 safe-pair completions for goods, and Table 6 lists all 14 allocations for the non-special triple in the chores construction. Each row claims to exhibit a concrete witness that the remaining agent is neither MMS- nor EFX-satisfied, and the authors state that the tables are exhaustive. However, the manuscript does not provide machine-checkable certificates, scripts, or the Z3 code itself; it only mentions that the code is included. The tables are easy to mis-transcribe, and a single incorrect entry in any row would invalidate the corresponding impossibility theorem. Because Theorems 1 and 2 are the surprising strengthening over prior EFX counterexamples, this is the most load-bearing point in the paper. The other main results (Theorem 4 and its corollaries) rely on separate arguments and do not inherit this risk; Algorithm 2's ambiguous condition for mixed items is an additional clarity issue but appears fixable without changing the theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines EFX∨MMS, an agent-wise disjunction requiring every agent to be either EFX-satisfied or MMS-satisfied, with the fairness certificate allowed to differ across agents. The main negative results are Theorem 1, a monotone submodular goods instance with three agents and eight goods admitting no EFX∨MMS allocation, and Theorem 2, an analogous submodular chores instance with three agents and seven chores. These are established by an SMT-guided search reduced to a human-checkable case analysis (Tables 1–3 for goods; Tables 4–6 for chores), followed by a rank-based submodularization step. The main positive result, Theorem 4, proves existence of EFX∨MMS allocations for additive mixed-item instances with at most three valuation types of multiplicities (n1,n2,1), via an MMS partition, a threshold-preserving EFX subroutine, and a cut-and-choose step. Corollaries extend this to MMS-feasible goods valuations, give approximation schemes, and show EFX∧MMS for identical additive mixed valuations. Theorem 3 shows incompatibility with fractional Pareto optimality for two agents and three items.","tokens_in":29220,"tokens_out":15454,"duration_ms":169398,"significance":"If the counterexamples are correct, Theorems 1 and 2 are significant: they show that even allowing each agent to choose between two independent fairness certificates does not restore existence in small submodular instances, substantially strengthening recent EFX nonexistence results. The positive results are also valuable: Theorem 4 gives the first structured existence guarantee for the disjunction, and the separation between EFX∨MMS and its constituents for two-type additive chores is clean and clearly explained. The paper's methodological choice—reducing an SMT search to a compact human-checkable case table—is a useful expository device, and the rank-based submodularization argument is elegant. The SMT search and the structural-barrier reduction are genuine strengths. However, the central nonexistence theorems currently rest on large tables that are not machine-auditable, and the main positive lemma has a correctness gap for mixed items; these issues must be resolved before the results can be accepted.","major_comments":[{"comment":"The impossibility proofs of Theorems 1 and 2 are reduced to exhaustive case tables (36 safe-pair cases for goods in Table 3 and fourteen allocations for chores in Table 6) that are asserted to be exhaustive and human-checkable but are not accompanied by machine-checkable certificates or by the Z3 code itself. The appendix states that the code is included, but the manuscript text does not reproduce it, and a single erroneous or omitted row would invalidate the corresponding nonexistence theorem. The AI-usage disclosure indicates that these tables were created with AI assistance and later verified by the authors; this makes an independently runnable verifier especially important. Since these tables are the load-bearing step for both central negative results, I ask that the authors provide the search code and an independently runnable verifier that checks each row's witness, or a formal proof of exhaustiveness.","section":"Section 3.1 and Appendix A.2, Tables 3 and 6"},{"comment":"Algorithm 2's first branch is triggered by the condition '∃g∈A_j s.t. v(A_i)<v(A_j\\{g})' without checking that g is a good. For additive mixed valuations this condition can hold for a chore g in A_j, since v(A_j\\{g})>v(A_j), and the algorithm would then transfer a chore from the envied bundle to the envious agent, decreasing the recipient's value and potentially violating the threshold τ. For example, let v(c1)=-1000, v(c')=-2800, v(g1)=g2=1500, A1={c1}, A2={c',g1,g2}; then v(A1)=-1000, v(A2)=200, and τ=-1000. Agent 1 is not EFX-feasible because v(A1\\{c1})=0<200, and the condition holds for c' because v(A2\\{c'})=3000>v(A1); line 4 would move c' into A1, dropping its value to -3800, below τ. Lemma 1's proof assumes the transferred item is a good only in Case 1, but the pseudocode does not enforce this. The fix is to require v(g)>0 in the 'good' branch and v(c)<0 in the 'chore' branch and to re-examine termination and threshold preservation under this corrected condition. Because Theorem 4 and Corollary 3 invoke this lemma for mixed items, this is a load-bearing correctness issue.","section":"Section 4, Algorithm 2 and Lemma 1"}],"minor_comments":[{"comment":"The sentence 'Let us now show consider the case of chores' should read 'Let us now consider the case of chores'.","section":"Section 3.3"},{"comment":"The caption refers to 'the next two displays' continuing the table, but the table is split across pages without clear continuation headings; adding a header to each continuation would improve readability and reduce the risk of transcription errors.","section":"Table 3"},{"comment":"In the definition of MMS-feasible valuations, the quantifier ranges over arbitrary subsets S and integers k, but the condition max_j v(Y_j) ≥ min_i v(X_i) implicitly assumes the partitions are ordered; a short clarifying sentence about indexing would be helpful.","section":"Section 2"},{"comment":"The EPMMS separation example would be easier to follow if the claimed pairwise-maximin-share values were derived explicitly rather than stated; the current text is correct but somewhat terse.","section":"Appendix C"}],"recommendation":"major_revision","confidential_remarks":"The paper's central negative results are plausible but currently depend on unaudited case tables; the Algorithm 2 issue is local and fixable. If the authors supply machine-checkable certificates for Tables 3 and 6 and patch the subroutine, I would be supportive. I have no concerns about novelty or citation practices; the AI-usage disclosure is transparent."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"EFX∨MMS is a natural criterion, and the paper's main news is that it still fails for 3 agents with 8 submodular goods and for 3 agents with 7 submodular chores. That strengthens recent EFX impossibilities, and the positive result for additive mixed instances with (n1,n2,1) valuation types gives a clean separation from the constituent notions. The paper earns its keep.\n\nWhat's new: the disjunction itself (with honest disclosure of concurrent IMMX/IMMP work), counterexamples that force the same agent to fail both EFX and MMS, and the (n1,n2,1) existence theorem. The techniques are sound: the threshold-preserving subroutine has a valid potential argument, the submodular rank transform is correct, and the case analyses are exhaustive in form. The identical-valuations EFX∧MMS corollary for mixed items is a nice extra. The authors' prior work is cited but not load-bearing.\n\nThe soft spot is the two impossibility theorems. They rest on large case tables (36 safe-pair cases for goods, 14 chore allocations) that are human-checkable but not machine-checked in the manuscript. The Z3 code is referenced but not reproduced, so a referee can't independently audit every row. One erroneous entry would invalidate the corresponding theorem. That's a real reproducibility gap, not a flaw in the argument, and it's fixable: provide the code and machine-checked certificates. Algorithm 2's pseudocode is also ambiguous about goods vs chores in mixed instances; minor and fixable without affecting the theorems.\n\nThis paper is for fair-division researchers, especially those working on EFX/MMS existence. It deserves a serious referee. Send it to review, and ask for the code, table certificates, and a clearer Algorithm 2.","headline":"Solid paper introducing EFX∨MMS with surprising submodular counterexamples and a clean positive theorem; the main risk is unaudited case tables that should be machine-verified.","tokens_in":29754,"tokens_out":3046,"would_cite":true,"duration_ms":30871,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that letting each agent choose either envy-freeness up to any item (EFX) or maximin share (MMS) as its personal fairness certificate does not guarantee a fair allocation: three-agent instances with eight submodular goods…","keywords":["EFX","maximin share","EFX∨MMS","submodular valuations","indivisible goods","indivisible chores","mixed items","fair division"],"falsifier":"Run the published eight-good valuation tables through a program that enumerates all 6561 allocations: if any allocation gives every agent either value 95 or an EFX-feasible bundle, Theorem 1 is false. For the chores instance, enumerate all allocations of seven chores and check each of the fourteen non-special-triple cases against Table 6; a single row with an EFX- and MMS-satisfied agent refutes Theorem 2.","tokens_in":28826,"feed_emoji":"⚖️","tokens_out":9186,"duration_ms":82091,"temperature":0.7,"pith_summary":"The paper studies the agent-wise disjunction EFX∨MMS, in which every agent must be satisfied by at least one of two fairness criteria — envy-freeness up to any item (EFX) or maximin share (MMS) — with the certificate allowed to differ across agents. It establishes a two-sided frontier: even this flexibility does not guarantee existence, since there exist three-agent instances with eight submodular goods and with seven submodular chores that admit no EFX∨MMS allocation. Under additive mixed items with at most three valuation types, one of which is a single agent, an EFX∨MMS allocation always exists. This positive result yields a separation: for additive chores with two valuation types both EFX and MMS fail individually, yet their disjunction always exists. The paper also proves that identical additive valuations admit the conjunction EFX∧MMS even for mixed items, and that EFX∨MMS can be incompatible with fractional Pareto optimality in two-agent, three-item additive instances.","feed_headline":"No EFX-or-MMS allocation exists in tiny submodular instances","feed_subtitle":"With three agents, eight goods or seven chores can force every agent to fail both EFX and MMS.","key_machinery":"For the impossibilities, the load-bearing object is a structural barrier: each agent has a private partition of the items into three bundles of common maximum value $H$, forcing the MMS value to $H$ so that any agent receiving less must be rescued by EFX. The reduction defines $\\beta_i(B)$ as the best value of $B$ after deleting one good and $\\lambda_i(S)$ as the minimum over completions of the larger of the two complementary $\\beta_i$ values, so that bundle $S$ can be part of an EFX-safe completion exactly when $v_i(S) \\geq \\lambda_i(S)$; the tables reduce all possible cases to 36 safe-pair configurations for goods and 14 allocations for chores, each exhibiting a witness failing both certificates. The order-preserving geometric transform $f(S)=1-2^{-r(S)}$ converts the monotone instances with ties into strictly monotone submodular ones while preserving the strict comparisons. For the existence results, the machinery is the threshold-preserving EFX transformation (Algorithm 2), which repairs EFX violations by single-item transfers without dropping any bundle below the initial minimum value, using the strictly decreasing potential $\\Phi=\\sum_i v(A_i)^2$ to terminate; cut-and-choose then yields the $(n_1, n_2, 1)$-type theorem.","core_discovery":"The paper's central claim is that the agent-wise disjunction EFX∨MMS is not a universal remedy but does move the existence frontier. Theorems 1 and 2 give the first nonexistence results for the disjunction: a monotone submodular goods instance with three agents and eight goods, and a monotone submodular chores instance with three agents and seven chores, in which every allocation leaves some agent failing both certificates simultaneously. The constructions work by aligning each agent's MMS threshold at a common maximum value $H$ and then blocking the “EFX rescue” through pairwise bundle comparisons. On the positive side, Theorem 4 proves that every additive $(n_1, n_2, 1)$-type mixed-item instance admits an EFX∨MMS allocation, leading to a clean separation from both constituent notions; and with identical additive valuations the stronger conjunction EFX∧MMS always exists.","pith_inferences":["The gap between eight goods and seven goods (and between seven chores and six chores) suggests the disjunction's minimal nonexistence threshold sits just above the known EFX thresholds; a search over all three-agent monotone submodular instances with seven goods would test whether the eight-item construction is tight.","The threshold-preserving EFX transformation looks like a reusable primitive: any partition can be converted to an EFX partition without lowering the minimum value, so variants of the cut-and-choose argument may extend to approximations of MMS or to other share-based guarantees for arbitrary agent counts.","The appendix's simultaneous incompatibility between epistemic EFX and EF1 for submodular chores hints that disjunctive or epistemic flexibility has its own structural obstructions; one could probe whether EFX∨EEFX or EF1∨MMS inherit the same pathologies.","If the positive theorem's singleton-agent condition is essential, then four-agent two-type additive instances are the natural next test; the paper leaves open whether EFX∨MMS survives there."],"forward_implications":["The known three-agent, eight-good submodular counterexamples to EFX cannot be repaired by allowing the affected agents to switch to an MMS certificate; the same agent fails both.","Every additive mixed-item instance whose agents fall into at most three valuation types, with one type a singleton, has an EFX∨MMS allocation, including instances mixing goods and chores.","For additive chores with two valuation types, neither EFX nor MMS is guaranteed individually, but EFX∨MMS always exists, so the disjunction is strictly more robust than either constituent.","Identical additive valuations imply the conjunction EFX∧MMS even with mixed items.","There are two-agent, three-item additive goods and chores instances where every EFX∨MMS allocation is fractionally Pareto dominated."],"supporting_citations":[{"why":"Introduces the EFX criterion and supplies the deletion convention against which the counterexamples are checked.","marker":"[Caragiannis et al., 2019]"},{"why":"Introduces the maximin share criterion that the disjunction is built from.","marker":"[Budish, 2011]"},{"why":"Provides a three-agent, eight-good submodular EFX counterexample that Theorem 1 strengthens to EFX∨MMS.","marker":"[Akrami et al., 2026b]"},{"why":"Gives a concurrent three-agent, eight-good submodular EFX counterexample against which the goods result is compared.","marker":"[Mackenzie and Suzuki, 2026]"},{"why":"Proves EFX nonexistence under superadditive costs, serving as a starting point for the chores counterexample.","marker":"[Christoforidis and Santorinaios, 2024]"},{"why":"Gives explicit submodular EFX inapproximability constructions for chores that Theorem 2 strengthens.","marker":"[Christoforidis, 2026]"},{"why":"Shows EFX can fail for additive chores with two valuation types, feeding the separation result.","marker":"[He and Tao, 2026]"},{"why":"Shows exact MMS can fail for chores, the other half of the separation result.","marker":"[Feige et al., 2021]"},{"why":"Supplies the Leximin++ EFX procedure for monotone goods used in Corollary 1.","marker":"[Plaut and Roughgarden, 2020]"},{"why":"Gives the two-agent, three-item instance used in Theorem 3's fractional Pareto optimality incompatibility.","marker":"[Freeman et al., 2019]"}],"fun_headline_variants":["EFX-or-MMS still fails with three agents and eight goods","Fairness disjunction hits a wall: tiny submodular failures","Even flexibility can't guarantee EFX∨MMS for small instances","EFX∨MMS: new impossibilities, but also new existence frontiers","Three-agent, eight-good counterexample shatters EFX-or-MMS hope"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The nonexistence theorems hinge on exhaustive case tables (36 safe-pair cases for goods and 14 chore allocations) that the manuscript presents as human-checkable but does not back with machine-readable certificates; a single missed case or miscalculated value in these tables would invalidate the corresponding theorem.","fun_headline_variants_meta":{"raw":{"variants":["EFX-or-MMS still fails with three agents and eight goods","Fairness disjunction hits a wall: tiny submodular failures","Even flexibility can't guarantee EFX∨MMS for small instances","EFX∨MMS: new impossibilities, but also new existence frontiers","Three-agent, eight-good counterexample shatters EFX-or-MMS hope"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000221,"raw_usage":{"total_tokens":1451,"prompt_tokens":950,"completion_tokens":501,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":566,"completion_tokens_details":{"reasoning_tokens":404}},"tokens_in":566,"tokens_out":501,"duration_ms":5173,"temperature":1.0,"reasoning_tokens":404,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T00:36:03.020602+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the published eight-good valuation tables through a program that enumerates all 6561 allocations: if any allocation gives every agent either value 95 or an EFX-feasible bundle, Theorem 1 is false. For the chores instance, enumerate all allocations of seven chores and check each of the fourteen non-special-triple cases against Table 6; a single row with an EFX- and MMS-satisfied agent refutes Theorem 2.","supporting_citations":[{"cited_title":"2026 , url=","cited_arxiv_id":null,"evidence_quote":"Gives a concurrent three-agent, eight-good submodular EFX counterexample against which the goods result is compared."},{"cited_title":"2024 , url=","cited_arxiv_id":null,"evidence_quote":"Proves EFX nonexistence under superadditive costs, serving as a starting point for the chores counterexample."},{"cited_title":"2026 , url=","cited_arxiv_id":null,"evidence_quote":"Gives explicit submodular EFX inapproximability constructions for chores that Theorem 2 strengthens."},{"cited_title":"2026 , url=","cited_arxiv_id":null,"evidence_quote":"Shows EFX can fail for additive chores with two valuation types, feeding the separation result."},{"cited_title":"2021 , organization=","cited_arxiv_id":null,"evidence_quote":"Shows exact MMS can fail for chores, the other half of the separation result."}],"review_version":1}