is_fractionally_pareto_optimal_scale
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.
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).
uses
Finset.mul_sumprivate 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]
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).
uses
Finset.mul_sum,Finset.sum_congrprivate 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
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.
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_leftprivate 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
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.
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 hiAn 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.
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
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.
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)