online_single_high_efx_ratio
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
- op826_online_single_high_efx_upper_bound_twoFor three agents and value ratio R = 2, the online single-high EFX competitive ratio is at most the conjectured envelope min (1 /…
- op826_online_single_high_efx_ratio_le_oneFor every real value ratio R, the online single-high EFX competitive ratio for three agents is at most 1.
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 α}