AFTD Auto-Formalizing Theoretical Domains

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

/-- **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)
See it in the graphDiscuss this resultChallenge it