AFTD Auto-Formalizing Theoretical Domains

is_ex_ante_proportional_of_equal_marginal

theoremverified

Every equal-marginal lottery over complete chore allocations is ex-ante proportional for any profile of chore costs.

Statement

theorem is_ex_ante_proportional_of_equal_marginal {m n : ℕ} (c : Fin n → Fin m → ℝ)
    (p : (Fin m → Fin n) → ℝ) (hp : is_equal_marginal_lottery p) :
    is_ex_ante_proportional_chores c p
Source
arXiv:2609.35280
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • is_equal_marginal_lotteryA lottery p over complete allocations of m chores to n agents has equal marginals if every chore g is assigned to every agent i with…
  • is_ex_ante_proportional_choresAn allocation lottery p over allocations of m chores among n agents is ex-ante proportional for chore cost functions c if each agent i's…
  • 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.

Read back from the Lean

Given natural numbers m and n, a chore cost function c : Fin n → Fin m → ℝ, and a lottery/weight function p : (Fin m → Fin n) → ℝ, if p is an equal-marginal lottery—meaning that for every item g : Fin m and every agent i : Fin n, the sum of p(σ) over all allocations σ : Fin m → Fin n assigning g to i equals 1 / n—then p is ex-ante proportional for chores with respect to c, meaning that for every agent i : Fin n, the expected cost under p, ∑ σ, p(σ) * (∑ j with σ(j) = i, c i j), is at most (∑ e : Fin m, c i e) / n.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

By linearity of expectation, an agent's expected chore cost under the lottery is the sum of the expected costs incurred from each chore individually. Because the lottery has equal marginals, every chore is assigned to any given agent with probability exactly $1/n$, contributing $c(i, j)/n$ to agent $i$'s expected cost. Summing over all chores yields an expected cost of exactly $(1/n) \sum_j c(i, j)$, which satisfies ex-ante proportionality.

  1. It suffices to show ex-ante proportionality for an arbitrary agent $i$.

    Fix an agent $i$. Ex-ante proportionality for chores requires showing that agent $i$'s expected cost under lottery $p$ is at most $(1/n) \sum_j c(i, j)$.

    line 5

      intro i
  2. For any allocation $\sigma$, agent $i$'s valuation is $\sum_j (\text{if } \sigma(j) = i \text{ then } c(i, j) \text{ else } 0)$.

    By definition, the bundle allocated to agent $i$ under assignment $\sigma$ is the set of chores $j$ with $\sigma(j) = i$. Expanding the definitions of `additive_valuation` and `bundle_of`, and converting the filtered sum into an unconditional sum with an indicator function via `Finset.sum_filter`, gives this expression.

    lines 6–8

    uses Finset.sum_filter

      have h1 (σ : Fin m → Fin n) : additive_valuation (c i) (bundle_of σ i) = ∑ j, if σ j = i then c i j else 0 := by
        dsimp [additive_valuation, bundle_of]
        rw [Finset.sum_filter]
  3. Agent $i$'s expected total cost can be written as a sum over chores: $\sum_j \sum_\sigma p(\sigma) \cdot (\text{if } \sigma(j) = i \text{ then } c(i, j) \text{ else } 0)$.

    Substituting the indicator formula for the valuation into the expected cost, we distribute the lottery probabilities $p(\sigma)$ inside the inner sum using `Finset.mul_sum`, and then swap the order of summation using `Finset.sum_comm`.

    lines 9–11

    uses Finset.mul_sum, Finset.sum_comm

      simp_rw [h1]
      simp_rw [Finset.mul_sum]
      rw [Finset.sum_comm]
  4. For each chore $j$, the expected cost incurred by agent $i$ is $c(i, j) / n$.

    Factoring the constant $c(i, j)$ out of the sum over allocations using `Finset.sum_mul` and `Finset.sum_congr`, the remaining sum is $\sum_\sigma (\text{if } \sigma(j) = i \text{ then } p(\sigma) \text{ else } 0)$, which represents the marginal probability that chore $j$ is assigned to agent $i$. By the equal-marginal assumption `hp`, this marginal probability is $1/n$, so the expectation evaluates to $(1/n) \cdot c(i, j) = c(i, j) / n$.

    lines 12–19

    uses Finset.sum_mul, Finset.sum_congr

      have h2 (j : Fin m) : (∑ σ, p σ * if σ j = i then c i j else 0) = c i j / ↑n := by
        have h3 : (∑ σ, p σ * if σ j = i then c i j else 0) = (∑ σ, (if σ j = i then p σ else 0)) * c i j := by
          rw [Finset.sum_mul]
          apply Finset.sum_congr rfl
          intro σ _
          split_ifs <;> ring
        rw [h3, hp j i]
        ring
  5. Agent $i$'s expected total cost equals $(1/n) \sum_j c(i, j)$, which completes the proof.

    Substituting the per-chore expected costs into the sum over all chores replaces the left-hand side with $\sum_j (c(i, j) / n)$. Pulling the division by $n$ outside the sum using `Finset.sum_div` leaves $(\sum_j c(i, j)) / n \le (\sum_j c(i, j)) / n$, which holds identically by reflexivity.

    lines 20–21

    uses Finset.sum_div

      simp_rw [h2]
      rw [← Finset.sum_div]
Finset.sum_filter
The sum of a function over elements of a finite set satisfying a predicate equals the sum over the entire set with terms where the predicate fails replaced by 0.
Finset.mul_sum
Left multiplication by a factor distributes over a finite sum: $a \sum_i f(i) = \sum_i a f(i)$.
Finset.sum_comm
The order of summation in a finite double sum can be exchanged: $\sum_x \sum_y f(x, y) = \sum_y \sum_x f(x, y)$.
Finset.sum_mul
Right multiplication by a factor distributes over a finite sum: $(\sum_i f(i)) a = \sum_i f(i) a$.
Finset.sum_congr
Two finite sums are equal if their index sets coincide and their summands agree on every element.
Finset.sum_div
Dividing a finite sum by a scalar equals the sum of the individually divided terms: $(\sum_i f(i)) / a = \sum_i (f(i) / a)$.

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 equal-marginal chore lottery is ex-ante proportional. -/theorem is_ex_ante_proportional_of_equal_marginal {m n : ℕ} (c : Fin n → Fin m → ℝ)    (p : (Fin m → Fin n) → ℝ) (hp : is_equal_marginal_lottery p) :    is_ex_ante_proportional_chores c p := by  intro i  have h1 (σ : Fin m → Fin n) : additive_valuation (c i) (bundle_of σ i) = ∑ j, if σ j = i then c i j else 0 := by    dsimp [additive_valuation, bundle_of]    rw [Finset.sum_filter]  simp_rw [h1]  simp_rw [Finset.mul_sum]  rw [Finset.sum_comm]  have h2 (j : Fin m) : (∑ σ, p σ * if σ j = i then c i j else 0) = c i j / ↑n := by    have h3 : (∑ σ, p σ * if σ j = i then c i j else 0) = (∑ σ, (if σ j = i then p σ else 0)) * c i j := by      rw [Finset.sum_mul]      apply Finset.sum_congr rfl      intro σ _      split_ifs <;> ring    rw [h3, hp j i]    ring  simp_rw [h2]  rw [← Finset.sum_div]
See it in the graphDiscuss this resultChallenge it