{"id":"e8fb3288-fc46-41cb-8fb9-4403b4ba0814","arxiv_id":"2505.24503","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"With normalization information, EF1 for two agents and PROP1 for all n are achievable; with frequency predictions, any offline share-based guarantee can be matched online.","lead":"This paper shows how much fairness an online allocation system can guarantee when it knows something about future goods. It provides algorithms that match offline guarantees when value totals or value frequencies are known, and proves limits on stronger fairness notions.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5.6's EFX impossibility proof has an uncovered branch: if agent2's extra good is g_{n+1}, the asserted bound v1(A2\\{g})≥K^2 is false and the cardinality argument does not apply, so the 0-EFX claim for n≥3 is not established as written.","rationale":"The exact-prediction transfer in Theorem 5.1 appears sound; the picking-sequence argument, Lemma 5.2, and the induction in Lemma 5.3 all check out under scrutiny. The main unaddressed weakness is not the noisy-frequency tautology (which the authors explicitly flag as future work), but an incompleteness in Theorem 5.6, which underpins the paper's claim that frequency predictions cannot yield positive EFX for n≥3. The proof's Case 2 contains a false assertion for a real subcase and then a cardinality step that does not follow from the case's premise. Because the abstract and contribution table advertise this EFX impossibility as a boundary of the frequency-prediction model, the central narrative is affected. The reader's verdict did not identify this; their weakest assumption concerns the noisy variant, which is a known open direction and does not touch the exact-prediction theorems. A conditional acceptance requiring a corrected proof of Theorem 5.6, or a weakened claim, is appropriate. The issue is purely logical completeness; no judgment about the authors is implied.","tokens_in":38238,"tokens_out":36628,"duration_ms":437956,"concrete_test":"For n=4 and the valuation table of Theorem 5.6, simulate the deterministic algorithm that outputs A1={g1}, A2={g2,g5}, A3={g3}, A4={g4} (i.e., g1→1, g2→2, g3→3, g4→4, g5→2). Check whether (i) the proof's asserted inequality v1(A2\\{g}) ≥ K^2 holds for g ∈ argmin_{g'∈A2} v1(g'); and (ii) the allocation is γ-EFX for some γ > 0. Since (i) fails (the argmin is g2 or g5, both ε-valued for agent1) and (ii) fails only via agent3's envy of agent2, this demonstrates that the proof's Case 2 does not cover its own premise. If confirmed, Theorem 5.6 needs a repaired argument before the impossibility claim can be accepted.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Theorem 5.6, Case 2, is incomplete. After g2 is allocated to agent2, the proof considers the case where at least one good from {g3,...,g_{n+1}} is allocated to agent2 and agent1 receives no good from {g4,...,g_n}, and claims v1(A2\\{g}) ≥ K^2 for g ∈ argmin_{g'∈A2} v1(g'). This is only guaranteed if A2 contains a good from {g4,...,g_n}. If the extra good is g_{n+1}, however, then v1(g_{n+1}) = ε by the valuation table, so for A2 = {g2, g_{n+1}} the minimum is ε and v1(A2\\{g}) = ε, not K^2. The subsequent cardinality step ('there are at most n−3 remaining goods and n−2 agents') also fails in this branch: for n=4, the allocation A1={g1}, A2={g2,g5}, A3={g3}, A4={g4} satisfies the case's premise, but agents 3 and 4 each receive a good and neither is empty. This allocation is not EFX, but the violation comes from agent3 envying agent2 (v3(A2\\{g2}) = K^2 > ε), a pair the proof never analyzes. Thus the proof does not cover its own premise, and the advertised hard EFX limit for n≥3 with frequency predictions is unsupported as written.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies online fair division of indivisible goods under an adaptive adversary and ex post guarantees, comparing three information models: no future information, normalization information (each agent's total value), and frequency predictions (each agent's value multiset without order). It proves that without information no deterministic online algorithm can guarantee a positive approximation of EF1, and PROP1 is impossible on sufficiently long streams. With normalization information, Algorithm 1 is shown to return EF1 allocations for two agents and PROP1 allocations for any number of agents, complemented by impossibilities for positive EFX (n≥2) and positive EF1 (n≥3), plus noisy-total robustness guarantees. With frequency predictions, a meta-algorithm (Theorem 5.1) is proposed that lifts any feasible single-shot share-based guarantee to the online setting, yielding the best-known offline MMS approximation, EFX for two agents, and an impossibility result for positive EFX when n≥3. The identical-valuations section adds an EF1 algorithm without information, a positive-EFX impossibility without information, a tight golden-ratio EFX algorithm for two agents with normalization, and a positive-EFX impossibility for n≥3 with normalization.","tokens_in":38577,"tokens_out":20798,"duration_ms":217855,"significance":"If correct, the frequency-prediction meta-algorithm is a substantial contribution: it shows that unordered multiset information is sufficient to transfer a broad class of offline share guarantees, including the current best MMS approximation, to an online setting with adversarially ordered arrivals. The normalization-information algorithm, with its explicit certificate invariant, is also a clean new result, and the identical-valuation tight bound for two agents is a nice addition. The paper is generally well organized and the main transfer proof of Theorem 5.1 is conceptually appealing. The primary concerns are the incomplete EFX impossibility proof for n≥3 with frequency predictions, which supports a headline entry in Table 1, and the fact that the noisy-frequency guarantee is expressed through an algorithm-chosen instantiation error rather than a bound in terms of prediction quality.","major_comments":[{"comment":"The proof of Case 2 contains an uncovered branch. After g2 is allocated to agent 2, the proof claims that if at least one of {g3,...,g_{n+1}} is allocated to agent 2 and agent 1 receives no good from {g4,...,g_n}, then v1(A2\\{g}) ≥ K^2 for g ∈ argmin_{g'∈A2} v1(g'). This is false when agent 2's additional good is g_{n+1}: by the valuation table v1(g_{n+1}) = ε, so with A2 = {g2, g_{n+1}} the minimum is ε and v1(A2\\{g}) = v1(g2) = K, not K^2. The subsequent cardinality step also fails in this branch: for n = 4, the allocation A1 = {g1}, A2 = {g2, g5}, A3 = {g3}, A4 = {g4} satisfies the case's premise, yet no agent is left empty; the EFX violation comes from agent 3 envying agent 2 after removing g2, a pair not analyzed by the proof. Thus Theorem 5.6, and the '✗†' entry for EFX under frequency predictions in Table 1, are not established as written. The proof needs either a complete case analysis covering this branch or a modified adversarial construction.","section":"Section 5, Theorem 5.6, Case 2"},{"comment":"The noisy-frequency guarantee is stated in terms of the algorithm's own instantiation error η_i, and the paper does not provide any instantiation rule with a worst-case bound on η_i in terms of a natural distance between predicted and true multisets, such as 1-Wasserstein distance. Consequently, the abstract's claim that guarantees 'degrade gracefully with the error parameters' under noisy frequency predictions is not yet a robustness guarantee with respect to prediction quality: if a predictor is approximately right but the instantiation rule is poorly chosen, η_i can be large and the bound becomes vacuous. The authors should either prove a bound for a concrete natural instantiation rule, or explicitly state in the main text that the advertised robustness is with respect to the end-to-end instantiation error, leaving the prediction-error dependence as an open question.","section":"Section 5.1, Theorem 5.7"}],"minor_comments":[{"comment":"The discussion of the flaw in the Kahana-Hazon example would be clearer if the proposed alternating algorithm's PROP1 guarantee were proved explicitly, since the example is used to justify relying on Theorem 3.3 for the PROP1 impossibility.","section":"Section 3, Example 3.2"},{"comment":"In the proof of Lemma 5.2, the phrase 'as only k−1 goods have been selected before this turn' is not the correct reason for the bound v_i(h_{k,v}) ≥ top_i(k); the bound holds because, for any set of k−1 removed goods, the best remaining value is at least the k-th largest value of the multiset. Please rephrase to avoid confusing the global turn count with the agent's own pick count.","section":"Section 5, Lemma 5.2"},{"comment":"In the proof of Theorem 4.3, the expression '1−2 −k3+1' is ambiguous: it should be typeset as either 1−2^{-k^3+1} or 1−2^{-(k^3+1)}. The same ambiguity appears in the valuation table in that proof.","section":"Section 4, Theorem 4.3"},{"comment":"In the proof of Theorem 6.3, expressions such as 'converges to √5−1/2' should be parenthesized as (√5−1)/2 to avoid confusion with √5 − 1/2.","section":"Section 6, Theorem 6.3"}],"recommendation":"major_revision","confidential_remarks":"The paper contains a strong and elegant main result in Theorem 5.1 and useful normalization-information algorithms, but I am more cautious than the provided reader's report because Theorem 5.6 has a genuine proof gap and is the sole support for a headline negative result in Table 1. The noisy-frequency section also needs to be either strengthened or carefully scoped. If the authors can repair Theorem 5.6 and address the instantiation-error issue, I would be willing to support acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: this is a strong paper and the central results are solid. The frequency-prediction meta-algorithm (Theorem 5.1) is a real transfer principle — it lifts any feasible single-shot share guarantee to the online setting via a picking sequence on the identically-ordered instance. That is not a trivial observation, and the proof (Lemmas 5.2 and 5.3) checks out. The normalization-information algorithm (Theorems 4.1–4.2) is also carefully argued, and the small EFX-for-two-agents result under identical valuations with tight constant (Theorem 6.3) is a nice piece of work.\n\nI was asked to stress-test Theorem 5.6, the EFX impossibility with frequency predictions for n≥3. The alleged uncovered branch does not hold up. If agent2's extra good is g_{n+1}, the bound v1(A2\\{g})≥K^2 is true because removing the minimum (the ε-valued g_{n+1}) leaves g2, which agent1 values at K^2. And the n=4 example A1={g1}, A2={g2,g5}, A3={g3}, A4={g4} falls in the first subcase, where the proof directly gets γ≤(K+2ε)/K^2; the cardinality step is only invoked after ruling that subcase out. So the proof covers its premise.\n\nThe real soft spot is the noisy-frequency guarantee, Theorem 5.7. It states the bound in terms of the algorithm's self-chosen instantiation error η_i, and there is no handle on η_i in terms of a natural prediction distance like 1-Wasserstein. The authors explicitly flag this as future work, so it is an honest limitation rather than a hidden gap. For a learning-augmented paper, that leaves the robustness claim weaker than one might hope, but it does not affect the exact-information results.\n\nThe paper is well-cited, and the two self-citations are used for auxiliary context. The impossibilities without information (Proposition 3.1, Corollary 3.4) are clean and new.\n\nWho is this for? Anyone working on online fair division, learning-augmented algorithms, or semi-online scheduling. It deserves a serious referee. I would recommend sending it to peer review and would cite it in my own work. The proof of Theorem 5.6 is dense, so a referee should check it line by line, but I do not see a flaw.","headline":"A careful, genuinely new map of what future information buys in online fair division; the main theorems hold up, including the EFX impossibility that the stress-test flagged.","tokens_in":39123,"tokens_out":12250,"would_cite":true,"duration_ms":122131,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","91B32"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that frequency predictions—the multiset of each agent's future values, without order—let online fair division match offline share-based fairness guarantees exactly, and that normalization information alone yields EF1 for…","keywords":["online fair division","frequency predictions","normalization information","envy-freeness up to one good","maximin share fairness","learning-augmented algorithms","share-based fairness"],"falsifier":"Test the noisy guarantee by fixing a predicted multiset at 1-Wasserstein distance $\\delta$ from the true multiset and applying the nearest-unused-value instantiation rule on a stream designed so that every realized value is matched to a predicted value $\\delta$ away per step; if the cumulative error $\\eta_i$ exceeds any constant times $\\delta \\cdot m$ while $s(\\hat{V}_i,n)$ stays fixed, the $(1-\\varepsilon_i)$ guarantee in Theorem 5.7 cannot be written as a function of prediction distance alone.","tokens_in":38024,"feed_emoji":"⚖️","tokens_out":7062,"duration_ms":62866,"temperature":0.7,"pith_summary":"The paper asks how much information about the future is needed to allocate indivisible goods fairly when goods arrive one by one and must be assigned irrevocably. It shows that with no information, no positive approximation to EF1 is possible and PROP1 cannot be guaranteed on long streams. With normalization information—only each agent's total value—it provides an algorithm that is EF1 for two agents and PROP1 for any number of agents, and proves matching impossibilities for stronger notions. Its main positive result is that with frequency predictions, the multiset of values each agent will see but not the order, any share-based fairness notion achievable offline becomes achievable online, matching the best-known offline approximation, including $(3/4+3/3836)$-MMS for any number of agents.","feed_headline":"Value-frequency forecasts restore offline fairness online","feed_subtitle":"A meta-algorithm lifts share-based fair division guarantees online, matching the best offline bounds.","key_machinery":"The machinery is a meta-algorithm built on picking sequences and identically-ordered (IDO) valuations. Given each agent's frequency multiset $V_i$, it sorts the values in decreasing order and attaches them to future goods in that fixed order, producing a single-shot IDO instance; any offline share-feasible allocation on that instance defines a picking sequence. Online, Algorithm 2 simulates the picking sequence on the remaining goods, allocating each arriving good to the agent who would have picked it, and the proof lemma shows each agent's realized value is at least the value she would get in the offline IDO allocation. For normalization information, Algorithm 1 instead maintains a certificate $x_i = v_i(A_i) + \\frac{n-1}{n}\\max\\{M_i, v_i(g)\\}$ that tracks whether one outside good added to the current bundle reaches $1/n$, which is what makes EF1 witnessable for two agents and PROP1 witnessable for all $n$.","core_discovery":"The central claim is Theorem 5.1: for any share-based fairness notion $s$ that is feasible in the single-shot setting, there is an online algorithm using frequency predictions that gives every agent $i$ a bundle worth at least $s(V_i,n)$. The proof is constructive: from the predicted multisets it builds an identically-ordered valuation profile, takes any offline allocation that meets the share on that profile, reads off the picking sequence that produces it, and then runs Algorithm 2 online, where each arriving good goes to the agent who would pick it in the simulated sequence. A domination lemma shows each agent's realized value is at least her value in the offline allocation, so the share guarantee transfers. This yields the best-known offline MMS ratio, EFX for two agents, and more, while impossibilities limit further progress for EFX with three or more agents.","pith_inferences":["The open instantiation-rule question in Section 5.1 is the hinge for practice: if a future result bounds $\\eta_i$ by a constant times the 1-Wasserstein distance between predicted and true multisets, then Theorem 5.7 becomes a genuine prediction-robustness guarantee rather than a certificate defined by the algorithm's own matching choices.","The paper's dichotomy suggests a general principle: for share-based fairness the order of arrivals is informationally irrelevant once the multiset is known, whereas envy-based notions like EF1 for $n\\ge 3$ may need additional structure such as identical valuations or type-specific arrivals.","Because frequency predictions can be obtained by forecasting type counts when goods fall into types, the model is directly testable in applications like ad impressions or compute slots where category-level demand forecasts are standard.","The conjectured impossibility of EF1 for $n\\ge 3$ with frequency predictions, if settled positively, would show that even perfect distributional information cannot overcome the need for order information in envy-based guarantees."],"forward_implications":["Frequency predictions turn online fair division into offline fair division for every share-based axiom: round-robin share, minimum EFX share, and the current best MMS approximation all transfer unchanged.","With normalization information alone, the paper's Algorithm 1 reaches the exact boundary: EF1 for two agents and PROP1 for all $n$ are achievable, while no positive EFX (even $n=2$) and no positive EF1 ($n\\ge 3$) can be guaranteed.","Without any information, only negative results hold: no positive EF1 approximation for $n\\ge 2$, and PROP1 is violated on sufficiently long streams.","Under noisy advice the guarantees degrade gracefully: normalization error causes additive EF1 loss for $n=2$ and a multiplicative $\\kappa$-PROP1 loss for all $n$; frequency error multiply degrades the share by $(1-\\varepsilon_i)$.","For identical valuations, EF1 is achievable with no information, and with normalization the $0.618$-EFX approximation is exactly tight for two agents, while zero-competitive EFX remains for $n\\ge 3$."],"supporting_citations":[{"why":"Supplies the normalized-valuation online MMS baseline and impossibility that frequency predictions improve upon; Algorithm 1 is a modified version of their algorithm.","marker":"[Zhou et al., 2023]"},{"why":"Provides the $(3/4+3/3836)$-MMS offline share used as the concrete instance of the frequency-prediction meta-algorithm.","marker":"[Akrami and Garg, 2024]"},{"why":"Gives the leximin++ cut-and-choose procedure that yields EFX for two agents with frequency predictions.","marker":"[Plaut and Roughgarden, 2018]"},{"why":"Supplies the lower bound used to prove that PROP1 cannot be guaranteed without future information.","marker":"[Benadè et al., 2018]"},{"why":"Defines the class of share-based fairness notions that Theorem 5.1 lifts from offline to online.","marker":"[Babaioff and Feige, 2024]"}],"fun_headline_variants":["Frequency predictions lift offline fairness guarantees online","Meta-algorithm turns predicted value multisets into online fairness","Online fair division matches offline bounds with future value hints","Robust online fair division from noisy frequency predictions","Share-based fairness achieved online via frequency forecast algorithm"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The result that frequency predictions match offline guarantees assumes the predicted multisets are exactly the true multisets and the horizon $m$ is known; with noisy predictions the advertised guarantee is expressed through the algorithm's own instantiation error, and the paper does not bound that error by a natural distance between predicted and true multisets.","fun_headline_variants_meta":{"raw":{"variants":["Frequency predictions lift offline fairness guarantees online","Meta-algorithm turns predicted value multisets into online fairness","Online fair division matches offline bounds with future value hints","Robust online fair division from noisy frequency predictions","Share-based fairness achieved online via frequency forecast algorithm"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000278,"raw_usage":{"total_tokens":1610,"prompt_tokens":859,"completion_tokens":751,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":475,"completion_tokens_details":{"reasoning_tokens":679}},"tokens_in":475,"tokens_out":751,"duration_ms":7906,"temperature":1.0,"reasoning_tokens":679,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:24:17.832481+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Test the noisy guarantee by fixing a predicted multiset at 1-Wasserstein distance $\\delta$ from the true multiset and applying the nearest-unused-value instantiation rule on a stream designed so that every realized value is matched to a predicted value $\\delta$ away per step; if the cumulative error $\\eta_i$ exceeds any constant times $\\delta \\cdot m$ while $s(\\hat{V}_i,n)$ stays fixed, the $(1-\\varepsilon_i)$ guarantee in Theorem 5.7 cannot be written as a function of prediction distance alone.","supporting_citations":[{"cited_title":"Almost envy-freeness with general valuations","cited_arxiv_id":null,"evidence_quote":"Gives the leximin++ cut-and-choose procedure that yields EFX for two agents with frequency predictions."}],"review_version":1}