op819_has_online_single_high_alpha_mono
If a deterministic online algorithm guarantees a beta-EFX allocation for n agents and m goods under single-high valuations with ratio R >= 0, then for any alpha <= beta, there exists a deterministic online algorithm guaranteeing an alpha-EFX allocation.
Statement
theorem op819_has_online_single_high_alpha_mono {n m : ℕ} {R α β : ℝ} (hR : 0 ≤ R) (hαβ : α ≤ β)
(h : has_online_single_high_alpha_efx n m R β) :
has_online_single_high_alpha_efx n m R α- Source
- arXiv:2610.34625
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- has_online_single_high_alpha_efxThere exists a deterministic online allocation algorithm for n agents and m goods that guarantees an alpha-EFX allocation for every…
- is_alpha_efx_goodsAn allocation of m indivisible goods to n agents is alpha-EFX under additive valuations u if for every pair of distinct agents i and j,…
- is_single_high_profileA valuation profile of n agents on m goods is a single-high profile with ratio R if every agent has a single-high valuation with ratio R.
- is_single_high_valuationAn agent's additive valuation vector on m goods is a single-high valuation with ratio R if there exists a good of value R such that all…
- 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.
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- is_online_allocatorAn allocation algorithm on m goods for n agents is online if the allocation of each arriving good t depends only on the valuation vectors…
Read back from the Lean
For any natural numbers $n$ and $m$, and real numbers $R, \alpha, \beta$, if $0 \le R$ and $\alpha \le \beta$, and if there exists an online allocator for $n$ agents and $m$ items that produces a $\beta$-EFX allocation for every single-high valuation profile with parameter $R$, then there exists an online allocator that produces an $\alpha$-EFX allocation for every single-high valuation profile with parameter $R$.
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
The same online algorithm that guarantees a β-EFX allocation also achieves an α-EFX allocation whenever α ≤ β. Because single-high valuations assign non-negative values (either R ≥ 0 or 1) to all items, the valuation of any bundle is non-negative. Multiplying this non-negative valuation by α ≤ β bounds the required guarantee by the known β-EFX guarantee, concluding the proof by transitivity of inequality.
The existing algorithm `alg` can serve as the witness for α-EFX solvability, reducing the theorem to checking the α-EFX inequality.
From the hypothesis that an online algorithm guarantees β-EFX allocations, extract the algorithm `alg`, its online property `halg_online`, and its guarantee `halg_efx`. Propose `alg` for the α-EFX claim. Since `alg` is already known to be online, it suffices to show that for any single-high profile v, distinct agents i and j, and good g in j's bundle, the α-EFX condition α * v_i(bundle_j \ {g}) ≤ v_i(bundle_i) holds.
rcases h with ⟨alg, halg_online, halg_efx⟩ refine ⟨alg, halg_online, fun v hv i j hij g hg => ?_⟩
Agent i's valuation of agent j's bundle without good g is non-negative.
By definition, an additive valuation is the sum over the items in the bundle. Using `Finset.sum_nonneg`, it suffices to show each item x has non-negative value under v i. Under a single-high profile, agent i values some item g0 at R and every other item at 1. In the case x = g0, the value is R, which is non-negative by assumption (hR). In the case x ≠ g0, the value is 1, which is also non-negative (closed by linear arithmetic).
uses
Finset.sum_nonneghave h_nonneg : 0 ≤ additive_valuation (v i) ((bundle_of (alg v) j).erase g) := by dsimp [additive_valuation] apply Finset.sum_nonneg intro x _ rcases hv i with ⟨g0, hg0, hrest⟩ by_cases hx : x = g0 · rw [hx, hg0]; exact hR · rw [hrest x hx]; linarith
The α-EFX inequality holds for alg.
Since α ≤ β and agent i's valuation of bundle_j \ {g} is non-negative, multiplying by this valuation preserves the inequality via `mul_le_mul_of_nonneg_right`, showing that α * v_i(bundle_j \ {g}) ≤ β * v_i(bundle_j \ {g}). Transitivity (`le_trans`) with the known β-EFX bound β * v_i(bundle_j \ {g}) ≤ v_i(bundle_i) completes the proof.
uses
le_trans,mul_le_mul_of_nonneg_rightexact le_trans (mul_le_mul_of_nonneg_right hαβ h_nonneg) (halg_efx v hv i j hij g hg)
Finset.sum_nonneg- A finite sum of non-negative elements in an ordered additive monoid is non-negative.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
mul_le_mul_of_nonneg_right- Multiplication on the right by a non-negative element preserves inequality: if b ≤ c and 0 ≤ a, then b * a ≤ c * a.
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 single-high alpha-EFX solvability in the approximation ratio alpha. -/theorem op819_has_online_single_high_alpha_mono {n m : ℕ} {R α β : ℝ} (hR : 0 ≤ R) (hαβ : α ≤ β) (h : has_online_single_high_alpha_efx n m R β) : has_online_single_high_alpha_efx n m R α := by rcases h with ⟨alg, halg_online, halg_efx⟩ refine ⟨alg, halg_online, fun v hv i j hij g hg => ?_⟩ have h_nonneg : 0 ≤ additive_valuation (v i) ((bundle_of (alg v) j).erase g) := by dsimp [additive_valuation] apply Finset.sum_nonneg intro x _ rcases hv i with ⟨g0, hg0, hrest⟩ by_cases hx : x = g0 · rw [hx, hg0]; exact hR · rw [hrest x hx]; linarith exact le_trans (mul_le_mul_of_nonneg_right hαβ h_nonneg) (halg_efx v hv i j hij g hg)