AFTD Auto-Formalizing Theoretical Domains

is_online_allocator

def

An allocation algorithm on m goods for n agents is online if the allocation of each arriving good t depends only on the valuation vectors of goods up to step t.

Statement

def is_online_allocator (n m : ℕ) (alg : (Fin n → Fin m → ℝ) → (Fin m → Fin n)) : Prop
Defined in
arXiv:2610.34625, Sec. 2
Verified
02 Nov 2026
Axioms
none listed
Used by 5
  • op819_has_online_single_high_alpha_monoIf a deterministic online algorithm guarantees a beta-EFX allocation for n agents and m goods under single-high valuations with ratio R >=…
  • op819_single_high_efx_one_goodFor any number of agents $n \ge 1$, $m = 1$ good, and parameter $R \ge 0$, there exists a deterministic online algorithm that achieves a…
  • 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…
  • adversary_forces_ratioGiven ratio r, factor α, and horizon H, an adversary forces factor α by prefix H on two agents if for every online allocator on H chores,…
  • is_consistent_online_allocatorA horizon-indexed family of two-agent allocation algorithms is a consistent online allocator if each alg m is an online allocator on m…

Read back from the Lean

Given natural numbers n and m, and a function alg : (Fin n → Fin m → ℝ) → (Fin m → Fin n), is_online_allocator n m alg asserts that for all valuation functions v, v' : Fin n → Fin m → ℝ and every round/item t : Fin m, if v and v' agree on all rounds up to t (that is, for all s : Fin m with s ≤ t and all agents i : Fin n, v i s = v' i s), then the allocation made by alg at round t is identical under v and v' (that is, alg v t = alg 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 on m goods for n agents is online if the allocation of each arriving good t depends only on the valuation vectors of goods up to step t. -/
def is_online_allocator (n m : ℕ) (alg : (Fin n → Fin m → ℝ) → (Fin m → Fin n)) : Prop := ∀ (v v' : Fin n → Fin m → ℝ) (t : Fin m),
    (∀ (s : Fin m), s ≤ t → ∀ i : Fin n, v i s = v' i s) → alg v t = alg v' t
See it in the graphDiscuss this resultChallenge it