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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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 _ _