AFTD Auto-Formalizing Theoretical Domains

lxv_is_ef1_iff

lemmaverified

In the instance, real EF1 is equivalent to the Boolean integer check lxv_ef1.

Statement

lemma lxv_is_ef1_iff (a : Fin 6 → Fin 4) : is_ef1_goods lxv_instance a ↔ lxv_ef1 a = true
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
Classical.choiceQuot.soundpropext
Built on 7
  • 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.
  • lxv_valuesThe integer values of the instance: 4 agents, 6 goods, each agent's values summing to 20.
  • lxv_ef1Boolean EF1 check for allocations in the instance lxv_values.
  • lxv_instanceThe real instance lxv_values / 20: nonnegative additive values summing to 1 for each agent.
  • lxv_additive_valuationIn the instance, the additive value of a set is its integer value divided by 20.
  • lxv_sum_bundleThe integer value of a bundle equals the explicit six-term sum lxv_val.
  • 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 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

lemma lxv_is_ef1_iff (a : Fin 6 → Fin 4) : is_ef1_goods lxv_instance a ↔ lxv_ef1 a = true := by  simp only [is_ef1_goods, lxv_ef1, List.all_eq_true, List.mem_finRange, true_implies,    Bool.or_eq_true, decide_eq_true_eq, List.any_eq_true, Bool.and_eq_true, true_and]  have h20 : (0 : ℝ) < 20 := by norm_num  refine forall_congr' fun i => forall_congr' fun j => or_congr ?_ ?_  · rw [lxv_additive_valuation, lxv_additive_valuation, lxv_sum_bundle, lxv_sum_bundle,      div_le_div_iff_of_pos_right h20, Nat.cast_le]  · have hmem : ∀ g, g ∈ bundle_of a j ↔ a g = j := fun g => by simp [bundle_of]    refine exists_congr fun g => ?_    rw [hmem]    constructor    · rintro ⟨hg, h⟩      refine ⟨hg, ?_⟩      have hs := Finset.add_sum_erase (bundle_of a j) (lxv_values i) ((hmem g).2 hg)      rw [lxv_additive_valuation, lxv_additive_valuation, lxv_sum_bundle,        div_le_div_iff_of_pos_right h20, Nat.cast_le] at h      rw [lxv_sum_bundle] at hs      omega    · rintro ⟨hg, h⟩      refine ⟨hg, ?_⟩      have hs := Finset.add_sum_erase (bundle_of a j) (lxv_values i) ((hmem g).2 hg)      rw [lxv_additive_valuation, lxv_additive_valuation, lxv_sum_bundle,        div_le_div_iff_of_pos_right h20, Nat.cast_le]      rw [lxv_sum_bundle] at hs      omega
See it in the graphDiscuss this resultChallenge it