is_ex_ante_proportional_of_equal_marginal
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.
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)$.
intro iFor 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.
uses
Finset.sum_filterhave 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]
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`.
uses
Finset.mul_sum,Finset.sum_commsimp_rw [h1] simp_rw [Finset.mul_sum] rw [Finset.sum_comm]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$.
uses
Finset.sum_mul,Finset.sum_congrhave 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
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.
uses
Finset.sum_divsimp_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)$.
- Ex-ante proportionality for chores requires that an agent's expected cost is at most their fair share, $(1/n) \sum_j c(i, j)$. An equal-marginal lottery achieves exact equality; Lean closes the final inequality reflexively once the expected cost is rewritten into that exact form.
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 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]