is_overestimate_prediction
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