AFTD Auto-Formalizing Theoretical Domains

is_fractionally_pareto_optimal_scale

theoremverified

Multiplying each agent's additive valuation vector by a positive scale c_i > 0 preserves and reflects fractional Pareto optimality.

Statement

theorem is_fractionally_pareto_optimal_scale {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n)
    (c : Fin n → ℝ) (hc : ∀ i, 0 < c i) :
    is_fractionally_pareto_optimal (fun i g => c i * u i g) σ ↔
    is_fractionally_pareto_optimal u σ
Source
step towards scaled_common_ratio_bivalued_efx_fpo_envyfreeable
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • is_fractionally_pareto_optimalAn allocation of goods σ is fractionally Pareto optimal for additive valuations u if no fractional assignment x weakly improves every…
  • goods_utilityThe utility vector of an allocation of goods under additive valuations: agent i's value for her own bundle.
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.

The proof, explained

An allocation is fractionally Pareto optimal if and only if there does not exist a fractional allocation that Pareto-dominates it. Because agents' valuations are additive, multiplying agent i's valuation vector by a positive constant c_i > 0 scales both their discrete bundle utility and their utility from any fractional allocation by exactly c_i. Since multiplying by a positive scalar preserves and reflects both weak and strict inequalities, a fractional allocation Pareto-dominates under the scaled valuations if and only if it does so under the original valuations. Taking the contrapositive of this equivalence shows that fractional Pareto optimality is invariant under positive scaling.

  1. Scaling an agent's valuation by a constant c_i scales their discrete bundle utility under allocation σ by c_i: goods_utility (c · u) σ i = c_i * goods_utility u σ i.

    By definition, an agent's discrete bundle utility is the additive valuation of the set of goods assigned to them under σ. Multiplying each item's valuation by c_i allows c_i to be factored out of the summation over the bundle using the distributivity of multiplication over finite sums (Finset.mul_sum).

    lines 1–5

    uses Finset.mul_sum

    private theorem is_fractionally_pareto_optimal_scale_gu {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n)
        (c : Fin n → ℝ) (i : Fin n) :
        goods_utility (fun i g => c i * u i g) σ i = c i * goods_utility u σ i := by
      simp [goods_utility, additive_valuation, Finset.mul_sum]
    
  2. Scaling valuations by a scalar c scales the utility of any fractional allocation x by c: ∑ g, (c * u g) * x g = c * ∑ g, u g * x g.

    Factoring c out of the sum turns c * ∑ g, u g * x g into ∑ g, c * (u g * x g) via Finset.mul_sum. Applying Finset.sum_congr reduces the equality of sums to the term-by-term equality (c * u g) * x g = c * (u g * x g), which holds by associativity of multiplication in ℝ (ring).

    lines 6–12

    uses Finset.mul_sum, Finset.sum_congr

    private theorem is_fractionally_pareto_optimal_scale_fs {m : ℕ} (u : Fin m → ℝ) (x : Fin m → ℝ) (c : ℝ) :
        ∑ g, (c * u g) * x g = c * ∑ g, u g * x g := by
      rw [Finset.mul_sum]
      apply Finset.sum_congr rfl
      intro g _
      ring
    
  3. If a fractional allocation Pareto-dominates σ under the scaled valuations c_i * u, it also Pareto-dominates σ under the original valuations u.

    Given a fractional allocation x that weakly improves every agent's utility and strictly improves at least one agent under the scaled valuations, the allocation x remains valid because non-negativity and sum-to-one constraints do not depend on valuations. For each agent i, rewriting the scaled weak inequality with is_fractionally_pareto_optimal_scale_gu and is_fractionally_pareto_optimal_scale_fs yields c_i * goods_utility u σ i ≤ c_i * ∑ g, u i g * x i g. Since c_i > 0, dividing by c_i via mul_le_mul_iff_of_pos_left yields the weak inequality for the original valuations. Similarly, rewriting the strict inequality for the strictly improved agent and dividing by c_i > 0 via mul_lt_mul_iff_of_pos_left yields the required strict inequality.

    lines 13–31

    uses is_fractionally_pareto_optimal_scale_gu, is_fractionally_pareto_optimal_scale_fs, mul_le_mul_iff_of_pos_left, mul_lt_mul_iff_of_pos_left

    private theorem fpo_exist_scale {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n)
        (c : Fin n → ℝ) (hc : ∀ i, 0 < c i) :
        (∃ x : Fin n → Fin m → ℝ, (∀ i g, 0 ≤ x i g) ∧ (∀ g, ∑ i, x i g = 1) ∧
          (∀ i, goods_utility (fun i g => c i * u i g) σ i ≤ ∑ g, (c i * u i g) * x i g) ∧
          ∃ i, goods_utility (fun i g => c i * u i g) σ i < ∑ g, (c i * u i g) * x i g) ↔
        (∃ x : Fin n → Fin m → ℝ, (∀ i g, 0 ≤ x i g) ∧ (∀ g, ∑ i, x i g = 1) ∧
          (∀ i, goods_utility u σ i ≤ ∑ g, u i g * x i g) ∧
          ∃ i, goods_utility u σ i < ∑ g, u i g * x i g) := by
      constructor
      · rintro ⟨x, hx, hsum, hle, hlt⟩
        refine ⟨x, hx, hsum, ?_, ?_⟩
        · intro i
          have h := hle i
          rw [is_fractionally_pareto_optimal_scale_gu, is_fractionally_pareto_optimal_scale_fs] at h
          exact (mul_le_mul_iff_of_pos_left (hc i)).mp h
        · obtain ⟨i, hi⟩ := hlt
          refine ⟨i, ?_⟩
          rw [is_fractionally_pareto_optimal_scale_gu, is_fractionally_pareto_optimal_scale_fs] at hi
          exact (mul_lt_mul_iff_of_pos_left (hc i)).mp hi
  4. Conversely, if a fractional allocation Pareto-dominates σ under the original valuations u, it also Pareto-dominates σ under the scaled valuations c_i * u.

    Given a fractional allocation x that Pareto-dominates σ under original valuations u, the same allocation x satisfies validity. For every agent i, multiplying the assumed weak inequality by c_i > 0 via mul_le_mul_iff_of_pos_left and rewriting both sides using is_fractionally_pareto_optimal_scale_gu and is_fractionally_pareto_optimal_scale_fs yields the weak inequality under scaled valuations. Likewise, multiplying the strict inequality for the improved agent by c_i > 0 via mul_lt_mul_iff_of_pos_left and rewriting establishes the strict inequality under scaled valuations.

    lines 32–41

    uses is_fractionally_pareto_optimal_scale_gu, is_fractionally_pareto_optimal_scale_fs, mul_le_mul_iff_of_pos_left, mul_lt_mul_iff_of_pos_left

      · rintro ⟨x, hx, hsum, hle, hlt⟩
        refine ⟨x, hx, hsum, ?_, ?_⟩
        · intro i
          rw [is_fractionally_pareto_optimal_scale_gu, is_fractionally_pareto_optimal_scale_fs]
          exact (mul_le_mul_iff_of_pos_left (hc i)).mpr (hle i)
        · obtain ⟨i, hi⟩ := hlt
          refine ⟨i, ?_⟩
          rw [is_fractionally_pareto_optimal_scale_gu, is_fractionally_pareto_optimal_scale_fs]
          exact (mul_lt_mul_iff_of_pos_left (hc i)).mpr hi
    
  5. An allocation σ is fractionally Pareto optimal under scaled valuations if and only if it is fractionally Pareto optimal under the original valuations.

    Unfolding the definition of fractional Pareto optimality expresses it as the negation of the existence of a fractional Pareto improvement. The lemma fpo_exist_scale established that the existence of a fractional Pareto improvement under scaled valuations is equivalent to its existence under original valuations. Applying not_congr takes the contrapositive equivalence of their negations, completing the proof.

    lines 42–48

    uses not_congr, fpo_exist_scale

    /-- Fractional Pareto optimality of an allocation is invariant under multiplying each agent's valuation vector by a positive constant. -/
    theorem is_fractionally_pareto_optimal_scale {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n)
        (c : Fin n → ℝ) (hc : ∀ i, 0 < c i) :
        is_fractionally_pareto_optimal (fun i g => c i * u i g) σ ↔
        is_fractionally_pareto_optimal u σ := by
      simp only [is_fractionally_pareto_optimal]
      exact not_congr (fpo_exist_scale u σ c hc)
