AFTD Auto-Formalizing Theoretical Domains

is_leximin_ef1

def

An allocation is leximin-optimal among EF1 allocations: it is EF1 and no EF1 allocation is strictly leximin-better.

Statement

def is_leximin_ef1 {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 3
  • goods_utilityThe utility vector of an allocation of goods under additive valuations: agent i's value for her own bundle.
  • is_ef1_goodsEF1 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.
  • leximin_lty is strictly leximin-better than x: the sorted profile of x is lexicographically smaller than that of y.
Used by 1
  • leximin_ef1_not_pareto_optimalChoosing the leximin-optimal allocation among EF1 allocations does not guarantee Pareto optimality, even for normalised additive…

Lean source view module on GitHub

/-- `σ` is a leximin-optimal allocation among the EF1 allocations: it is EF1 and no EF1 allocation is strictly leximin-better. -/
def is_leximin_ef1 {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : Prop :=
  is_ef1_goods u σ ∧ ∀ τ, is_ef1_goods u τ → ¬ leximin_lt (goods_utility u σ) (goods_utility u τ)
See it in the graphDiscuss this resultChallenge it