AFTD Auto-Formalizing Theoretical Domains

is_exact_prediction

def

Frequency 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 tuple of a_hat i equals the sorted tuple of v i.

Statement

def is_exact_prediction {m n : ℕ} (v : Fin n → Fin m → ℝ) (a_hat : Fin n → Fin m → ℝ) : Prop
Defined in
arXiv:2610.34625 Sec. 6
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 5
  • is_consistent_algorithmAn online algorithm alg for n agents is consistent if for every m : ℕ and all nonnegative valuations v and predictions a_hat with exact…
  • not_has_online_alpha_ef1_four_of_gt_oneFor any alpha > 1, there is no deterministic online algorithm guaranteeing an alpha-EF1 allocation for four agents under exact frequency…
  • has_online_alpha_ef1_algorithm_zeroFor any positive number of agents n, there exists a deterministic online algorithm guaranteeing a 0-EF1 allocation under exact frequency…
  • has_online_alpha_ef1_algorithmThere exists a deterministic online algorithm for n agents that, for any number of goods m, given exact frequency predictions a_hat and…
  • op561_has_online_algorithm_monoIf there exists an online algorithm guaranteeing a beta-EF1 allocation for n agents under exact frequency predictions, then for any alpha…

Read back from the Lean

For natural numbers m and n, and two families of m-tuples of real numbers v, a_hat : Fin n → Fin m → ℝ, is_exact_prediction v a_hat asserts that for every index i : Fin n, the sorted tuple of a_hat i equals the sorted tuple 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 exact for v if sorted_tuple (a_hat i) = sorted_tuple (v i) for all agents i. -/
def is_exact_prediction {m n : ℕ} (v : Fin n → Fin m → ℝ) (a_hat : Fin n → Fin m → ℝ) : Prop :=
  ∀ i : Fin n, sorted_tuple (a_hat i) = sorted_tuple (v i)
See it in the graphDiscuss this resultChallenge it