AFTD Auto-Formalizing Theoretical Domains

is_online_algorithm

def

For an allocation algorithm alg taking a number of goods m : ℕ, predicted valuation profiles a_hat : Fin n → Fin m → ℝ, and true valuation profiles v : Fin n → Fin m → ℝ to an allocation Fin m → Fin n, alg is online if for all m, a_hat, v, v', and step t : Fin m, whenever v and v' agree on all agents and all steps s ≤ t, alg m a_hat v t equals alg m a_hat v' t.

Statement

def is_online_algorithm (n : ℕ) (alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n)) : Prop
Defined in
arXiv:2610.34625 Sec. 2
Verified
27 Oct 2026
Axioms
none listed
Used by 6
  • 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…
  • op562_not_consistent_eefx_of_ge_three_halvesFor any number of agents n at least 3 and any error factor rho at least 3/2, no consistent online algorithm can guarantee any positive…
  • has_consistent_eefx_algorithmThere exists an online, consistent algorithm alg for n agents and a positive constant α > 0 such that alg guarantees α-EEFX under error…
  • 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…
  • 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 natural number n and a function alg that, for every natural number m, takes two functions of type Fin n → Fin m → ℝ (called a_hat and v) and produces a sequence of choices Fin m → Fin n, is_online_algorithm n alg asserts: For all natural numbers m, for all a_hat : Fin n → Fin m → ℝ, for all v, v' : Fin n → Fin m → ℝ, and for all t : Fin m: if for every s : Fin m with s ≤ t and every i : Fin n, v i s = v' i s, then alg m a_hat v t = alg m a_hat v' t.

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

/-- An allocation algorithm is online if the decision at step t depends only on predictions and arrivals up to step t. -/
def is_online_algorithm (n : ℕ) (alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n)) : Prop :=
  ∀ (m : ℕ) (a_hat : Fin n → Fin m → ℝ) (v v' : Fin n → Fin m → ℝ) (t : Fin m),
    (∀ (s : Fin m), s ≤ t → ∀ i : Fin n, v i s = v' i s) → alg m a_hat v t = alg m a_hat v' t
See it in the graphDiscuss this resultChallenge it