AFTD Auto-Formalizing Theoretical Domains

has_online_single_high_alpha_efx

def

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

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)
See it in the graphDiscuss this resultChallenge it