AFTD Auto-Formalizing Theoretical Domains

online_ef1_approximation_ratio

def

For n agents, the online EF1 approximation ratio is the supremum of all ratios alpha in [0, 1] for which there exists a deterministic online algorithm guaranteeing an alpha-EF1 allocation under exact frequency predictions.

Statement

noncomputable def online_ef1_approximation_ratio (n : ℕ) : ℝ
Defined in
arXiv:2610.34625 Sec. 5
Verified
27 Oct 2026
Axioms
none listed
Built on 1
  • 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…
Used by 4

Read back from the Lean

Given the number of agents n : ℕ, online_ef1_approximation_ratio n is defined as the supremum (sSup) in ℝ of the set of all α ∈ ℝ such that: 1. 0 ≤ α ≤ 1, and 2. There exists an online allocation algorithm achieving an α-EF1 (envy-free up to one good) guarantee under exact predictions. Specifically, has_online_alpha_ef1_algorithm n α asserts the existence of a function alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n) such that: - alg is an online algorithm: for all m : ℕ, prediction matrices a_hat, actual valuation profiles v and v', and item t : Fin m, if v and v' agree on all agents i and all items s ≤ t, then alg m a_hat v t = alg m a_hat v' t (the allocation of item t depends only on m, a_hat, and the valuation of items up to t). - For all m : ℕ and all valuation profiles v, a_hat : Fin n → Fin m → ℝ: - if all valuations in v are non-negative (v i g ≥ 0 for all i, g), and - a_hat is an exact prediction of v in the sense that for each agent i : Fin n, the sorted tuple of a_hat i equals the sorted tuple of v i (i.e., a_hat i is a permutation of v i), - then the allocation σ = alg m a_hat v is α-EF1 for goods: for every pair of distinct agents i ≠ j, if agent j's bundle σ⁻¹(j) is non-empty, there exists some item g in j's bundle such that α * (∑_{k ∈ σ⁻¹(j) \ {g}} v i k) ≤ ∑_{k ∈ σ⁻¹(i)} v i k.

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

/-- The supremum of approximation ratios α ∈ [0, 1] guaranteed by a deterministic online algorithm for n agents under exact frequency predictions. -/
noncomputable def online_ef1_approximation_ratio (n : ℕ) : ℝ :=
  sSup {α : ℝ | 0 ≤ α ∧ α ≤ 1 ∧ has_online_alpha_ef1_algorithm n α}
See it in the graphDiscuss this resultChallenge it