AFTD Auto-Formalizing Theoretical Domains

online_single_high_efx_ratio

def

For ratio R, the online single-high EFX competitive ratio for three agents is the supremum of all alpha in [0, 1] such that for every number of goods m >= 1, there exists a deterministic online algorithm guaranteeing alpha-EFX on all single-high valuation profiles with ratio R.

Statement

noncomputable def online_single_high_efx_ratio (R : ℝ) : ℝ
Defined in
arXiv:2610.34625, Sec. 4
Verified
02 Nov 2026
Axioms
none listed
Built on 1
  • has_online_single_high_alpha_efxThere exists a deterministic online allocation algorithm for n agents and m goods that guarantees an alpha-EFX allocation for every…
Used by 2

Read back from the Lean

online_single_high_efx_ratio R is defined as the supremum (sSup in ℝ) of the set of all α : ℝ such that: 1. 0 ≤ α ≤ 1, and 2. For every positive integer m ≥ 1, there exists an online allocator alg for 3 agents and m items that guarantees an α-EFX allocation for all single-high valuation profiles with parameter R. Specifically, for 3 agents and m items: - An allocator alg : (Fin 3 → Fin m → ℝ) → (Fin m → Fin 3) is "online" if for all valuation profiles v, v' and all items t : Fin m, whenever v i s = v' i s for all agents i : Fin 3 and all items s ≤ t, we have alg v t = alg v' t. - A valuation profile v is "single-high" with parameter R if for every agent i : Fin 3, there is some item g : Fin m with valuation R, and every other item g' ≠ g has valuation 1. - An allocation σ = alg v is α-EFX for goods if for all distinct agents i ≠ j and every item g in agent j's bundle (σ g = j), α times agent i's additive valuation of j's bundle with g removed is at most agent i's additive valuation of their own bundle (σ⁻¹({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

/-- The online single-high EFX competitive ratio for three agents at ratio R is the supremum of alpha in [0, 1] guaranteeing alpha-EFX for all m >= 1. -/
noncomputable def online_single_high_efx_ratio (R : ℝ) : ℝ := sSup {α : ℝ | 0 ≤ α ∧ α ≤ 1 ∧ ∀ m : ℕ, 1 ≤ m → has_online_single_high_alpha_efx 3 m R α}
See it in the graphDiscuss this resultChallenge it