AFTD Auto-Formalizing Theoretical Domains

op561_has_online_algorithm_mono

theoremverifiedoriginal

If there exists an online algorithm guaranteeing a beta-EF1 allocation for n agents under exact frequency predictions, then for any alpha <= beta, there exists an online algorithm guaranteeing an alpha-EF1 allocation.

Statement

theorem op561_has_online_algorithm_mono (n : ℕ) {α β : ℝ} (hαβ : α ≤ β)
    (h : has_online_alpha_ef1_algorithm n β) :
    has_online_alpha_ef1_algorithm n α
Related work
arXiv:2610.34625 Sec. 2.1
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • has_online_alpha_ef1_algorithmThere exists a deterministic online algorithm for n agents that, for any number of goods m, given exact frequency predictions a_hat and…
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
  • is_exact_predictionFrequency predictions a_hat : Fin n → Fin m → ℝ are exact for valuations v : Fin n → Fin m → ℝ if for every agent i : Fin n, the sorted…
  • bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
  • is_alpha_ef1_goodsAn allocation of m indivisible goods to n agents is alpha-EF1 under additive valuations u if for every pair of distinct agents i and j…
  • is_online_algorithmFor an allocation algorithm alg taking a number of goods m : ℕ, predicted valuation profiles a_hat : Fin n → Fin m → ℝ, and true valuation…

Read back from the Lean

For any natural number $n$ and any real numbers $\alpha$ and $\beta$, if $\alpha \le \beta$ and there exists an online $\beta$-EF1 algorithm for $n$ agents with exact predictions, then there exists an online $\alpha$-EF1 algorithm for $n$ agents with exact predictions.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To show monotonicity of the approximation ratio, the proof uses the exact same online algorithm that guarantees a β-EF1 allocation. Given any instance, the algorithm provides an item whose removal satisfies the β-EF1 bound. Because all valuations are non-negative and α ≤ β, the valuation scaled by α is at most the valuation scaled by β, which immediately satisfies the α-EF1 requirement.

  1. The online algorithm witnessing the β-EF1 guarantee can serve as the candidate algorithm for α-EF1.

    We unpack the assumption `h` to obtain an online algorithm `alg`, a proof `halg` that it is online, and its guarantee `hgood` that allocations are β-EF1 under exact predictions and non-negative valuations. Unfolding the definition of `has_online_alpha_ef1_algorithm`, we witness `alg` and `halg` directly, leaving us to show that `alg` produces an α-EF1 allocation for any number of goods m, non-negative valuations v, exact prediction a_hat, and pair of distinct agents i ≠ j where j has a non-empty bundle.

    lines 5–7

      obtain ⟨alg, halg, hgood⟩ := h
      unfold has_online_alpha_ef1_algorithm
      exact ⟨alg, halg, fun m v a_hat hv hpred i j hij hne => by
  2. There exists an item g in agent j's bundle satisfying the β-EF1 bound with respect to agent i.

    Applying the guarantee `hgood` to the current parameters yields an item g in agent j's bundle such that β times agent i's valuation for j's bundle without g does not exceed agent i's valuation for their own bundle.

    line 8

        obtain ⟨g, hg, hle⟩ := hgood m v a_hat hv hpred i j hij hne
  3. The same item g satisfies the α-EF1 envy-freeness bound.

    We choose the same item g. Since α ≤ β (by `hαβ`) and agent i's valuation of j's bundle without g is non-negative (being a sum of non-negative goods by `Finset.sum_nonneg`), multiplying by the valuation preserves the inequality via `mul_le_mul_of_nonneg_right`. Chaining this with the β-EF1 bound using transitivity (`le_trans`) yields α * v_i(bundle_j \ {g}) ≤ v_i(bundle_i).

    lines 9–10

    uses le_trans, mul_le_mul_of_nonneg_right, Finset.sum_nonneg

        refine ⟨g, hg, le_trans (mul_le_mul_of_nonneg_right hαβ ?_) hle⟩
        exact Finset.sum_nonneg fun x hx => hv i x⟩
le_trans
If a ≤ b and b ≤ c, then a ≤ c (transitivity of the order).
mul_le_mul_of_nonneg_right
If b ≤ c and 0 ≤ a, then b * a ≤ c * a (multiplying an inequality by a non-negative value preserves the inequality).
Finset.sum_nonneg
If every term in a finite sum is non-negative, then the sum is non-negative.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Monotonicity of online EF1 approximation: guaranteeing ratio β implies guaranteeing any smaller ratio α ≤ β. -/theorem op561_has_online_algorithm_mono (n : ℕ) {α β : ℝ} (hαβ : α ≤ β)    (h : has_online_alpha_ef1_algorithm n β) :    has_online_alpha_ef1_algorithm n α := by  obtain ⟨alg, halg, hgood⟩ := h  unfold has_online_alpha_ef1_algorithm  exact ⟨alg, halg, fun m v a_hat hv hpred i j hij hne => by    obtain ⟨g, hg, hle⟩ := hgood m v a_hat hv hpred i j hij hne    refine ⟨g, hg, le_trans (mul_le_mul_of_nonneg_right hαβ ?_) hle⟩    exact Finset.sum_nonneg fun x hx => hv i x⟩
See it in the graphDiscuss this resultChallenge it