leximin_ef1_not_pareto_optimal
theoremverifiedoriginal
Choosing the leximin-optimal allocation among EF1 allocations does not guarantee Pareto optimality, even for normalised additive valuations: with 4 agents and 6 goods, a leximin-optimal EF1 allocation exists and every one is Pareto-dominated.
Statement
theorem leximin_ef1_not_pareto_optimal :
∃ u : Fin 4 → Fin 6 → ℝ, (∀ i g, 0 ≤ u i g) ∧ (∀ i, ∑ g, u i g = 1) ∧
(∃ σ, is_leximin_ef1 u σ) ∧ ∀ σ, is_leximin_ef1 u σ → ¬ is_pareto_optimal_goods u σ- Related work
- operator (Claude), 2026-10-03: counterexample to leximin-among-EF1 being Pareto optimal, confirming the conjecture in The Unreasonable Fairness of Maximum Nash Welfare, ACM TEAC 7(3), 2019, Defs. 2.1-2.2 and App. B ("we conjecture that it does not"); 4 agents, 6 goods, values normalised to sum to 1; found by random search, checked in exact arithmetic and by the Lean kernel
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- is_leximin_ef1An allocation is leximin-optimal among EF1 allocations: it is EF1 and no EF1 allocation is strictly leximin-better.
- is_pareto_optimal_goodsAn allocation of goods is Pareto optimal if no allocation Pareto-dominates it.
- lxv_valuesThe integer values of the instance: 4 agents, 6 goods, each agent's values summing to 20.
- lxv_valAgent i's integer value for agent j's bundle under an allocation, in the instance lxv_values.
- lxv_optThe allocation with bundles {g2,g3}, {g4}, {g1,g5}, {g6}.
- lxv_domThe allocation with bundles {g2,g3}, {g5}, {g1,g4}, {g6} (agents 2 and 3 swap g4 and g5).
- lxv_instanceThe real instance lxv_values / 20: nonnegative additive values summing to 1 for each agent.
- lxv_check_specUnpacked finite check: lxv_opt is EF1, no EF1 allocation is strictly leximin-better, and every EF1 allocation not strictly leximin-worse…
- lxv_goods_utilityThe real utility vector of an allocation in the instance is its integer own-bundle values divided by 20.
- lxv_is_ef1_iffIn the instance, real EF1 is equivalent to the Boolean integer check lxv_ef1.
- lxv_leximin_lt_iffIn the instance, the real leximin comparison is equivalent to the lexicographic comparison of integer profiles.
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.
/-- **Leximin among EF1 allocations is not Pareto optimal** (conjectured in The Unreasonable Fairness of Maximum Nash Welfare, App. B). Four agents, six goods, additive values normalised to sum to 1: there is a leximin-optimal EF1 allocation, and every leximin-optimal EF1 allocation is Pareto-dominated. -/theorem leximin_ef1_not_pareto_optimal : ∃ u : Fin 4 → Fin 6 → ℝ, (∀ i g, 0 ≤ u i g) ∧ (∀ i, ∑ g, u i g = 1) ∧ (∃ σ, is_leximin_ef1 u σ) ∧ ∀ σ, is_leximin_ef1 u σ → ¬ is_pareto_optimal_goods u σ := by obtain ⟨hopt, hall⟩ := lxv_check_spec have hlex : is_leximin_ef1 lxv_instance lxv_opt := by refine ⟨(lxv_is_ef1_iff _).2 hopt, fun τ hτ => ?_⟩ rw [lxv_leximin_lt_iff] exact (hall τ ((lxv_is_ef1_iff τ).1 hτ)).1 refine ⟨lxv_instance, fun i g => by unfold lxv_instance; positivity, fun i => ?_, ⟨_, hlex⟩, ?_⟩ · simp only [lxv_instance, ← Finset.sum_div, Fin.sum_univ_six] fin_cases i <;> simp [lxv_values] <;> norm_num · intro σ hσ have hσo : σ = lxv_opt := by rcases (hall σ ((lxv_is_ef1_iff σ).1 hσ.1)).2 with h | h · exact absurd ((lxv_leximin_lt_iff _ _).2 h) (hσ.2 _ hlex.1) · exact h subst hσo intro hpo apply hpo have hN : (∀ i, lxv_val lxv_opt i i ≤ lxv_val lxv_dom i i) ∧ lxv_val lxv_opt 2 2 < lxv_val lxv_dom 2 2 := by decide refine ⟨lxv_dom, fun i => ?_, 2, ?_⟩ · rw [lxv_goods_utility, lxv_goods_utility] exact div_le_div_of_nonneg_right (Nat.cast_le.2 (hN.1 i)) (by norm_num) · rw [lxv_goods_utility, lxv_goods_utility] exact div_lt_div_of_pos_right (Nat.cast_lt.2 hN.2) (by norm_num)