Finset.mul_sum
Left multiplication distributes over a finite sum: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_congr
Two finite sums over the same index set are equal if their summands are equal at every element.
is_fractionally_pareto_optimal_scale_gu
Multiplying an agent's valuation vector by a constant c_i scales their discrete bundle utility under allocation σ by c_i.
is_fractionally_pareto_optimal_scale_fs
A scalar constant c can be factored out of a sum of weighted valuations: ∑ g, (c * u g) * x g = c * ∑ g, u g * x g.
mul_le_mul_iff_of_pos_left
Multiplication by a strictly positive element preserves and reflects weak inequalities: for a > 0, a * b ≤ a * c ↔ b ≤ c.
mul_lt_mul_iff_of_pos_left
Multiplication by a strictly positive element preserves and reflects strict inequalities: for a > 0, a * b < a * c ↔ b < c.
fpo_exist_scale
For positive scaling factors c_i > 0, there exists a fractional Pareto improvement under the scaled valuations if and only if there exists one under the original valuations.
not_congr
Logical equivalence is preserved under negation: (P ↔ Q) → (¬P ↔ ¬Q).

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

private theorem is_fractionally_pareto_optimal_scale_gu {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n)    (c : Fin n → ℝ) (i : Fin n) :    goods_utility (fun i g => c i * u i g) σ i = c i * goods_utility u σ i := by  simp [goods_utility, additive_valuation, Finset.mul_sum]private theorem is_fractionally_pareto_optimal_scale_fs {m : ℕ} (u : Fin m → ℝ) (x : Fin m → ℝ) (c : ℝ) :    ∑ g, (c * u g) * x g = c * ∑ g, u g * x g := by  rw [Finset.mul_sum]  apply Finset.sum_congr rfl  intro g _  ringprivate theorem fpo_exist_scale {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n)    (c : Fin n → ℝ) (hc : ∀ i, 0 < c i) :    (∃ x : Fin n → Fin m → ℝ, (∀ i g, 0 ≤ x i g) ∧ (∀ g, ∑ i, x i g = 1) ∧      (∀ i, goods_utility (fun i g => c i * u i g) σ i ≤ ∑ g, (c i * u i g) * x i g) ∧      ∃ i, goods_utility (fun i g => c i * u i g) σ i < ∑ g, (c i * u i g) * x i g) ↔    (∃ x : Fin n → Fin m → ℝ, (∀ i g, 0 ≤ x i g) ∧ (∀ g, ∑ i, x i g = 1) ∧      (∀ i, goods_utility u σ i ≤ ∑ g, u i g * x i g) ∧      ∃ i, goods_utility u σ i < ∑ g, u i g * x i g) := by  constructor  · rintro ⟨x, hx, hsum, hle, hlt⟩    refine ⟨x, hx, hsum, ?_, ?_⟩    · intro i      have h := hle i      rw [is_fractionally_pareto_optimal_scale_gu, is_fractionally_pareto_optimal_scale_fs] at h      exact (mul_le_mul_iff_of_pos_left (hc i)).mp h    · obtain ⟨i, hi⟩ := hlt      refine ⟨i, ?_⟩      rw [is_fractionally_pareto_optimal_scale_gu, is_fractionally_pareto_optimal_scale_fs] at hi      exact (mul_lt_mul_iff_of_pos_left (hc i)).mp hi  · rintro ⟨x, hx, hsum, hle, hlt⟩    refine ⟨x, hx, hsum, ?_, ?_⟩    · intro i      rw [is_fractionally_pareto_optimal_scale_gu, is_fractionally_pareto_optimal_scale_fs]      exact (mul_le_mul_iff_of_pos_left (hc i)).mpr (hle i)    · obtain ⟨i, hi⟩ := hlt      refine ⟨i, ?_⟩      rw [is_fractionally_pareto_optimal_scale_gu, is_fractionally_pareto_optimal_scale_fs]      exact (mul_lt_mul_iff_of_pos_left (hc i)).mpr hi/-- Fractional Pareto optimality of an allocation is invariant under multiplying each agent's valuation vector by a positive constant. -/theorem is_fractionally_pareto_optimal_scale {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n)    (c : Fin n → ℝ) (hc : ∀ i, 0 < c i) :    is_fractionally_pareto_optimal (fun i g => c i * u i g) σ ↔    is_fractionally_pareto_optimal u σ := by  simp only [is_fractionally_pareto_optimal]  exact not_congr (fpo_exist_scale u σ c hc)
See it in the graphDiscuss this resultChallenge it