is_alpha_ef1_goods
An allocation of m indivisible goods to n agents is alpha-EF1 under additive valuations u if for every pair of distinct agents i and j with j's bundle nonempty, there exists a good g in j's bundle such that alpha times i's value for j's bundle without g is at most i's value for i's own bundle.
Statement
def is_alpha_ef1_goods {m n : ℕ} (u : Fin n → Fin m → ℝ) (α : ℝ) (σ : Fin m → Fin n) : Prop
- Defined in
- arXiv:2610.34625 Sec. 2.1
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Built on 2
- bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- Used by 5
- not_has_online_alpha_ef1_four_of_gt_oneFor any alpha > 1, there is no deterministic online algorithm guaranteeing an alpha-EF1 allocation for four agents under exact frequency…
- has_online_alpha_ef1_algorithm_zeroFor any positive number of agents n, there exists a deterministic online algorithm guaranteeing a 0-EF1 allocation under exact frequency…
- is_alpha_ef1_goods_one_of_ef1_goodsIf an allocation is exactly EF1 (in the is_ef1_goods sense) for nonnegative additive valuations, then it is 1-EF1 in the…
- has_online_alpha_ef1_algorithmThere exists a deterministic online algorithm for n agents that, for any number of goods m, given exact frequency predictions a_hat and…
- op561_has_online_algorithm_monoIf there exists an online algorithm guaranteeing a beta-EF1 allocation for n agents under exact frequency predictions, then for any alpha…
Read back from the Lean
Given implicit natural numbers $m$ and $n$, a utility profile $u : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$, a real parameter $\alpha : \mathbb{R}$, and an allocation $\sigma : \text{Fin } m \to \text{Fin } n$, is_alpha_ef1_goods asserts that for all agents $i, j : \text{Fin } n$ such that $i \neq j$, if agent $j$'s assigned bundle bundle_of σ j is nonempty, then there exists an item $g \in \text{bundle_of } \sigma\ j$ such that $\alpha$ times the additive valuation by agent $i$ of agent $j$'s bundle with $g$ removed is less than or equal to the additive valuation by agent $i$ of their own bundle bundle_of σ 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
/-- An allocation σ is α-EF1 for additive valuations u if for all distinct agents i ≠ j with non-empty bundle A_j, some item g in A_j satisfies α * u_i(A_j \ {g}) ≤ u_i(A_i). -/ def is_alpha_ef1_goods {m n : ℕ} (u : Fin n → Fin m → ℝ) (α : ℝ) (σ : Fin m → Fin n) : Prop := ∀ (i j : Fin n), i ≠ j → (bundle_of σ j).Nonempty → ∃ g ∈ bundle_of σ j, α * additive_valuation (u i) ((bundle_of σ j).erase g) ≤ additive_valuation (u i) (bundle_of σ i)