{"id":"b8aac06b-28d5-49c8-98ca-215334abca8b","arxiv_id":"2505.24321","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper claims optimal online EF1/MMS approximation ratios for submodular binary goods and personalized bi-valued goods/chores, with matching impossibility results, though proof gaps remain.","lead":"This paper studies online fair division where items arrive one by one and must be assigned immediately, for goods and chores with binary or bi-valued preferences. It claims tight approximation bounds for EF1, MMS, and welfare, but several key proofs are incomplete.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's 1/2-MMS proof contains a false set equality; the contradiction omits the m=|A_i| items already in A_i, so the central positive guarantee is not proven as written.","rationale":"The reader correctly identifies the central claim as the simultaneous 1/2-EF1, 1/2-MMS, and 1/2-max-USW guarantee for submodular binary valuations, and also flags the 1/2-MMS derivation in Theorem 2 as containing an unjustified inequality. My stress-test focuses on a more specific defect in that derivation: the union bound compares sets from the MMS partition with sets from the EF1 argument while dropping the m items already allocated to agent i. This is a genuine gap in the proof of the positive half of the central claim. I do not treat it as a refutation of the theorem because the corrected identity and the resulting contradiction appear to go through: the matroid inequality supplies |C_j| ≥ m+1, and the corrected disjoint union gives |∪C_j| = m + ∑|B_j|, which still contradicts the upper bound. I therefore partially agree with the reader: the concern is real and load-bearing as written, but it is likely repairable rather than fatal. The separate issue raised by the reader about Theorem 3's undefined e4 and absent Figure 1 is also a serious presentation gap, but the e4 construction can be filled in branch-dependently under a partition matroid, so I do not regard it as the strongest correctness objection. Since the manuscript as submitted contains this unresolved gap in a central proof, the reader's REJECT verdict is not changed by my analysis; the paper needs a corrected, fully self-contained proof before the central claim can be accepted.","tokens_in":40862,"tokens_out":40892,"duration_ms":494656,"concrete_test":"Repair the identity to |∪C_j| = m + |∪_{j≠i}B_j| with m=|A_i|. Under the contradiction assumption m < (1/2) MMS_i, use the matroid-rank bound vi(X_j) ≤ m + |C*_j| to derive |C_j| ≥ |C*_j| ≥ m+1 for every share X_j. Combining this with the EF1-derived bound ∑_{j≠i}|B_j| ≤ (n−1)(m+1) yields n(m+1) ≤ |∪C_j| = m + ∑_{j≠i}|B_j| ≤ n(m+1)−1, a contradiction. If this corrected chain is valid for every matroid rank valuation, the 1/2-MMS claim survives; if any step fails, Theorem 2's MMS guarantee is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the 1/2-MMS part of Theorem 2, after defining C_j from an MMS partition X of T, the proof asserts: \"|∪_{j∈N} C_j| = |{e : e ∈ T, A_i+e ∈ F_i}| = |∪_{j∈N} B_j| ≤ (n−1)(|A_i|+1)\". The final B_j comes from the EF1 half of the proof and only counts items allocated to agents j ≠ i that are addable to A_i. But the middle set also contains every item in A_i itself: for e ∈ A_i, A_i ∪ {e} = A_i is independent, so e is counted on the left but not in ∪_{j≠i} B_j. Thus the printed equality is off by m = |A_i|, and the contradiction as written does not follow. This is load-bearing because 1/2-MMS is one of the three guarantees in the paper's central claim for submodular binary valuations. The gap is repairable by writing |∪C_j| = m + |∪_{j≠i}B_j| and then checking the contradiction n(m+1) ≤ |∪C_j| ≤ n(m+1)−1, but the proof as published does not contain this step.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies online fair division of indivisible goods and chores under deterministic immediate allocation. It introduces non-wastefulness for goods and completeness for chores, and proves a sequence of approximation results and impossibilities for classes beyond additive binary valuations: submodular binary valuations, additive personalized bi-valued valuations, and combinations with additive binary valuations. The headline claims are a Marginal-Greedy algorithm that simultaneously guarantees NW, 1/2-EF1, 1/2-MMS, and 1/2-max-USW for submodular binary goods with all ratios tight, a two-agent Adapted Envy-Graph Procedure achieving 1/2-EF1 and 1/3-MMS for additive personalized bi-valued goods, and analogous chores-side results including 2-EF1 and 5/3-MMS for two-agent bi-valued costs.","tokens_in":41071,"tokens_out":19002,"duration_ms":199647,"significance":"If the results are correct, the paper would meaningfully extend online fair allocation beyond additive binary valuations and beyond the OXS matching model of Hosseini et al. [2024], while providing tight fairness/efficiency trade-offs. The paper also makes a useful conceptual contribution by separating goods and chores constraints (non-wastefulness vs. completeness). However, several load-bearing proofs currently contain concrete gaps: a false set equality in the 1/2-MMS proof, an underspecified lower-bound construction in Theorem 3, and inconsistent ratio calculations in Theorem 11. These issues prevent the central claims from being accepted as proven, although at least the first two appear repairable with additional matroid arguments and a completed construction.","major_comments":[{"comment":"The displayed chain |∪_{j∈N} C_j| = |{e : e ∈ T, A_i+e ∈ F_i}| = |∪_{j∈N} B_j| ≤ (n−1)(|A_i|+1) is false as written. The set {e ∈ T : A_i+e ∈ F_i} contains every e ∈ A_i, because A_i ∪ {e} = A_i is independent, while the union over B_j, as defined in the EF1 part of the proof, counts only items in the other agents' bundles that are addable to A_i. Thus the printed equality is off by |A_i|, and the contradiction n(|A_i|+1) < |∪ C_j| ≤ (n−1)(|A_i|+1) does not follow. Moreover, the equality v_i(X_j) = |A_i| + |C*_j| used to derive |C_j| > |A_i|+1 is not generally valid for matroid rank functions; only an inequality is available. A correct proof can likely be recovered by writing {e ∈ T : A_i+e ∈ F_i} as A_i ⊎ (∪_{j≠i} B_j), using |B_j| ≤ |A_i|+1 for each j, and bounding |X_j \\ C_j| ≤ |A_i| because X_j \\ C_j is an independent subset of the closure of A_i; but that argument is not what is printed. This gap is load-bearing because 1/2-MMS is one of the three guarantees in the paper's central claim for submodular binary valuations.","section":"§3.2, Theorem 2 (1/2-MMS paragraph)"},{"comment":"The lower-bound construction is underspecified. The proof refers to Figure 1 and to 'the fourth item e4' without ever defining e4's category, value, or marginal structure. In Case 1 the proof immediately writes A4_2 = {e2, e3, e4}, and in Case 2 it asserts that 'we must allocate the fourth item e4 to agent 1 due to non-wastefulness', but the item e4 has not been introduced. Consequently the asserted equalities v(A4_1) = 1/2 v(A4_2 \\ {e}) for every e ∈ A4_2 and v(A4_1) = 1/2 MMS_1 cannot be checked. Since Theorem 3 is the tightness result for all three 1/2 guarantees of the central positive claim, the omitted description of e4 is a load-bearing gap. The referenced figure is also not present in the text, so the category structure must be specified explicitly or the figure supplied.","section":"§3.2, Theorem 3 (lower bound)"},{"comment":"The EF1 lower-bound ratios are inconsistent with the claimed bound of 2. With a1 = a2 = 1 and b1 = b2 = 1/ε, the proof reports worst-case ratios 1/ε, 1 + 1/ε, (1/(2ε) + 1/2), and 2/(1+ε) in different branches. As ε → 0, the first two expressions diverge, while as ε → 1, the last two approach 1. No single choice of ε makes all displayed branches force the EF1 ratio to be at least 2−δ, so the sentence 'the lower bound of EF1 is 2' does not follow from the given instance. The proof appears to conflate upper and lower bounds on the approximation ratio. Because Theorem 11 is the tightness statement for the chore-side bi-valued results, this inconsistency is load-bearing and must be repaired.","section":"§4.3, Theorem 11 (EF1 lower bound)"}],"minor_comments":[{"comment":"The sentence 'the max-USW is 2 by allocating e1 to agent 2 and e1 to agent 1' should read 'e1 to agent 2 and e2 to agent 1'; as printed it names the same item twice.","section":"§3.2, Theorem 3 (USW paragraph)"},{"comment":"The sentence 'the number of items with a 1 cost of agent j must be at least as large as the number of items with a 1 cost of agent j' is vacuous as printed; the second occurrence should refer to agent i.","section":"§4.2.1, proof of Theorem 8"},{"comment":"The proofs rely on Figures 1, 3, and 4, which are not included in the text. Since the constructions depend on the category/color structure of the matroids, the figures must be supplied or the category memberships must be specified in text.","section":"Theorems 3 and 9"},{"comment":"The MMS partition X is introduced over the full item set T, while the proof is conducted at a fixed round k with item set T^k. The relation between T and T^k should be stated explicitly to avoid ambiguity in the definitions of C_j and B_j.","section":"§3.2, proof of Theorem 2"}],"recommendation":"major_revision","confidential_remarks":"The referee report from the reader and the stress-test note identify the same central technical gaps that I found: the false set equality in Theorem 2's 1/2-MMS proof, the missing e4 in Theorem 3, and the inconsistent EF1 ratios in Theorem 11. I agree with those specific objections. I do not recommend reject, because the 1/2-MMS proof seems repairable via a matroid closure argument and the lower-bound constructions are completable in principle. The larger risk is the two-agent bi-valued algorithms (Theorems 4 and 10), whose correctness rests on extensive handwritten case analyses in Lemmas 5, 6, 9, and 10; if those case analyses cannot be formalized with clear invariants, the positive results in those sections may not survive revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper is worth engaging, but not as-is. The headline result—tight 1/2-EF1/MMS/USW for submodular binary valuations—is a real extension beyond the OXS model of Hosseini et al., and the bi-valued two-agent bounds look new. The proof of Theorem 2 has a gap exactly where the stress test says: the equality |∪C_j| = |{e ∈ T : A_i+e ∈ F_i}| = |∪B_j| is false, because items already in A_i are counted on the left but not in ∪B_j. That is an off-by-m error, so the contradiction n(m+1) ≤ |∪C_j| ≤ (n-1)(m+1) does not follow as printed. The error looks repairable—write |∪C_j| = m + |∪_{j≠i}B_j| and the contradiction still goes through—so the theorem is probably true, but the published proof is not. The lower-bound construction in Theorem 3 also omits the fourth item e4 in the written text; the argument references a figure, and the claimed tightness of 1/2 is not established without e4. Theorem 11's EF1 lower bound has ratios that look internally inconsistent (1/(2ϵ)+1/2 vs 2/(1+ϵ) don't both give 2 as the lower bound), and Algorithm 8 contains what looks like a genuine bug: it references v_{πi} in a chores algorithm that only has cost functions. Many lemmas for the bi-valued algorithms are asserted rather than proved in the main text; the appendix cases are numerous but the proofs often rely on one-line 'easy to check' statements on which the whole EF1/MMS guarantee rests. On the credit side, the paper clearly identifies a real gap in the prior OXS-only results, the marginal-greedy technique is natural, and the 1/2-USW argument using the Lehmann et al. reduction is sound in spirit. The worst-case constructions for additive tri-valued valuations are simple and convincing, and the citation pattern looks reasonable. The issues are in the formal proofs, not in the framing. Who is this for? Someone working on online fair division will find the questions and several of the bounds useful. It deserves a serious referee, but the referee should be told to focus on Theorem 2 and the two lower-bound gaps. I would not accept it in this state; I would with a careful major revision.","headline":"Plausible and useful extension beyond OXS, but Theorem 2's 1/2-MMS proof has a load-bearing set-equality error and the lower-bound constructions are incomplete; worth a serious referee, not acceptance yet.","tokens_in":705,"tokens_out":710,"would_cite":false,"duration_ms":44276,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32","68W27"],"pacs":[],"model":"deepseek-v4-flash","headline":"For submodular binary valuations, a marginal-greedy algorithm computes allocations that are simultaneously non-wasteful, 1/2-EF1, 1/2-MMS, and 1/2-max-USW, and all three ratios are tight.","keywords":["online fair division","indivisible goods","indivisible chores","envy-freeness up to one item","maximin share fairness","submodular binary valuations","additive bi-valued valuations","online algorithms"],"falsifier":"Enumerate all two-agent partition-matroid rank functions on four items and check whether the marginal pattern claimed in the missing figure is realizable: after e1 goes to agent 1 and e2 to agent 2, there must be an e4 whose marginal value is 1 for the agent who received e3 and 0 for the other, with all earlier allocations unchanged. If no such e4 exists, the 1/2 lower bound for submodular binary valuations fails; if it exists, the tightness proof is complete.","tokens_in":40630,"feed_emoji":"⚖️","tokens_out":11225,"duration_ms":93089,"temperature":0.7,"pith_summary":"The paper asks what fairness and efficiency can be guaranteed when indivisible items arrive online and must be allocated immediately, with no knowledge of future items. Its central claim is that the frontier lies beyond additive binary valuations: for submodular binary valuations—where every item has marginal value 0 or 1 and values show diminishing returns—a simple marginal-greedy rule yields a non-wasteful allocation that is simultaneously 1/2-EF1, 1/2-MMS, and 1/2-max-USW, and all three ratios are tight. The same paper maps the achievable frontier for two-agent additive bi-valued goods and chores, giving 1/2-EF1 with 1/3-MMS for goods and 2-EF1 with 5/3-MMS for chores, each matched by impossibility results. It also shows that tri-valued additive valuations and costs make EF1 and MMS inapproximable, while additive binary chores admit exact EF1, MMS, and minimum social cost. A reader should care because these are deterministic, order-oblivious rules with worst-case guarantees that cannot be improved within their classes.","feed_headline":"One greedy rule hits 1/2-fair and 1/2-efficient online allocations","feed_subtitle":"When agents value each arriving item as either 0 or 1 with diminishing returns, the paper proves these ratios are the best possible.","key_machinery":"The load-bearing object is the identification of submodular binary valuations with matroid rank functions, together with the Marginal-Greedy Algorithm's rotating-priority allocation order. For any bundle, the valuation equals the size of a maximal independent subset of a matroid, a set system whose independent sets satisfy an exchange axiom; assigning an item only when its marginal value is 1 keeps every bundle independent, and the matroid exchange property is what bounds the envy between any two agents and drives the MMS contradiction. Non-wastefulness is maintained because any item with a positive marginal for someone is never discarded, and the welfare argument re-runs the same greedy rule with zero-marginal items assigned to agent 1, using submodularity to show the original output has half the optimal welfare.","core_discovery":"The central discovery is that submodular binary valuation functions—equivalently, matroid rank functions—admit an online algorithm with simultaneous constant-factor fairness and efficiency guarantees. The paper's Marginal-Greedy Algorithm assigns each arriving good to the first agent in a rotating order whose marginal value for it is 1, and discards only items that nobody values. Because a submodular binary valuation is the rank function of a matroid, each agent's bundle is an independent set and the matroid exchange property controls how much envy can accumulate: no agent can be forced to value another's bundle above twice her own after removing one item, and every agent receives at least half her maximin share. The paper claims the same algorithm is also a 1/2 approximation to utilitarian social welfare, via a submodularity induction, and that matching lower-bound examples show no deterministic online algorithm can beat 1/2 for EF1, MMS, or USW while maintaining non-wastefulness.","pith_inferences":["If the submodular-binary 1/2 lower bound can also be realized by coverage functions or other natural subclasses of submodular binary valuations, then the marginal-greedy rule likely marks a general frontier for diminishing-returns binary values, not just an artifact of matroid structure.","The two-agent bi-valued results derive MMS by plugging EF1 into an implication that degrades with agent count, so for more than two agents a direct MMS argument would be needed to decide whether the same 1/2 and 1/3 ratios persist.","The appendix's deadline-one results suggest a general principle: one round of waiting converts envy-cycle obstructions into matchings and yields exact EF1 for two-agent bi-valued instances, raising the testable question of whether d-period waiting does the same for n>2.","The repeated incompatibility of EF1 or MMS with any positive welfare approximation in mixed binary and bi-valued settings suggests that non-wastefulness plus exact fairness is the binding constraint; allowing randomized tie-breaking or relaxing non-wastefulness might restore simultaneous welfare guarantees."],"forward_implications":["For streams of goods with submodular binary valuations, a deterministic, future-free rule simultaneously guarantees 1/2-EF1, 1/2-MMS, and 1/2-max-USW at every round, and no non-wasteful deterministic algorithm can raise any of the three ratios to 1/2+epsilon.","Because assignment-style OXS valuations are a subclass of submodular binary valuations, the same algorithm covers online matching with class fairness and inherits the earlier 1/2 bounds while operating on a larger class.","For two-agent additive personalized bi-valued goods, the 1/2-EF1 and 1/3-MMS pair is tight, and no positive approximation to utilitarian social welfare can be added without dropping exact fairness.","For two-agent additive personalized bi-valued chores, a complete allocation satisfying 2-EF1 and 5/3-MMS is achievable, and no deterministic algorithm can guarantee 2-epsilon EF1 or 3/2-epsilon MMS.","For additive binary chores, a complete allocation satisfying EF1, MMS, and minimum utilitarian social cost exists, whereas for supermodular binary chores no nontrivial approximation is possible."],"supporting_citations":[{"why":"Supplies the online item-arrival model and the EF1 benchmark for additive binary valuations that the paper generalizes.","marker":"Aleksandrov et al. [2015]"},{"why":"Establishes 1/2-EF1 and 1/2-MMS for OXS online matching, the class that the submodular-binary result extends.","marker":"Hosseini et al. [2024]"},{"why":"Provides the submodularity lemma used in the 1/2-max-USW proof.","marker":"Lehmann et al. [2001]"},{"why":"Gives the equivalence between submodular binary functions and matroid rank functions on which the EF1 and MMS proofs rest.","marker":"Schrijver et al. [2003]"},{"why":"Supplies the alpha-EF1 to alpha/((n-1)alpha+1)-MMS implication used to convert the two-agent goods bound into 1/3-MMS.","marker":"Amanatidis et al. [2018]"},{"why":"Gives the chores analogue of the EF1-to-MMS implication used to obtain 5/3-MMS.","marker":"Sun et al. [2021]"},{"why":"Provides the matroid-complement characterization of supermodular binary costs used in the chores impossibility result.","marker":"Barman et al. [2023]"}],"fun_headline_variants":["Greedy rule achieves tight 1/2 fairness and efficiency","Online binary valuations: 1/2 is optimal for fairness","Marginal greedy: half-optimal online allocation","Binary goods: tight 1/2 bounds for EF1 and MMS"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The tightness claim for submodular binary valuations assumes that, after the third item is forced to one agent, a fourth item e4 exists with exactly the marginal values needed to make any allocation have envy and MMS ratio exactly 1/2; the paper states this case by referring to a figure and never specifies e4's item category, value, or order constraints.","fun_headline_variants_meta":{"raw":{"variants":["Greedy rule achieves tight 1/2 fairness and efficiency","Online binary valuations: 1/2 is optimal for fairness","Marginal greedy: half-optimal online allocation","Binary goods: tight 1/2 bounds for EF1 and MMS"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000208,"raw_usage":{"total_tokens":1365,"prompt_tokens":866,"completion_tokens":499,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":482,"completion_tokens_details":{"reasoning_tokens":427}},"tokens_in":482,"tokens_out":499,"duration_ms":5235,"temperature":1.0,"reasoning_tokens":427,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:26:30.466064+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all two-agent partition-matroid rank functions on four items and check whether the marginal pattern claimed in the missing figure is realizable: after e1 goes to agent 1 and e2 to agent 2, there must be an e4 whose marginal value is 1 for the agent who received e3 and 0 for the other, with all earlier allocations unchanged. If no such e4 exists, the 1/2 lower bound for submodular binary valuations fails; if it exists, the tightness proof is complete.","supporting_citations":[],"review_version":1}