AFTD Auto-Formalizing Theoretical Domains

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