AFTD Auto-Formalizing Theoretical Domains

is_consistent_algorithm

def

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

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)
See it in the graphDiscuss this resultChallenge it