fpo_of_itemwise_weighted_max
If an allocation σ assigns each item g to an agent maximizing w_i * u_i(g) for positive weights w, then σ is fractionally Pareto optimal for additive utilities u.
Statement
theorem fpo_of_itemwise_weighted_max {m n : ℕ}
(u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n)
(w : Fin n → ℝ) (hw : ∀ i, 0 < w i)
(hmax : ∀ (g : Fin m) (j : Fin n), w j * u j g ≤ w (σ g) * u (σ g) 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
- goods_utilityThe utility vector of an allocation of goods under additive valuations: agent i's value for her own bundle.
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- 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.
- is_fractionally_pareto_optimalAn allocation of goods σ is fractionally Pareto optimal for additive valuations u if no fractional assignment x weakly improves every…
- Used by 2
- op_1004_two_type_efx_fpo_equal_ratioFor any real number a > 1, every two-agent instance on a finite set of goods where each good is valued at a by both agents or at 1 by both…
- op_1004_two_type_efx_fpo_single_typeFor two agents and any finite set of identical goods valued at c > 0 by agent 0 and d > 0 by agent 1, there exists an allocation that is…
The proof, explained
We proceed by contradiction: suppose there exists a fractional allocation $x$ that Pareto dominates $\sigma$. We evaluate the positive weighted sum of utilities under both allocations. On the one hand, because $x$ Pareto dominates $\sigma$ and all agent weights are strictly positive, the total weighted utility under $x$ must be strictly greater than that under $\sigma$. On the other hand, interchanging the summation order and using the fact that $\sigma$ maximizes the weighted utility itemwise shows that the total weighted utility under $x$ cannot exceed that under $\sigma$, yielding a contradiction.
Assume for contradiction that $\sigma$ is not fractionally Pareto optimal, so there exists a fractional allocation $x$ that Pareto dominates it.
By definition of fractional Pareto optimality (`is_fractionally_pareto_optimal`), non-optimality means there is a fractional allocation $x$ where each agent gets a non-negative share $x_{i, g} \ge 0$ of each good $g$, every good is fully distributed ($\sum_i x_{i, g} = 1$), every agent receives at least their utility under $\sigma$ ($\sum_g u_i(g) x_{i, g} \ge \text{goods\_utility}(u, \sigma, i)$), and at least one agent receives strictly more utility. We introduce these assumptions and name the hypotheses.
rintro ⟨x, hxnn, hxsum, hge, hgt⟩
The total weighted utility of $\sigma$ equals the itemwise weighted sum $\sum_g w_{\sigma(g)} u_{\sigma(g)}(g)$.
For each agent $i$, their bundle consists of the goods $g$ assigned to them ($\sigma(g) = i$), so their weighted utility is $w_i \cdot \text{goods\_utility}(u, \sigma, i) = \sum_{g \in \text{bundle\_of}(\sigma, i)} w_i u_i(g) = \sum_{g \in \text{bundle\_of}(\sigma, i)} w_{\sigma(g)} u_{\sigma(g)}(g)$. Summing over all agents partitions the goods into fibers under $\sigma$. By `Finset.sum_fiberwise`, this double sum collapses to the single sum over all items $\sum_g w_{\sigma(g)} u_{\sigma(g)}(g)$.
uses
Finset.mul_sum,Finset.sum_congr,Finset.sum_fiberwisehave hstep2 : ∑ i, w i * goods_utility u σ i = ∑ g, w (σ g) * u (σ g) g := by have h2 : ∀ i, w i * goods_utility u σ i = ∑ g ∈ bundle_of σ i, w (σ g) * u (σ g) g := by intro i rw [goods_utility, additive_valuation, Finset.mul_sum] apply Finset.sum_congr rfl intro g hg have hg' : σ g = i := by simpa [bundle_of] using hg rw [← hg'] rw [show (∑ i, w i * goods_utility u σ i) = ∑ i, ∑ g ∈ bundle_of σ i, w (σ g) * u (σ g) g from by apply Finset.sum_congr rfl; intro i _; exact h2 i] rw [← Finset.sum_fiberwise (Finset.univ : Finset (Fin m)) σ (fun g => w (σ g) * u (σ g) g)] apply Finset.sum_congr rfl intro i _ apply Finset.sum_congr · simp [bundle_of] · intro g _; rfl
The total weighted utility under the fractional allocation $x$ is at most $\sum_g w_{\sigma(g)} u_{\sigma(g)}(g)$.
Distributing the weights into each agent's utility sum and interchanging the order of summation gives $\sum_i w_i \sum_g u_i(g) x_{i, g} = \sum_g \sum_i w_i u_i(g) x_{i, g}$. By assumption, $\sigma$ assigns each item $g$ to maximize $w_i u_i(g)$, so $w_i u_i(g) \le w_{\sigma(g)} u_{\sigma(g)}(g)$ for every $i$ and $g$. Because $x_{i, g} \ge 0$, multiplying preserves this inequality. Factoring out $w_{\sigma(g)} u_{\sigma(g)}(g)$ for each item $g$, the fractions sum to $\sum_i x_{i, g} = 1$, leaving the upper bound $\sum_g w_{\sigma(g)} u_{\sigma(g)}(g)$.
uses
Finset.mul_sum,Finset.sum_congr,Finset.sum_comm,Finset.sum_le_sum,mul_onehave hstep3 : ∑ i, w i * (∑ g, u i g * x i g) ≤ ∑ g, w (σ g) * u (σ g) g := by have h3 : ∀ i, w i * (∑ g, u i g * x i g) = ∑ g, w i * u i g * x i g := by intro i rw [Finset.mul_sum] apply Finset.sum_congr rfl intro g _ ring rw [show (∑ i, w i * (∑ g, u i g * x i g)) = ∑ i, ∑ g, w i * u i g * x i g from by apply Finset.sum_congr rfl; intro i _; exact h3 i] rw [Finset.sum_comm] calc ∑ g, ∑ i, w i * u i g * x i g ≤ ∑ g, ∑ i, w (σ g) * u (σ g) g * x i g := by apply Finset.sum_le_sum intro g _ apply Finset.sum_le_sum intro i _ have h1 : w i * u i g ≤ w (σ g) * u (σ g) g := hmax g i have h2 : 0 ≤ x i g := hxnn i g nlinarith [h1, h2] _ = ∑ g, w (σ g) * u (σ g) g := by apply Finset.sum_congr rfl intro g _ rw [← Finset.mul_sum, hxsum g, mul_one]
The total weighted utility under $\sigma$ is strictly less than the total weighted utility under $x$.
Because $x$ Pareto dominates $\sigma$, every agent receives at least as much utility under $x$ as under $\sigma$, with at least one agent $k$ receiving strictly more. Since all weights are strictly positive ($w_i > 0$), multiplying by $w_i$ preserves the weak inequalities for all agents and gives a strict inequality for agent $k$. Summing over all agents with `Finset.sum_lt_sum` yields the strict inequality between the total weighted utilities.
uses
Finset.sum_lt_sum,mul_le_mul_of_nonneg_left,le_of_lt,Finset.mem_univ,mul_lt_mul_of_pos_lefthave hstep1 : ∑ i, w i * goods_utility u σ i < ∑ i, w i * (∑ g, u i g * x i g) := by apply Finset.sum_lt_sum · intro i _ exact mul_le_mul_of_nonneg_left (hge i) (le_of_lt (hw i)) · obtain ⟨k, hk⟩ := hgt exact ⟨k, Finset.mem_univ k, mul_lt_mul_of_pos_left hk (hw k)⟩
A contradiction is reached, completing the proof.
The previous steps establish that the total weighted utility under $\sigma$ is strictly less than that under $x$, which in turn is at most the itemwise weighted sum, which equals the total weighted utility under $\sigma$. This implies that a quantity is strictly less than itself, which linear arithmetic (`linarith`) detects as a contradiction.
linarith
Finset.mul_sum- Multiplication distributes over finite sums from the left: $a \cdot \sum_{i \in s} f(i) = \sum_{i \in s} a \cdot f(i)$.
Finset.sum_congr- Two finite sums are equal if their index sets are identical and their terms are equal at every element.
Finset.sum_fiberwise- Summing a function over a finite set is equal to partitioning the set by the fibers of a map and summing the inner sums over each fiber.
Finset.sum_comm- The order of summation in a double finite sum can be interchanged: $\sum_{x \in s} \sum_{y \in t} f(x, y) = \sum_{y \in t} \sum_{x \in s} f(x, y)$.
Finset.sum_le_sum- If $f(i) \le g(i)$ for all $i \in s$, then the sum of $f$ over $s$ is at most the sum of $g$ over $s$.
mul_one- Multiplying any element by 1 leaves it unchanged: $a \cdot 1 = a$.
Finset.sum_lt_sum- If $f(i) \le g(i)$ for all $i \in s$ and $f(i) < g(i)$ for at least one $i \in s$, then the sum of $f$ over $s$ is strictly less than the sum of $g$ over $s$.
mul_le_mul_of_nonneg_left- Multiplying both sides of an inequality $b \le c$ on the left by a non-negative element $a \ge 0$ preserves the inequality: $a \cdot b \le a \cdot c$.
le_of_lt- A strict inequality $a < b$ implies the weak inequality $a \le b$.
Finset.mem_univ- Every element of a finite type belongs to its universal finset `univ`.
mul_lt_mul_of_pos_left- Multiplying both sides of a strict inequality $b < c$ on the left by a strictly positive element $a > 0$ preserves the strict inequality: $a \cdot b < a \cdot c$.
- Step 3 uses the `nlinarith` tactic to multiply the itemwise inequality by the non-negative fraction $x_{i, g} \ge 0$, and Step 5 closes the contradiction $W(\sigma) < W(x) \le W(\sigma)$ using linear arithmetic (`linarith`).
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.
/-- An allocation that maximizes a positive weighted sum of utilities itemwise is fractionally Pareto optimal. -/theorem fpo_of_itemwise_weighted_max {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) (w : Fin n → ℝ) (hw : ∀ i, 0 < w i) (hmax : ∀ (g : Fin m) (j : Fin n), w j * u j g ≤ w (σ g) * u (σ g) g) : is_fractionally_pareto_optimal u σ := by rintro ⟨x, hxnn, hxsum, hge, hgt⟩ have hstep2 : ∑ i, w i * goods_utility u σ i = ∑ g, w (σ g) * u (σ g) g := by have h2 : ∀ i, w i * goods_utility u σ i = ∑ g ∈ bundle_of σ i, w (σ g) * u (σ g) g := by intro i rw [goods_utility, additive_valuation, Finset.mul_sum] apply Finset.sum_congr rfl intro g hg have hg' : σ g = i := by simpa [bundle_of] using hg rw [← hg'] rw [show (∑ i, w i * goods_utility u σ i) = ∑ i, ∑ g ∈ bundle_of σ i, w (σ g) * u (σ g) g from by apply Finset.sum_congr rfl; intro i _; exact h2 i] rw [← Finset.sum_fiberwise (Finset.univ : Finset (Fin m)) σ (fun g => w (σ g) * u (σ g) g)] apply Finset.sum_congr rfl intro i _ apply Finset.sum_congr · simp [bundle_of] · intro g _; rfl have hstep3 : ∑ i, w i * (∑ g, u i g * x i g) ≤ ∑ g, w (σ g) * u (σ g) g := by have h3 : ∀ i, w i * (∑ g, u i g * x i g) = ∑ g, w i * u i g * x i g := by intro i rw [Finset.mul_sum] apply Finset.sum_congr rfl intro g _ ring rw [show (∑ i, w i * (∑ g, u i g * x i g)) = ∑ i, ∑ g, w i * u i g * x i g from by apply Finset.sum_congr rfl; intro i _; exact h3 i] rw [Finset.sum_comm] calc ∑ g, ∑ i, w i * u i g * x i g ≤ ∑ g, ∑ i, w (σ g) * u (σ g) g * x i g := by apply Finset.sum_le_sum intro g _ apply Finset.sum_le_sum intro i _ have h1 : w i * u i g ≤ w (σ g) * u (σ g) g := hmax g i have h2 : 0 ≤ x i g := hxnn i g nlinarith [h1, h2] _ = ∑ g, w (σ g) * u (σ g) g := by apply Finset.sum_congr rfl intro g _ rw [← Finset.mul_sum, hxsum g, mul_one] have hstep1 : ∑ i, w i * goods_utility u σ i < ∑ i, w i * (∑ g, u i g * x i g) := by apply Finset.sum_lt_sum · intro i _ exact mul_le_mul_of_nonneg_left (hge i) (le_of_lt (hw i)) · obtain ⟨k, hk⟩ := hgt exact ⟨k, Finset.mem_univ k, mul_lt_mul_of_pos_left hk (hw k)⟩ linarith