op561_has_online_algorithm_mono
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.
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.
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
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.
obtain ⟨g, hg, hle⟩ := hgood m v a_hat hv hpred i j hij hneThe 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).
uses
le_trans,mul_le_mul_of_nonneg_right,Finset.sum_nonnegrefine ⟨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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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⟩