lxv_check_spec
lemmaverified
Unpacked finite check: lxv_opt is EF1, no EF1 allocation is strictly leximin-better, and every EF1 allocation not strictly leximin-worse than lxv_opt is lxv_opt.
Statement
lemma lxv_check_spec : lxv_ef1 lxv_opt = true ∧ ∀ τ : Fin 6 → Fin 4, lxv_ef1 τ = true →
¬ List.Lex (· < ·) (lxv_profile lxv_opt) (lxv_profile τ) ∧
(List.Lex (· < ·) (lxv_profile τ) (lxv_profile lxv_opt) ∨ τ = lxv_opt)- 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 5
- lxv_ef1Boolean EF1 check for allocations in the instance lxv_values.
- lxv_profileInteger leximin profile (sorted own-bundle values) of an allocation in the instance lxv_values.
- lxv_optThe allocation with bundles {g2,g3}, {g4}, {g1,g5}, {g6}.
- 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_eq_trueThe finite check lxv_check evaluates to true (kernel computation).
- Used by 3
- WickContraction.getDual?_eq_some_iff_memWickContraction.getDual?_eq_some_iff_mem
- leximin_ef1_not_pareto_optimalChoosing the leximin-optimal allocation among EF1 allocations does not guarantee Pareto optimality, even for normalised additive…
- WickContraction.mem_uncontracted_iff_not_contractedWickContraction.mem_uncontracted_iff_not_contracted
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_check_spec : lxv_ef1 lxv_opt = true ∧ ∀ τ : Fin 6 → Fin 4, lxv_ef1 τ = true → ¬ List.Lex (· < ·) (lxv_profile lxv_opt) (lxv_profile τ) ∧ (List.Lex (· < ·) (lxv_profile τ) (lxv_profile lxv_opt) ∨ τ = lxv_opt) := by have h := lxv_check_eq_true simp only [lxv_check, Bool.and_eq_true, List.all_eq_true, List.mem_finRange, true_implies, Bool.or_eq_true, Bool.not_eq_true', decide_eq_false_iff_not, decide_eq_true_eq] at h refine ⟨h.1, fun τ hτ => ?_⟩ have hτ' : (![τ 0, τ 1, τ 2, τ 3, τ 4, τ 5] : Fin 6 → Fin 4) = τ := by ext g; fin_cases g <;> rfl have := h.2 (τ 0) (τ 1) (τ 2) (τ 3) (τ 4) (τ 5) rw [hτ'] at this rcases this with h1 | ⟨h1, h2⟩ · rw [hτ] at h1; exact absurd h1 (by simp) · refine ⟨h1, h2.imp id fun h3 => funext fun g => ?_⟩ simpa using h3 g