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
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_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