AFTD Auto-Formalizing Theoretical Domains

lxv_ef1

def

Boolean EF1 check for allocations in the instance lxv_values.

Statement

def lxv_ef1 (a : Fin 6 → Fin 4) : Bool
Source
step towards leximin_ef1_not_pareto_optimal (conjecture of The Unreasonable Fairness of Maximum Nash Welfare, ACM TEAC 7(3), 2019, App. B)
Verified
06 Oct 2026
Axioms
none listed
Built on 2
  • lxv_valuesThe integer values of the instance: 4 agents, 6 goods, each agent's values summing to 20.
  • lxv_valAgent i's integer value for agent j's bundle under an allocation, in the instance lxv_values.
Used by 3
  • lxv_is_ef1_iffIn the instance, real EF1 is equivalent to the Boolean integer check lxv_ef1.
  • lxv_checkThe finite check over all 4^6 allocations: lxv_opt is EF1, no EF1 allocation has a strictly better leximin profile, and any EF1 allocation…
  • lxv_check_specUnpacked finite check: lxv_opt is EF1, no EF1 allocation is strictly leximin-better, and every EF1 allocation not strictly leximin-worse…

Lean source view module on GitHub

/-- Integer EF1 check for the instance `lxv_values`. -/
def lxv_ef1 (a : Fin 6 → Fin 4) : Bool :=
  (List.finRange 4).all fun i => (List.finRange 4).all fun j =>
    decide (lxv_val a i j ≤ lxv_val a i i) ||
      (List.finRange 6).any fun g => decide (a g = j) && decide (lxv_val a i j ≤ lxv_val a i i + lxv_values i g)
See it in the graphDiscuss this resultChallenge it