{"id":"8b5a464f-9dc2-4911-b900-1cf6ea83bc38","arxiv_id":"2505.22174","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For personalized two-value instances, a deterministic online algorithm maintains a tight 1/(2n-1)-maximin-share allocation at every step, and limited foresight yields EF1 every n steps.","lead":"This paper designs algorithms for fairly dividing goods that arrive one by one, when each agent only cares whether a good is \"high\" or \"low\" value for them. It gives tight worst-case fairness guarantees and shows that knowing a few future goods can give much stronger guarantees.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1 as printed never resets the active-agent flags χ_i after Phase 0, so after the first n goods every candidate set is empty and the algorithm cannot allocate any further good.","rationale":"The reader's verdict accepted the paper with moderate confidence and identified a different weakest assumption in Algorithm 3. My stress-test found a more fundamental, concrete problem in the main algorithm: Algorithm 1 as printed cannot proceed past the first n goods. This is not a matter of subtle proof difficulty; it is a missing instruction in the pseudocode that makes the central positive claim false as stated. Because the intended algorithm almost certainly includes a reset of χ_i at each phase boundary—and the surrounding proofs appear to depend on exactly that—the mathematical contribution may be salvageable with a small correction. The right verdict is therefore conditional acceptance: the pseudocode must be fixed and the proofs must be rechecked against the corrected algorithm. I do not see grounds for outright rejection, since the lower-bound arguments and the foresight-based Algorithm 3 seem internally coherent, and the χ-reset omission is localized to one line. However, as the paper currently stands, the main theorem is not supported by the stated algorithm, so an unconditional accept is premature.","tokens_in":34589,"tokens_out":22093,"duration_ms":237324,"concrete_test":"Implement Algorithm 1 exactly as written for n=2, m=4 with arbitrary 2-value valuations (e.g., α_i=10, β_i=1). After the first two goods are allocated, both agents have χ_i=1. At time t=3, the sets N^h and N^ℓ in lines 11–12 are empty, so line 21's argmin over N^ℓ is undefined; if the implementation instead skips allocation, no agent receives goods at t=3 or t=4, violating Theorem 4.1 and Corollary 4.5 at t=3. Rerun after inserting 'for i∈N: χ_i←0' at the phase transition (around lines 26–30): if the claimed 1/(2n−1)-MMS guarantee now holds, the issue is a missing reset line rather than a deeper proof error.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central positive result (Theorem 4.1, Corollary 4.5) rests on Algorithm 1, but the pseudocode is internally inconsistent. The flags χ_i are initialized to 0 (line 3), and lines 18 and 24–25 set χ_i←1 for every agent who receives a good during Phase 0. When Phase 0 ends at line 26–30, the algorithm increments phase and resets low, high, and L[i], but it never resets χ_i to 0. Consequently, at time n+1 every agent has χ_i=1, so the candidate sets N^h(g,t) and N^ℓ(g,t) defined in lines 11–12 are both empty. Line 13 falls through to line 20, and line 21 computes argmin over the empty set N^ℓ(g,t), which is undefined; even if that line is bypassed, no good is ever allocated again. This directly contradicts Theorem 4.1 parts 2 and 3 for every t>n, and hence Corollary 4.5 fails. The proofs silently assume agents become active at the start of each phase: the proof of part 3 defines an agent as active iff χ_i=0, and Claim 4.7's Case 2 reasons about active high-valued bidders. That assumption requires a phase-boundary reset of χ, which is absent from the stated algorithm.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies deterministic online fair division with personalized 2-value additive valuations. It proves impossibility results for temporal EF1 and MMS (Theorems 3.1 and 3.2), proposes Algorithm 1 as a tight 1/(2n-1)-temporal-MMS algorithm for type-1 agents (Theorem 4.1 and Corollary 4.5), and designs two foresight-augmented algorithms: Algorithm 2 for two agents with foresight 1 (Theorem 5.2) and Algorithm 3 with foresight n-1 that achieves EF2 at every step and EF1 at every n-th step (Theorem 5.4). It also provides a reduction from interval-restricted instances to 2-value instances (Theorem 6.1). The paper is technically ambitious, with detailed invariant-based proofs (Lemma 4.2) and matching arguments.","tokens_in":34883,"tokens_out":8615,"duration_ms":86994,"significance":"If the results were fully correct, the tight characterization for personalized 2-value instances would be a meaningful contribution to online fair division, and the foresight results would extend the reach of temporal fairness notions. The lower bounds are explicit adversarial streams, and the proof strategy for Algorithm 1 (the H/L priority system and Lemma 4.2) is intricate and interesting. However, the central positive result is currently invalid as printed because of a missing reset in Algorithm 1, so the claimed tight guarantee is not established; the paper is promising but requires a substantive fix.","major_comments":[{"comment":"The pseudocode never resets the active-agent flags chi_i after Phase 0. Lines 11-12 define the candidate sets as subsets of agents with chi_i=0; line 18 sets chi_j to 1 for every high-valued recipient, and lines 24-25 (intended to read chi_j<-1) do the same for every agent who receives a good during Phase 0. Since each agent receives exactly one good in Phase 0, at the end of Phase 0 every agent has chi_i=1. The phase-termination block (lines 26-30) resets phase, low, high, and L[i] but not chi_i, so for every t>n the sets N^h(g,t) and N^ell(g,t) are empty, line 21 takes the argmin over an empty set, and no further good is ever allocated. This contradicts Parts 2 and 3 of Theorem 4.1 for all t>n and invalidates Corollary 4.5. The proof of Part 3 ('an agent is active if chi_i=0') and Claim 4.7's Case 2 silently assume that agents become active at the start of each phase; this requires a phase-boundary reset such as 'for i in N do chi_i<-0', which is absent from the printed algorithm. This is a load-bearing gap, not a cosmetic issue, and it must be fixed (and the induction in Claim 4.7 re-examined under the corrected reset) before the main result can be accepted.","section":"Section 4, Algorithm 1, lines 24-30; Theorem 4.1"}],"minor_comments":[{"comment":"The assignment 'chi_i<-1' should presumably read 'chi_j<-1', since the loop index i is out of scope at that point; this typo contributes to the confusion around the active-flag handling.","section":"Section 4, Algorithm 1, line 25"},{"comment":"Corollaries 6.4 and 6.5 use 'a*' (and 'ai') where the notation 'alpha*' and 'alpha_i' is introduced in Theorem 6.1 and Definition 2.2; please harmonize the symbols.","section":"Corollaries 6.4 and 6.5"},{"comment":"The header of Section 5.2 reads 'Foresight of Length n-1Suffices' with a missing space; also Table 1 would benefit from a legend explaining the four value patterns.","section":"Section 5.2 and Table 1"},{"comment":"In the proof of Proposition 5.1, 'vi(A1)=v1(g1)=1' should be 'v1(A1)=1' to avoid an undefined index.","section":"Proposition 5.1 proof"}],"recommendation":"major_revision","confidential_remarks":"The reader's report (ACCEPT, soundness 8) appears to have overlooked the missing chi-reset in Algorithm 1; without the reset the main algorithm fails after the first n goods. The error is likely a simple omission, but because the entire positive MMS result depends on it, the paper needs a corrected pseudocode and a re-verification of the inductive claims before acceptance. I recommend major revision rather than reject, because the lower-bound and foresight parts seem solid and the fix is local."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I read the online fair division paper. The high-level content is good, but there's a concrete bug in the printed Algorithm 1 that kills the main theorem as stated.\n\nAfter Phase 0, the χ_i flags are never reset. Every agent gets exactly one good in Phase 0, so at t=n all χ_i=1. The candidate sets N^h and N^ℓ are then empty; line 21's argmin over the empty set is undefined, and no further good is allocated. The proofs of Theorem 4.1 and Claim 4.7 are written as though agents become active at the start of each phase—that's an explicit assumption in the proof of part 3 and in Claim 4.7's Case 1—but the pseudocode doesn't implement it. This looks like a missing line in the phase-transition block, something like 'χ_i←0 for all i'. It's a simple fix, but as printed the central positive result isn't proven.\n\nCredit where it's earned. The 1/(2n-1) bound for personalized 2-value instances and the matching impossibility are genuinely new and tight. The foresight-based algorithms (2 and 3) are separate and don't share the bug; their EF1/EF2 analysis, while intricate, checks out as far as I can tell. The reduction to interval-restricted instances is clean and useful.\n\nThe main proof of Lemma 4.2 is long and delicate. I didn't find gaps beyond the χ-reset issue, but the invariant on H is the sort that benefits from machine-checking or at least a careful hand re-derivation. The lower-bound constructions are explicit and fine. The citation pattern is normal—they build on prior work fairly.\n\nWho this is for: people working on online fair division, restricted valuations, temporal fairness. It deserves a serious referee: the conceptual contribution is meaningful and the flaw is likely a one-line fix. I'd recommend not desk-rejecting; send it out, but flag the Algorithm 1 pseudocode issue prominently. If the authors fix that and double-check the subsequent proofs, the result should be solid.","headline":"The paper has a real, likely fixable bug in Algorithm 1's pseudocode that invalidates the main theorem as printed, but the underlying ideas are strong and the rest of the paper is solid.","tokens_in":35359,"tokens_out":5288,"would_cite":false,"duration_ms":50515,"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 personalized two-value goods, a deterministic online algorithm keeps every agent's value at or above $1/(2n-1)$ of her maximin share at every time step, and no deterministic algorithm can beat that factor.","keywords":["online fair division","personalized 2-value instances","maximin share fairness","envy-freeness up to one good","temporal fairness","deterministic algorithm","foresight","interval-restricted valuations"],"falsifier":"Simulate Algorithm 1 on the $n=3$ instance from the proof of Theorem 3.2, with $\\alpha=2n^2+2n$ and the described arrival order; at time $3n-2$ the construction is designed to give the disadvantaged agent a maximin share of $2n-1$ while holding only the low-valued good $g_k$ of value 1, so if Algorithm 1 ever gives that agent less than $\\mu_i(t)/(2n-1)$ at any prefix, the main positive claim is refuted.","tokens_in":34448,"feed_emoji":"⚖️","tokens_out":9914,"duration_ms":86962,"temperature":0.7,"pith_summary":"Goods arrive one at a time and must be handed out before the next one appears; with unrestricted preferences, even tiny fairness guarantees are impossible. This paper shows that the landscape changes when each agent values every good either 'high' or 'low', with the threshold allowed to differ per agent. Its central result is an algorithm that, at every time step, gives each agent at least $1/(2n-1)$ of her maximin share, together with a matching impossibility theorem showing that no deterministic algorithm can guarantee anything larger. The same algorithm eventually reaches a constant $1/4$ approximation, and with only $n-1$ steps of look-ahead a much simpler matching algorithm is envy-free up to one good at every round boundary and up to two goods at all times. These guarantees extend to interval-restricted additive valuations at the cost of a $1/\\sqrt{\\alpha_i}$ factor, yielding the first nontrivial temporal fairness bounds there.","feed_headline":"Two-value goods: online fairness at a tight 1/(2n-1) ratio","feed_subtitle":"A deferred-priority algorithm matches the best any deterministic rule can do, and n-1-step foresight earns EF1 every n rounds.","key_machinery":"The load-bearing mechanism is the priority counter system of Algorithm 1: $H[i]$ and $L[i]$ count how many high- and low-valued goods agent $i$ can still afford to miss, decreased on every missed good and increased sharply (by $3n-2$ for $H$, or to $2n+t$ for $L$) after a win, which creates the 'priority levels' $H_\\ell(t)$. The invariant $|\\bigcup_{\\ell=0}^{k} H_\\ell(t)|\\le k$ for all $k$ is what guarantees no counter ever hits zero, and that invariant is what carries the $1/(2n-1)$ argument. For the foresight results, the central object is a perfect matching between agents and the next $n$ goods computed from auxiliary valuations that give a high-valued good exactly twice the weight of a low-valued good, scaled by a factor depending on the agent's position in the topological order of the envy graph; this exact 2-to-1 ratio is what makes the swap argument rule out undesirable envy edges.","core_discovery":"The paper's main positive claim is that for any personalized $2$-value instance, Algorithm 1 (Deferred-Priority) maintains a $1/(2n-1)$-MMS allocation at every time step, and Theorem 3.2 shows this is tight: no deterministic algorithm can guarantee $(1/(2n-1)+\\varepsilon)$-temporal-MMS for any constant $\\varepsilon>0$. The algorithm works by maintaining counters $H[i]$ and $L[i]$ that encode how many high- and low-valued goods each agent can still afford to lose; the invariant that at most $k$ agents have priority level at most $k$ keeps all counters positive, which translates into each agent receiving one out of every $2n-1$ goods after the first $n$, and one out of every $3n-2$ high-valued goods. The paper also establishes that with foresight of $n-1$ goods, a maximum-weight matching under carefully weighted auxiliary valuations yields EF1 at every multiple of $n$ and EF2 throughout, and that the same techniques give the first nontrivial guarantees for bounded-ratio additive instances.","pith_inferences":["The tightness in Theorem 3.2 suggests that within the personalized 2-value model, any improvement over $1/(2n-1)$ must come from weakening the requirement that fairness holds at every single time step, not from smarter deterministic allocation rules.","Algorithm 3's reliance on an exact 2-to-1 auxiliary value ratio is delicate: perturbing the weights to $2\\pm\\delta$ would likely break the envy-cancellation argument, so the design principle is tied to the two-value structure.","A natural open extension, already hinted at in the paper's discussion, is whether sublinear foresight (say $O(\\log n)$ or $O(\\sqrt n)$ steps) suffices for temporal-EF1; the matching-based proof uses the full $n$-good round, but simpler algorithms might exist.","The threshold reduction in Section 6 could be stress-tested computationally: on random interval-restricted instances, compare the achieved per-step MMS fraction with the worst-case $1/(\\sqrt{\\alpha^*}(2n-1))$ to see whether the bound is pessimistic for typical inputs."],"forward_implications":["Every deterministic algorithm, even one that knows the whole instance, cannot maintain a $(1/(2n-1)+\\varepsilon)$-MMS allocation at every step, so Algorithm 1 is per-time-step optimal for personalized 2-value instances.","Agents with identical high and low values receive a $1/(2n-1)$-MMS guarantee at every step; agents for whom all goods are equal (type 2) keep at least half their maximin share, and agents who only care about high-valued goods (type 3) keep at least a third.","With $n-1$ steps of foresight, the allocation is EF1 at every time step that is a multiple of $n$, EF2 at every time step, and satisfies $1/n$-MMS at the EF1 checkpoints.","If the allocation ever fails to be $1/2$-EF1, it recovers and stays $1/2$-EF1 from the next round boundary onward.","For any instance where each agent's values lie in $[1,\\alpha_i]$, the reduction yields a $1/(\\sqrt{\\alpha^*}(2n-1))$-temporal-MMS allocation, the first nontrivial guarantee of its kind."],"supporting_citations":[{"why":"Establishes that no deterministic algorithm can achieve temporal-EF1 for general additive goods, motivating the restricted valuation focus.","marker":"[He et al., 2019]"},{"why":"Shows no MMS approximation is possible for general additive goods beyond two agents, the impossibility barrier this paper bypasses.","marker":"[Zhou et al., 2023]"},{"why":"Introduces the online good-arrival model and gives positive results for binary instances, the direct predecessor of personalized 2-value instances.","marker":"[Aleksandrov et al., 2015]"},{"why":"Formalizes temporal fairness and gives positive results for two types of goods, a case generalized by personalized 2-value instances.","marker":"[Elkind et al., 2024]"},{"why":"Introduces k-value instances as a tractable restriction, the conceptual starting point for the 2-value analysis.","marker":"[Amanatidis et al., 2021]"},{"why":"Introduces personalized k-ary instances, i.e., per-agent values, which the paper adopts.","marker":"[Murhekar and Garg, 2021]"},{"why":"Defines envy-freeness up to k goods, the fairness notion used by Algorithms 2 and 3.","marker":"[Lipton et al., 2004]"},{"why":"Defines maximin share fairness and EF1 in the combinatorial assignment problem, the yardstick for the MMS guarantees.","marker":"[Budish, 2011]"}],"fun_headline_variants":["Two-value goods: tight 1/(2n-1) MMS online","Deterministic online fair division hits tight 1/(2n-1) MMS","Tight 1/(2n-1) MMS online, or EF1 with n-1 foresight","Online fairness for 2-value agents: tight MMS, EF1 with foresight"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantees collapse if valuations are not truly two-valued: the algorithm assumes each agent's value for every good is exactly one of two known constants $\\alpha_i$ or $\\beta_i$, so every miss or win can be recorded as high or low and the matching's ratio argument applies.","fun_headline_variants_meta":{"raw":{"variants":["Two-value goods: tight 1/(2n-1) MMS online","Deterministic online fair division hits tight 1/(2n-1) MMS","Tight 1/(2n-1) MMS online, or EF1 with n-1 foresight","Online fairness for 2-value agents: tight MMS, EF1 with foresight"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000842,"raw_usage":{"total_tokens":3765,"prompt_tokens":1141,"completion_tokens":2624,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":757,"completion_tokens_details":{"reasoning_tokens":2527}},"tokens_in":757,"tokens_out":2624,"duration_ms":16452,"temperature":1.0,"reasoning_tokens":2527,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:13:01.696404+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate Algorithm 1 on the $n=3$ instance from the proof of Theorem 3.2, with $\\alpha=2n^2+2n$ and the described arrival order; at time $3n-2$ the construction is designed to give the disadvantaged agent a maximin share of $2n-1$ while holding only the low-valued good $g_k$ of value 1, so if Algorithm 1 ever gives that agent less than $\\mu_i(t)/(2n-1)$ at any prefix, the main positive claim is refuted.","supporting_citations":[{"cited_title":"Multi-agent online scheduling: MMS allocations for indivisible items","cited_arxiv_id":null,"evidence_quote":"Shows no MMS approximation is possible for general additive goods beyond two agents, the impossibility barrier this paper bypasses."},{"cited_title":"On fair and efficient allocations of indivisible goods","cited_arxiv_id":null,"evidence_quote":"Introduces personalized k-ary instances, i.e., per-agent values, which the paper adopts."}],"review_version":1}