AFTD Auto-Formalizing Theoretical Domains

fpo_of_itemwise_weighted_max

theoremverified

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

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.

  1. 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.

    line 7

      rintro ⟨x, hxnn, hxsum, hge, hgt⟩
  2. 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)$.

    lines 8–26

    uses Finset.mul_sum, Finset.sum_congr, Finset.sum_fiberwise

      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
  3. 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)$.

    lines 27–49

    uses Finset.mul_sum, Finset.sum_congr, Finset.sum_comm, Finset.sum_le_sum, mul_one

      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]
  4. 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.

    lines 50–56

    uses Finset.sum_lt_sum, mul_le_mul_of_nonneg_left, le_of_lt, Finset.mem_univ, mul_lt_mul_of_pos_left

      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)⟩
  5. 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.

    line 57

      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$.

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

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