is_consistent_online_allocator
A horizon-indexed family of two-agent allocation algorithms is a consistent online allocator if each alg m is an online allocator on m chores and the allocation of chore t on a prefix depends only on the costs up to t and is consistent across all horizons.
Statement
def is_consistent_online_allocator (alg : (m : ℕ) → (Fin 2 → Fin m → ℝ) → Fin m → Fin 2) : Prop
- Related work
- arXiv:2505.24321
- Verified
- 12 Nov 2026
- Axioms
- none listed
- Built on 1
- is_online_allocatorAn allocation algorithm on m goods for n agents is online if the allocation of each arriving good t depends only on the valuation vectors…
- Used by 1
- has_consistent_online_alpha_mmsGiven ratio r and approximation factor α, there exists a consistent online allocator for two agents that, whenever each agent's cost for…
Read back from the Lean
A family of allocation algorithms alg (indexed by horizon $m : ℕ$, taking an input $c : \text{Fin } 2 \to \text{Fin } m \to ℝ$ and returning an allocation $\text{Fin } m \to \text{Fin } 2$) satisfies is_consistent_online_allocator if and only if:
1. For every natural number $m$, alg m is an online allocator: for any two input profiles $v, v' : \text{Fin } 2 \to \text{Fin } m \to ℝ$ and any time step $t : \text{Fin } m$, if $v(i, s) = v'(i, s)$ for all $s \le t$ and all $i : \text{Fin } 2$, then alg m v t = alg m v' t.
2. For all natural numbers $m_1, m_2$ with $m_1 \le m_2$, every input profile $c : \text{Fin } 2 \to \text{Fin } m_2 \to ℝ$, and every time step $t : \text{Fin } m_1$, the decision made by alg m₁ at step $t$ on the restriction of $c$ to the first $m_1$ steps is equal to the decision made by alg m₂ on $c$ at the corresponding step $t$ (embedded into $\text{Fin } m_2$).
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
/-- A family of allocators across horizons m is a consistent online allocator if each alg m is online and decisions on initial prefixes agree across horizons. -/ def is_consistent_online_allocator (alg : (m : ℕ) → (Fin 2 → Fin m → ℝ) → Fin m → Fin 2) : Prop := (∀ m, is_online_allocator 2 m (alg m)) ∧ ∀ (m₁ m₂ : ℕ) (h : m₁ ≤ m₂) (c : Fin 2 → Fin m₂ → ℝ) (t : Fin m₁), alg m₁ (fun i s => c i ⟨s.val, lt_of_lt_of_le s.isLt h⟩) t = alg m₂ c ⟨t.val, lt_of_lt_of_le t.isLt h⟩