{"id":"7f1ea681-8f8e-4944-a1e4-a0b6299af660","arxiv_id":"2412.00358","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For monotone restricted MMS-feasible valuations, an allocation that is simultaneously MXS and EFL always exists, and the paper gives a constructive algorithm for it.","lead":"This paper proves that, for a broad class of valuations, there is always an allocation of indivisible goods that is fair under two different rules at once: MXS (a relaxed proportionality) and EFL (a relaxed envy-freeness). The proof is an algorithm that combines fairness guarantees that were previously only known separately, settling an open question in fair division.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 8's proof that multiplicative valuations are restricted MMS-feasible is invalid; the advertised generalization to multiplicative is unproven as written.","rationale":"The reader's stated weakest assumption is the restricted MMS-feasible condition itself, but I found no internal inconsistency in how the proof uses that condition; the central termination arguments appear to rely on it exactly where stated. The reader correctly flags the multiplicative-valuation issue in Section 8, and I agree this is a real flaw, but I would sharpen it: good cancelable fails not only at zero item values but also for positive values below 1, so the proof of Corollary 8.1 is invalid more broadly. I also note that the statement of Corollary 8.1 may still be true for multiplicative valuations, so the concern is a proof gap rather than a demonstrated false theorem. This does not change the verdict: the paper should be accepted only conditional on repairing Section 8 (or narrowing the claimed scope), while the main algorithm for restricted MMS-feasible valuations is not directly impeached by this flaw.","tokens_in":37412,"tokens_out":27645,"duration_ms":236267,"concrete_test":"Run a brute-force search over small instances (m≤4) enumerating multiplicative valuations with item values in {0.01, 0.5, 2, 10}, and check (a) the good-cancelable definition on all disjoint quadruples Q,R,S,T, and (b) the restricted-MMS-feasible inequality on all pairs of partitions of every subset. If a valuation violates good cancelable but satisfies restricted MMS-feasible, Corollary 8.1's conclusion survives but its proof must be replaced; if any multiplicative valuation violates restricted MMS-feasible, the paper's claimed generalization is false and the theorem's scope must be narrowed.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 3.1 itself is conditional on the class of restricted MMS-feasible valuations, and the main termination/fairness arguments in Sections 5-6 appear internally coherent. The load-bearing weakness is in the paper's claimed scope: Corollary 8.1 asserts that multiplicative valuations are restricted MMS-feasible via good cancelability (Lemma 8.1). This proof is false even when all item values are positive. Example: v({d})=0.01, v({a})=10, v({b})=5, with Q={d}, R=∅, S={a}, T={b}. Then v(Q)=0.01 ≥ v(R)=0 and v(S)=10 > v(T)=5, but v(Q∪S)=0.1 < 5 = v(R∪T), violating good cancelable. Thus multiplicative valuations are not good cancelable, and the provided proof of Corollary 8.1 collapses. The conclusion may still be true (a geometric-mean argument gives max over any partition ≥ (v(S))^{1/k} ≥ min over any other partition), but the paper does not supply that argument. Since the abstract and Section 8 advertise restricted MMS-feasible as generalizing multiplicative valuations, the central theorem's claimed applicability to multiplicative agents is not proven as written. This is a genuine gap in the paper's central scope, even though it does not directly invalidate the algorithm's correctness for the restricted MMS-feasible class.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a new class of valuation functions, called restricted MMS-feasible valuations (Definition 2.1), and presents Algorithm MXS+EFL, which it claims always terminates and returns an allocation that is simultaneously MXS and EFL for all agents whenever valuations are monotone and restricted MMS-feasible (Theorem 3.1). The algorithm iteratively grows the number of bundles from 2 to n and uses a ReBalance procedure with two phases; termination is shown through invariants, a chain-dominance relation, and a potential-function argument. Section 7 derives corollaries for additive valuations, showing that MXS allocations are 4/7-MMS and EFL allocations are 1/2-GMMS, 1/2-EFX, and 2/3-PMMS. Section 8 claims that restricted MMS-feasible valuations include good-cancelable valuations and, in particular, additive, multiplicative, budget-additive, and unit-demand valuations.","tokens_in":37657,"tokens_out":6973,"duration_ms":64513,"significance":"If Theorem 3.1 is correct, the paper makes a substantial contribution: it provides the first simultaneous MXS+EFL guarantee and, for additive valuations, combines approximate proportionality and approximate envy-freeness into a single allocation with several derived fairness implications. The proof strategy is original and detailed, with explicitly stated invariants and no fitted parameters; the restricted-MMS-feasible condition is an explicit domain assumption rather than a restatement of the conclusion. However, the advertised scope is not fully established: the claim that multiplicative valuations fall into the new class rests on an assertion that is false as written. The central theorem for the restricted-MMS-feasible class appears internally coherent, but the manuscript as it stands overstates its applicability to multiplicative valuations. This gap is localized and likely fixable, but it is load-bearing for the paper's stated breadth.","major_comments":[{"comment":"The proof that multiplicative valuations are good cancelable is invalid. Under Definition 8.1, take item values v({a})=10, v({b})=5, v({d})=0.01 and bundles Q={d}, R=∅, S={a}, T={b}. Then Q∩S=R∩T=∅, v(Q)=0.01 ≥ v(R)=0, and v(S)=10 > v(T)=5, but v(Q∪S)=0.1 < 5 = v(R∪T). Thus multiplicative valuations are not good cancelable for the paper's definition, and Corollary 8.1's assertion that multiplicative valuations are restricted MMS-feasible is unproven as written. This affects the abstract and introduction, which advertise restricted MMS-feasible as generalizing multiplicative valuations. A direct geometric-mean argument may well prove that multiplicative valuations are restricted MMS-feasible, but that argument is not supplied in the manuscript.","section":"Section 8, Corollary 8.1"}],"minor_comments":[{"comment":"The sentence 'By Lemma 5.5, Ck(X′, f′) = SCk(X, f)' appears to be a typo; it should read 'SCk(X′, f′) = SCk(X, f)'.","section":"Section 5.1, proof of Lemma 5.6"},{"comment":"The phrase 'subsequently derived in poly-time by Chan et al.' does not give a citation year or reference number in the text; please add the appropriate citation.","section":"Section 1, Related Work"},{"comment":"Since multiplicative valuations are defined over arbitrary nonnegative item weights, the paper should state clearly whether the intended domain assumes all item values are at least 1; the current definition allows values below 1, which is what makes the good-cancelable claim fail.","section":"Section 8"}],"recommendation":"major_revision","confidential_remarks":"The main theorem for restricted MMS-feasible valuations appears to be a serious contribution, and I found no concrete error in the central termination argument. The Section 8 flaw is real and affects the paper's advertised scope, but it is localized and likely repairable by a direct proof for multiplicative valuations or by weakening the claims. I therefore recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Christina — quick take on arXiv:2412.00358 (Ashuri/Gkatzelis). The headline: this is a real result — an algorithm that simultaneously guarantees MXS and EFL for a broad class of monotone valuations, subsuming additive, budget-additive, and unit-demand. That combination was open; prior EFL work only got 1/2-MMS alongside, and this gets 4/7-MMS. The proof is intricate: envy-cycle elimination, chain dominance, a Phase-2 potential function. I cannot machine-check every deferred lemma, but the structure is coherent and the main termination argument is plausible. The authors also correctly observe that EFL implies EF1, 1/2-EFX, 1/2-GMMS, and 2/3-PMMS.\n\nThe soft spot is Section 8. Corollary 8.1 says multiplicative valuations are good cancelable, and therefore restricted MMS-feasible. That is false even with positive item values. Take v({d})=0.01, v({a})=10, v({b})=5; then Q={d}, R=∅, S={a}, T={b} satisfies v(Q)≥v(R) and v(S)>v(T), but v(Q∪S)=0.1 < 5 = v(R∪T). So multiplicative is not good cancelable, and the proof of Corollary 8.1 collapses. This matters because the abstract and intro advertise restricted MMS-feasible as generalizing multiplicative valuations. The claim itself is likely salvageable — a geometric-mean argument gives max over any partition ≥ (v(S))^{1/k} ≥ min over any other partition — but the paper does not supply it. Also, Lemma 8.1's proof has a case-split gap: it handles all Y bundles ≥ all X bundles and all Y bundles < all X bundles, but the mixed case is missing. Neither issue invalidates the main theorem for the restricted MMS-feasible class; it is a scope-proof problem, not a core-algorithm problem. But as written, the advertised applicability to multiplicative agents is unproven.\n\nVerdict: worth a serious referee. The main theorem is novel, the proof strategy is a real contribution, and the Section 8 issue is fixable. I would send it to review with a request to repair the multiplicative claim (or drop it) and to add a proof sketch for the mixed case in Lemma 8.1. My own confidence in the main theorem is moderate, not high; the proof is long and unformalized, but nothing I saw points to a load-bearing error. I would cite this if I were working on EFL/MXS combinations.","headline":"A genuinely new MXS+EFL existence result with a serious but fixable flaw in the Section 8 scope proof for multiplicative valuations.","tokens_in":38215,"tokens_out":6504,"would_cite":true,"duration_ms":55668,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that for a broad class of valuations, an allocation can always be simultaneously MXS and EFL, and gives an algorithm that finds one.","keywords":["fair division","indivisible goods","MXS","EFL","restricted MMS-feasible valuations","maximin share","envy-free up to one less-preferred good","resource allocation"],"falsifier":"A concrete falsifier is a computer search over small instances: enumerate all monotone valuations on, say, four goods that satisfy Definition 2.1, run Algorithm MXS+EFL for n = 3, and test both termination and the MXS/EFL condition on the output. Finding a single restricted-MMS-feasible instance where the algorithm loops or returns an allocation that fails MXS or EFL for some agent would refute Theorem 3.1; the paper's invariants identify Lemma 6.15 as the step most likely to break first.","tokens_in":37194,"feed_emoji":"⚖️","tokens_out":10111,"duration_ms":89514,"temperature":0.7,"pith_summary":"The paper asks whether two relaxed fairness benchmarks for indivisible goods can be met at once: MXS, an absolute benchmark based on the envy-free-up-to-any-good condition, and EFL, a relative envy-freeness notion stronger than EF1. Each was known to be achievable separately, but their simultaneous achievability was open. The paper answers this by constructing an allocation that is simultaneously MXS and EFL for every agent, and it proves the construction works for all monotone restricted-MMS-feasible valuations, a class strictly broader than additive valuations. If the argument is correct, the same allocation automatically inherits several other fairness guarantees, so one allocation covers many fairness notions at once.","feed_headline":"MXS and EFL fairness can be satisfied simultaneously","feed_subtitle":"A new constructive proof guarantees both fairness benchmarks for restricted MMS-feasible valuations, going beyond additive.","key_machinery":"The central mechanism is the two-phase ReBalance subroutine, which repairs fairness after each new empty bundle is inserted into a partition. Phase 1 moves goods along envy chains between highly demanded and under-demanded bundles, and its termination is proved by a chain-dominance invariant: each repetition strictly dominates the previous allocation in a partial order on chains of the generalized envy graph. Phase 2 uses the value of a residual bundle R for agent j as a potential function: each iteration weakly increases it, and whenever the value stays the same, the bundle X_p strictly shrinks, bounding the number of iterations by the number of goods. The valuation-generalizing inequality behind both phases is restricted MMS-feasibility: for every agent, every set S, every k, and every two partitions X_k and Z_k of S, max v(X_i) >= min v(Z_i); this inequality is what lets the proof control the effect of transferring a good between bundles in Lemmas 6.7 and 6.15.","core_discovery":"Theorem 3.1 is the central claim: for any monotone restricted-MMS-feasible valuations, the MXS+EFL algorithm terminates and returns a full allocation in which every agent's bundle is both MXS-feasible and EFL-feasible. The construction is incremental: it starts with one agent holding all goods and, for k = 2 through n, adds an empty bundle and runs the ReBalance subroutine to restore MXS+EFL before proceeding. The proof that ReBalance terminates is the technical core, and it uses two separate arguments: Phase 1 uses a chain-dominance order on envy-graph chains to rule out infinite loops, and Phase 2 uses the value of a distinguished bundle for one agent as a monotone potential. Along the way the paper introduces the restricted-MMS-feasible class and shows it contains additive, budget-additive, unit-demand, and multiplicative valuations.","pith_inferences":["The restricted-MMS-feasible condition is presented as sufficient, not necessary; if the true boundary of simultaneous MXS+EFL existence is wider, the same algorithm might run on a larger domain with only minor adjustments.","The two-phase potential-and-chain-dominance structure could be reusable for other pairs of fairness notions; the paper itself notes that EEFX+EFL cannot be handled by the same observation, so a modified invariant would be needed.","The algorithm is not claimed to be polynomial-time because FairAssociation may be implemented by exhaustive search; a natural practical extension would be to find a polynomial-time implementation for additive valuations."],"forward_implications":["For additive, budget-additive, unit-demand, and multiplicative valuations, an MXS+EFL allocation is guaranteed to exist and the algorithm finds one.","Every allocation returned is simultaneously EF1, 1/2-EFX, 1/2-GMMS, and 2/3-PMMS (from EFL) and 4/7-MMS (from MXS) for additive valuations, so a single allocation satisfies a broad menu of fairness notions.","The previously known best simultaneous guarantee of EFL with an alpha-MMS notion had alpha = 1/2; this result raises the MMS factor to 4/7.","Because the algorithm works for restricted-MMS-feasible valuations, the simultaneous existence result extends to a strictly broader class than additive valuations, answering an open problem raised when MXS was introduced."],"supporting_citations":[{"why":"Introduced EFL and proved it is achievable on its own; also supplies the lemma that EFL implies 1/2-GMMS, used in the implications section.","marker":"[Barman et al., 2018]"},{"why":"Introduced MXS and EEFX; the paper's main goal is to combine MXS with EFL, and the algorithm builds on those definitions.","marker":"[Caragiannis et al., 2023]"},{"why":"Provides the envy-cycle elimination procedure that the algorithm's EliminateCycles subroutine is based on.","marker":"[Lipton et al., 2004]"},{"why":"Shows that every EFX allocation is 4/7-MMS for additive valuations, which gives the MXS-to-4/7-MMS implication.","marker":"[Amanatidis et al., 2018]"}],"fun_headline_variants":["MXS and EFL fairness: now simultaneously satisfiable","New algorithm guarantees both MXS and EFL allocations","Simultaneous MXS and EFL for restricted MMS-feasible valuations","Both MXS and EFL fairness now guaranteed"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the restricted-MMS-feasible inequality of Definition 2.1: for any agent, any set of goods, and any two partitions of that set into the same number of bundles, the best bundle in one partition must be worth at least as much as the worst bundle in the other; if that inequality fails for some monotone valuation, the termination proofs in Phase 1 and Phase 2 no longer have their key comparison.","fun_headline_variants_meta":{"raw":{"variants":["MXS and EFL fairness: now simultaneously satisfiable","New algorithm guarantees both MXS and EFL allocations","Simultaneous MXS and EFL for restricted MMS-feasible valuations","Both MXS and EFL fairness now guaranteed"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000688,"raw_usage":{"total_tokens":3161,"prompt_tokens":1031,"completion_tokens":2130,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":647,"completion_tokens_details":{"reasoning_tokens":2065}},"tokens_in":647,"tokens_out":2130,"duration_ms":14933,"temperature":1.0,"reasoning_tokens":2065,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:28:56.001108+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete falsifier is a computer search over small instances: enumerate all monotone valuations on, say, four goods that satisfy Definition 2.1, run Algorithm MXS+EFL for n = 3, and test both termination and the MXS/EFL condition on the output. Finding a single restricted-MMS-feasible instance where the algorithm loops or returns an allocation that fails MXS or EFL for some agent would refute Theorem 3.1; the paper's invariants identify Lemma 6.15 as the step most likely to break first.","supporting_citations":[],"review_version":1}