guarantees_alpha_eefx
An algorithm alg guarantees alpha-EEFX for n agents under error factor ρ if for every m : ℕ, all nonnegative valuations v and all predictions a_hat that are overestimates with factor ρ, the allocation alg m a_hat v is alpha-EEFX.
Statement
def guarantees_alpha_eefx (n : ℕ) (alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n)) (ρ α : ℝ) : Prop
- Defined in
- arXiv:2610.34625 Sec. 6.1
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Built on 3
- is_overestimate_predictionPredictions a_hat : Fin n → Fin m → ℝ are overestimates of valuations v : Fin n → Fin m → ℝ with error factor ρ if for every agent i : Fin…
- is_alpha_eefx_allocationAn allocation is alpha-EEFX if each agent's bundle is alpha-EEFX for that agent.
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- Used by 2
- op562_not_consistent_eefx_of_ge_three_halvesFor any number of agents n at least 3 and any error factor rho at least 3/2, no consistent online algorithm can guarantee any positive…
- has_consistent_eefx_algorithmThere exists an online, consistent algorithm alg for n agents and a positive constant α > 0 such that alg guarantees α-EEFX under error…
Read back from the Lean
guarantees_alpha_eefx n alg ρ α asserts that for a fixed number of agents n, an allocation algorithm alg (which takes the number of goods m, a predicted valuation profile a_hat, and a true valuation profile v, and outputs an allocation Fin m → Fin n), and real parameters ρ and α:
For every number of goods m : ℕ, and for all valuation profiles v, a_hat : Fin n → Fin m → ℝ:
If:
1. Every valuation in v is non-negative (∀ i g, 0 ≤ v i g), and
2. a_hat is a ρ-overestimate prediction of v in the sense that for every agent i : Fin n and rank r : Fin m, the r-th entry of v i sorted non-decreasingly is bounded above by the r-th entry of a_hat i sorted non-decreasingly, which in turn is bounded above by ρ times the r-th entry of v i sorted non-decreasingly,
Then:
The allocation σ = alg m a_hat v is an α-EEFX allocation for the additive valuations induced by v. That is, for every agent i : Fin n, agent i's assigned bundle S = {g : Fin m | σ g = i} is an α-EEFX bundle: there exists a partition of all remaining goods Finset.univ \ S into n - 1 pairwise disjoint subsets Y : Fin (n - 1) → Finset (Fin m) such that for every p : Fin (n - 1) and every good g ∈ Y p, α * (∑ j ∈ (Y p).erase g, v i j) ≤ ∑ j ∈ S, v i j.
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
/-- An algorithm guarantees alpha-EEFX under error factor rho if its allocations are alpha-EEFX for all valid instances. -/ def guarantees_alpha_eefx (n : ℕ) (alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n)) (ρ α : ℝ) : Prop := ∀ (m : ℕ) (v a_hat : Fin n → Fin m → ℝ), (∀ i g, 0 ≤ v i g) → is_overestimate_prediction ρ v a_hat → is_alpha_eefx_allocation (fun i => additive_valuation (v i)) α (alg m a_hat v)