has_online_alpha_ef1_algorithm
There exists a deterministic online algorithm for n agents that, for any number of goods m, given exact frequency predictions a_hat and arriving nonnegative additive valuations v, produces an alpha-EF1 allocation.
Statement
def has_online_alpha_ef1_algorithm (n : ℕ) (α : ℝ) : Prop
- Defined in
- arXiv:2610.34625 Sec. 2, Sec. 5
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Built on 3
- 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…
- 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…
- Used by 8
- online_ef1_approximation_ratioFor n agents, the online EF1 approximation ratio is the supremum of all ratios alpha in [0, 1] for which there exists a deterministic…
- online_ef1_approximation_ratio_le_oneFor any number of agents n, the online EF1 approximation ratio is at most 1.
- online_ef1_approximation_ratio_nonnegFor any number of agents n, the online EF1 approximation ratio under exact frequency predictions is nonnegative.
- not_has_online_alpha_ef1_four_of_gt_oneFor any alpha > 1, there is no deterministic online algorithm guaranteeing an alpha-EF1 allocation for four agents under exact frequency…
- has_online_alpha_ef1_algorithm_zeroFor any positive number of agents n, there exists a deterministic online algorithm guaranteeing a 0-EF1 allocation under exact frequency…
- online_ef1_ratio_ge_of_online_algorithmIf alpha lies in [0,1] and some deterministic online algorithm guarantees an alpha-EF1 allocation for n agents under exact frequency…
- 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…
- op561_has_online_algorithm_monoIf there exists an online algorithm guaranteeing a beta-EF1 allocation for n agents under exact frequency predictions, then for any alpha…
Read back from the Lean
Given a number of agents n : ℕ and an approximation ratio α : ℝ, has_online_alpha_ef1_algorithm n α asserts that there exists an allocation algorithm alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n) such that:
1. alg is an online algorithm: for all m : ℕ, all predicted valuation profiles a_hat, all valuation profiles v and v', and all item indices t : Fin m, if v and v' agree on all items s ≤ t (i.e., ∀ s ≤ t, ∀ i : Fin n, v i s = v' i s), then the allocation of item t is identical: alg m a_hat v t = alg m a_hat v' t.
2. For every number of items m : ℕ, every valuation profile v : Fin n → Fin m → ℝ, and every predicted valuation profile a_hat : Fin n → Fin m → ℝ:
- if all valuations are non-negative (∀ i g, 0 ≤ v i g), and
- a_hat is an exact prediction of v in the sense that for every agent i : Fin n, the sorted values of a_hat i equal the sorted values of v i (i.e., a_hat i is a permutation of v i),
- then the allocation σ = alg m a_hat v satisfies α-EF1 (envy-freeness up to one good scaled by factor α): for every pair of distinct agents i ≠ j such that j's bundle is nonempty, there exists a good g in j's bundle such that α times agent i's valuation of j's bundle with g removed is at most agent i's valuation of i's own bundle.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Existence of a deterministic online algorithm guaranteeing an α-EF1 allocation for n agents given exact frequency predictions. -/ def has_online_alpha_ef1_algorithm (n : ℕ) (α : ℝ) : Prop := ∃ (alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n)), is_online_algorithm n alg ∧ ∀ (m : ℕ) (v a_hat : Fin n → Fin m → ℝ), (∀ i g, 0 ≤ v i g) → is_exact_prediction v a_hat → is_alpha_ef1_goods v α (alg m a_hat v)