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