AFTD Auto-Formalizing Theoretical Domains

has_online_alpha_ef1_algorithm

def

There exists a deterministic online algorithm for n agents that, for any number of goods m, given exact frequency predictions a_hat and arriving nonnegative additive valuations v, produces an alpha-EF1 allocation.

Statement

def has_online_alpha_ef1_algorithm (n : ℕ) (α : ℝ) : Prop
Defined in
arXiv:2610.34625 Sec. 2, Sec. 5
Verified
27 Oct 2026
Axioms
none listed
Built on 3
  • is_alpha_ef1_goodsAn allocation of m indivisible goods to n agents is alpha-EF1 under additive valuations u if for every pair of distinct agents i and j…
  • is_online_algorithmFor an allocation algorithm alg taking a number of goods m : ℕ, predicted valuation profiles a_hat : Fin n → Fin m → ℝ, and true valuation…
  • 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…
Used by 8

Read back from the Lean

Given a number of agents n : ℕ and an approximation ratio α : ℝ, has_online_alpha_ef1_algorithm n α asserts that there exists an allocation algorithm alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n) such that: 1. alg is an online algorithm: for all m : ℕ, all predicted valuation profiles a_hat, all valuation profiles v and v', and all item indices t : Fin m, if v and v' agree on all items s ≤ t (i.e., ∀ s ≤ t, ∀ i : Fin n, v i s = v' i s), then the allocation of item t is identical: alg m a_hat v t = alg m a_hat v' t. 2. For every number of items m : ℕ, every valuation profile v : Fin n → Fin m → ℝ, and every predicted valuation profile a_hat : Fin n → Fin m → ℝ: - if all valuations are non-negative (∀ i g, 0 ≤ v i g), and - a_hat is an exact prediction of v in the sense that for every agent i : Fin n, the sorted values of a_hat i equal the sorted values of v i (i.e., a_hat i is a permutation of v i), - then the allocation σ = alg m a_hat v satisfies α-EF1 (envy-freeness up to one good scaled by factor α): for every pair of distinct agents i ≠ j such that j's bundle is nonempty, there exists a good g in j's bundle such that α times agent i's valuation of j's bundle with g removed is at most agent i's valuation of i's own bundle.

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

/-- Existence of a deterministic online algorithm guaranteeing an α-EF1 allocation for n agents given exact frequency predictions. -/
def has_online_alpha_ef1_algorithm (n : ℕ) (α : ℝ) : Prop :=
  ∃ (alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n)),
    is_online_algorithm n alg ∧
    ∀ (m : ℕ) (v a_hat : Fin n → Fin m → ℝ),
      (∀ i g, 0 ≤ v i g) →
      is_exact_prediction v a_hat →
      is_alpha_ef1_goods v α (alg m a_hat v)
See it in the graphDiscuss this resultChallenge it