has_online_single_high_alpha_efx
There exists a deterministic online allocation algorithm for n agents and m goods that guarantees an alpha-EFX allocation for every single-high valuation profile with ratio R.
Statement
def has_online_single_high_alpha_efx (n m : ℕ) (R α : ℝ) : Prop
- Defined in
- arXiv:2610.34625, Sec. 4
- Verified
- 02 Nov 2026
- Axioms
- none listed
- Built on 3
- is_online_allocatorAn allocation algorithm on m goods for n agents is online if the allocation of each arriving good t depends only on the valuation vectors…
- is_single_high_profileA valuation profile of n agents on m goods is a single-high profile with ratio R if every agent has a single-high valuation with ratio R.
- is_alpha_efx_goodsAn allocation of m indivisible goods to n agents is alpha-EFX under additive valuations u if for every pair of distinct agents i and j,…
- Used by 4
- op819_has_online_single_high_alpha_monoIf a deterministic online algorithm guarantees a beta-EFX allocation for n agents and m goods under single-high valuations with ratio R >=…
- op819_single_high_efx_one_goodFor any number of agents $n \ge 1$, $m = 1$ good, and parameter $R \ge 0$, there exists a deterministic online algorithm that achieves a…
- 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.
- online_single_high_efx_ratioFor 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…
Read back from the Lean
Given numbers of agents n and items m, and real parameters R and α, there exists an allocation rule alg : (Fin n → Fin m → ℝ) → (Fin m → Fin n) such that: 1. alg is online: for all valuation profiles v, v' and every item t : Fin m, if v i s = v' i s for all agents i and all items s ≤ t, then alg v t = alg v' t. 2. For every valuation profile v, if for every agent i there exists an item g : Fin m such that v i g = R and v i g' = 1 for all g' ≠ g, then the allocation alg v is α-EFX: for every pair of distinct agents i ≠ j and every item g assigned to agent j (i.e., alg v g = j), α times agent i's valuation of j's bundle without g (sum of v i over items assigned to j other than g) is at most agent i's valuation of their own bundle (sum of v i over items assigned to 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
/-- There exists a deterministic online allocation algorithm for n agents and m goods that guarantees an alpha-EFX allocation for every single-high valuation profile with ratio R. -/ def has_online_single_high_alpha_efx (n m : ℕ) (R α : ℝ) : Prop := ∃ alg : (Fin n → Fin m → ℝ) → (Fin m → Fin n), is_online_allocator n m alg ∧ ∀ v : Fin n → Fin m → ℝ, is_single_high_profile R v → is_alpha_efx_goods v α (alg v)