has_online_alpha_ef1_algorithm_zero
For any positive number of agents n, there exists a deterministic online algorithm guaranteeing a 0-EF1 allocation under exact frequency predictions.
Statement
theorem has_online_alpha_ef1_algorithm_zero (n : ℕ) [NeZero n] :
has_online_alpha_ef1_algorithm n 0- Source
- step towards op561_exists_online_algorithm_gt_sqrt5
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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_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…
- 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_online_algorithmFor an allocation algorithm alg taking a number of goods m : ℕ, predicted valuation profiles a_hat : Fin n → Fin m → ℝ, and true valuation…
- 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…
- Used by 1
- op561_exists_of_ratio_gtIf the online EF1 approximation ratio for four agents strictly exceeds (3 - sqrt 5)/2, then there exists an achievable approximation ratio…
The proof, explained
To guarantee a 0-EF1 allocation, it suffices to use the constant algorithm that always allocates every item to agent 0. Because this algorithm is constant, its decision at each step is independent of previous valuations, satisfying the online condition trivially. For the 0-EF1 fairness guarantee, removing any item from an envied bundle scales its remaining value by α = 0, which reduces the requirement to showing that agent i's bundle has non-negative valuation—a fact that holds immediately since all goods have non-negative values.
We propose the constant algorithm assigning every good to agent 0, reducing the goal to checking that it is online and achieves 0-EF1 fairness.
We instantiate the existential quantifier in has_online_alpha_ef1_algorithm with the constant policy (fun m _ _ _ => 0), which ignores the predictions, valuations, and good index to always allocate to agent 0 (valid since n > 0). We then split the conjunction into the online property and the 0-EF1 guarantee.
use fun m _ _ _ => 0 constructor
The constant allocation algorithm is an online algorithm.
Given two valuation profiles agreeing up to step t, the algorithm outputs agent 0 in both cases regardless of the valuations, so the two allocations are definitionally equal and the condition holds by reflexivity (rfl).
· intro m a_hat v v' t ht rfl
For any distinct agents i and j where j has a nonempty bundle, choosing any good in j's bundle sets up the 0-EF1 inequality.
We introduce the valuations v, predictions a_hat, nonnegativity hypothesis h_nonneg, exact prediction hypothesis h_exact, and distinct agents i ≠ j. Given that j's bundle is nonempty, there is some good g in it; removing g leaves a goal of showing 0 * v_i(bundle(j) \ {g}) ≤ v_i(bundle(i)).
· intro m v a_hat h_nonneg h_exact i j hij h_nonempty rcases h_nonempty with ⟨g, hg⟩ refine ⟨g, hg, ?_⟩
The 0-EF1 inequality holds because 0 ≤ ∑_{x ∈ bundle(i)} v_i(x) by nonnegativity of valuations.
Multiplying by 0 makes the left-hand side 0 via zero_mul. Unfolding the definition of additive valuation expresses the right-hand side as the sum of agent i's valuations over their bundle. By Finset.sum_nonneg and the nonnegativity of all item valuations (h_nonneg), this sum is non-negative, completing the proof.
uses
zero_mul,Finset.sum_nonnegrw [zero_mul] unfold additive_valuation exact Finset.sum_nonneg (fun x _ => h_nonneg i x)
zero_mul- Multiplying by zero on the left yields zero: 0 * a = 0.
Finset.sum_nonneg- A finite sum of non-negative elements is non-negative.
- The proof does not use the prediction accuracy hypothesis h_exact, nor does it depend on which agent receives the goods: when α = 0, the EF1 guarantee trivially requires only 0 ≤ v_i(bundle(i)), which holds for any bundle under non-negative valuations.
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.
/-- For any positive number of agents n, there exists a deterministic online algorithm guaranteeing a 0-EF1 allocation under exact frequency predictions. -/theorem has_online_alpha_ef1_algorithm_zero (n : ℕ) [NeZero n] : has_online_alpha_ef1_algorithm n 0 := by use fun m _ _ _ => 0 constructor · intro m a_hat v v' t ht rfl · intro m v a_hat h_nonneg h_exact i j hij h_nonempty rcases h_nonempty with ⟨g, hg⟩ refine ⟨g, hg, ?_⟩ rw [zero_mul] unfold additive_valuation exact Finset.sum_nonneg (fun x _ => h_nonneg i x)