AFTD Auto-Formalizing Theoretical Domains

lxv_leximin_lt_iff

lemmaverified

In the instance, the real leximin comparison is equivalent to the lexicographic comparison of integer profiles.

Statement

lemma lxv_leximin_lt_iff (a b : Fin 6 → Fin 4) :
    leximin_lt (goods_utility lxv_instance a) (goods_utility lxv_instance b) ↔
      List.Lex (· < ·) (lxv_profile a) (lxv_profile b)
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
  • goods_utilityThe utility vector of an allocation of goods under additive valuations: agent i's value for her own bundle.
  • leximin_profileThe leximin profile of a utility vector: its entries sorted in increasing order.
  • leximin_lty is strictly leximin-better than x: the sorted profile of x is lexicographically smaller than that of y.
  • list_lex_map_iff_of_strictMonoA strictly monotone map from naturals to reals preserves and reflects the strict lexicographic order on lists.
  • lxv_profileInteger leximin profile (sorted own-bundle values) of an allocation in the instance lxv_values.
  • lxv_instanceThe real instance lxv_values / 20: nonnegative additive values summing to 1 for each agent.
  • lxv_goods_utilityThe real utility vector of an allocation in the instance is its integer own-bundle values divided by 20.
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_leximin_lt_iff (a b : Fin 6 → Fin 4) :    leximin_lt (goods_utility lxv_instance a) (goods_utility lxv_instance b) ↔      List.Lex (· < ·) (lxv_profile a) (lxv_profile b) := by  have hf : StrictMono fun k : ℕ => (k : ℝ) / 20 := fun x y h =>    div_lt_div_of_pos_right (Nat.cast_lt.2 h) (by norm_num)  have hprof : ∀ c : Fin 6 → Fin 4, leximin_profile (goods_utility lxv_instance c) =      (lxv_profile c).map fun k : ℕ => (k : ℝ) / 20 := by    intro c    rw [lxv_goods_utility, leximin_profile, lxv_profile,      List.map_insertionSort (r := (· ≤ ·)) (s := (· ≤ ·))]    · rw [List.map_ofFn]; rfl    · intro x _ y _; exact hf.le_iff_le.symm  rw [leximin_lt, hprof, hprof]  exact list_lex_map_iff_of_strictMono hf _ _
See it in the graphDiscuss this resultChallenge it