is_ef1_goods
def
EF1 for goods: every agent i either does not envy agent j, or stops envying j after some single good is removed from j's bundle.
Statement
def is_ef1_goods {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : Prop
- Defined in
- The Unreasonable Fairness of Maximum Nash Welfare, ACM TEAC 7(3), 2019, Defs. 2.1-2.2 and App. B; formalized by the operator (Claude), 2026-10-03
- Verified
- 03 Oct 2026
- Axioms
- none listed
- Built on 2
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- 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.
- Used by 3
- is_leximin_ef1An allocation is leximin-optimal among EF1 allocations: it is EF1 and no EF1 allocation is strictly leximin-better.
- lxv_is_ef1_iffIn the instance, real EF1 is equivalent to the Boolean integer check lxv_ef1.
- 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…
Lean source view module on GitHub
/-- EF1 for goods (The Unreasonable Fairness of Maximum Nash Welfare, Def. 2.2 with footnote 1): for all agents `i, j`, either `i` does not envy `j`, or removing some good from `j`'s bundle removes the envy. -/ def is_ef1_goods {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : Prop := ∀ i j, additive_valuation (u i) (bundle_of σ j) ≤ additive_valuation (u i) (bundle_of σ i) ∨ ∃ g ∈ bundle_of σ j, additive_valuation (u i) ((bundle_of σ j).erase g) ≤ additive_valuation (u i) (bundle_of σ i)