AFTD Auto-Formalizing Theoretical Domains

is_overestimate_prediction

def

Predictions a_hat : Fin n → Fin m → ℝ are overestimates of valuations v : Fin n → Fin m → ℝ with error factor ρ if for every agent i : Fin n and rank r : Fin m, sorted_tuple (v i) r ≤ sorted_tuple (a_hat i) r and sorted_tuple (a_hat i) r ≤ ρ * sorted_tuple (v i) r.

Statement

def is_overestimate_prediction {m n : ℕ} (ρ : ℝ) (v : Fin n → Fin m → ℝ) (a_hat : Fin n → Fin m → ℝ) : Prop
Defined in
arXiv:2610.34625 Sec. 6.1
Verified
27 Oct 2026
Axioms
none listed
Built on 1
  • sorted_tupleFor any tuple u : Fin m → ℝ, its sorted tuple is u ∘ Tuple.sort u, which reorders the values of u in nondecreasing order.
Used by 2
  • guarantees_alpha_eefxAn algorithm alg guarantees alpha-EEFX for n agents under error factor ρ if for every m : ℕ, all nonnegative valuations v and all…
  • 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…

Read back from the Lean

For fixed natural numbers $m$ and $n$, a real number $\rho$, and functions $v, \hat{a} : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$, the predicate is_overestimate_prediction asserts that for every $i \in \text{Fin } n$ and every $r \in \text{Fin } m$, the $r$-th component of the sorted version of $v(i)$ is less than or equal to the $r$-th component of the sorted version of $\hat{a}(i)$, which in turn is less than or equal to $\rho$ times the $r$-th component of the sorted version of $v(i)$.

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

/-- Predictions a_hat are overestimates of v with error factor rho if sorted true values <= sorted predicted values <= rho * sorted true values. -/
def is_overestimate_prediction {m n : ℕ} (ρ : ℝ) (v : Fin n → Fin m → ℝ) (a_hat : Fin n → Fin m → ℝ) : Prop :=
  ∀ (i : Fin n) (r : Fin m),
    sorted_tuple (v i) r ≤ sorted_tuple (a_hat i) r ∧ sorted_tuple (a_hat i) r ≤ ρ * sorted_tuple (v i) r
See it in the graphDiscuss this resultChallenge it