is_consistent_algorithm
An online algorithm alg for n agents is consistent if for every m : ℕ and all nonnegative valuations v and predictions a_hat with exact predictions, the allocation alg m a_hat v is 1-EEFX.
Statement
def is_consistent_algorithm (n : ℕ) (alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n)) : Prop
- Defined in
- arXiv:2610.34625 Sec. 6
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Built on 3
- is_exact_predictionFrequency predictions a_hat : Fin n → Fin m → ℝ are exact for valuations v : Fin n → Fin m → ℝ if for every agent i : Fin n, the sorted…
- is_alpha_eefx_allocationAn allocation is alpha-EEFX if each agent's bundle is alpha-EEFX for that agent.
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- Used by 2
- 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…
Read back from the Lean
is_consistent_algorithm n alg asserts that for a fixed number of agents n : ℕ and an algorithm alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n):
For every number of goods m : ℕ, and for all valuation profiles v : Fin n → Fin m → ℝ (true valuations) and a_hat : Fin n → Fin m → ℝ (predicted valuations):
If:
1. All valuations under v are non-negative: ∀ (i : Fin n) (g : Fin m), 0 ≤ v i g, and
2. a_hat is an exact prediction of v in the sense of is_exact_prediction v a_hat,
Then:
The allocation produced by alg m a_hat v is a 1-EEFX allocation (is_alpha_eefx_allocation) with respect to the additive valuations induced by v.
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 algorithm alg is consistent if it returns an EEFX allocation whenever predictions are exact. -/ def is_consistent_algorithm (n : ℕ) (alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n)) : Prop := ∀ (m : ℕ) (v a_hat : Fin n → Fin m → ℝ), (∀ i g, 0 ≤ v i g) → is_exact_prediction v a_hat → is_alpha_eefx_allocation (fun i => additive_valuation (v i)) 1 (alg m a_hat v)