two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling
For two agents with arbitrary real valuations over subsets of a finite set of items, if q is an ex-ante envy-free lottery over complete allocations, then for every coordinatewise positive vector c, there exists an allocation in the support of q that is envy-freeable at the rescaled profile c ⊙ v.
Statement
theorem two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling {M : Type*} [Fintype M] [DecidableEq M] (v : Fin 2 → Finset M → ℝ) (q : (M → Fin 2) → ℝ) (hq_nonneg : ∀ A, 0 ≤ q A) (hq_sum : ∑ A, q A = 1) (hef : ∀ i j, ∑ A, q A * v i (allocation_bundle A j) ≤ ∑ A, q A * v i (allocation_bundle A i)) (c : Fin 2 → ℝ) (hc : ∀ i, 0 < c i) : ∃ A : M → Fin 2, 0 < q A ∧ allocation_is_envy_freeable (fun i S => c i * v i S) A
- Formalizes
- arXiv:2610.14994, Theorem 4.1 (first part)
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- allocation_bundleFor a complete allocation A of the goods M to the agents N (each good to one agent), the bundle of agent i is the set of goods A assigns…
- allocation_is_envy_freeableAn allocation is envy-freeable if there are nonnegative payments p such that every agent i weakly prefers its own bundle plus payment to…
- two_agent_envy_freeable_iffFor two agents with arbitrary valuations over bundles of items, an allocation is envy-freeable if and only if the sum of agent 0's net…
- Used by 1
- two_agent_converse_theoremFor two agents with arbitrary real valuations over subsets of a finite set of items, if q is an ex-ante envy-free lottery over complete…
Read back from the Lean
Let $M$ be a finite type with decidable equality (representing a set of items). Consider two agents indexed by $\mathrm{Fin}\ 2 = \{0, 1\}$. Let $v : \mathrm{Fin}\ 2 \to \mathrm{Finset}\ M \to \mathbb{R}$ be valuation functions for both agents over subsets of $M$. Let $q : (M \to \mathrm{Fin}\ 2) \to \mathbb{R}$ be a lottery (probability distribution) over allocations of items to the two agents, satisfying: 1. $q(A) \ge 0$ for all allocations $A : M \to \mathrm{Fin}\ 2$; 2. $\sum_{A} q(A) = 1$; 3. Ex-ante envy-freeness: for all agents $i, j \in \mathrm{Fin}\ 2$, the expected valuation agent $i$ receives from their own bundle under $q$ is at least their expected valuation from agent $j$'s bundle, i.e., $$\sum_{A} q(A) v(i, \{g \in M \mid A(g) = j\}) \le \sum_{A} q(A) v(i, \{g \in M \mid A(g) = i\}).$$ Let $c : \mathrm{Fin}\ 2 \to \mathbb{R}$ be a profile of strictly positive scaling factors, so $c(i) > 0$ for all $i \in \mathrm{Fin}\ 2$. Then there exists an allocation $A : M \to \mathrm{Fin}\ 2$ in the support of $q$ ($q(A) > 0$) such that the rescaled valuation profile $(i, S) \mapsto c(i) \cdot v(i, S)$ is envy-freeable at $A$. That is, there exists a vector of non-negative subsidies/transfers $p : \mathrm{Fin}\ 2 \to \mathbb{R}$ such that $p(i) \ge 0$ for all $i \in \mathrm{Fin}\ 2$, and for all $i, j \in \mathrm{Fin}\ 2$, $$c(i) \cdot v(i, \{g \in M \mid A(g) = j\}) + p(j) \le c(i) \cdot v(i, \{g \in M \mid A(g) = i\}) + p(i).$$
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
To show that an ex-ante envy-free lottery contains an allocation envy-freeable under any positive rescaling $c$, we reduce envy-freeability to a scalar inequality using the two-agent characterization: an allocation $A$ is envy-freeable under $c \odot v$ if and only if the weighted surplus $f(A) = c_0 (v_0(A_0) - v_0(A_1)) + c_1 (v_1(A_1) - v_1(A_0))$ is nonnegative. By ex-ante envy-freeness, each agent's expected surplus is nonnegative, so the expected weighted surplus $\sum_A q(A) f(A)$ is a sum of nonnegative terms and thus nonnegative. A probabilistic helper lemma then guarantees that any lottery with nonnegative expected value must assign positive probability to an outcome with $f(A) \ge 0$, which is therefore envy-freeable.
Assuming for contradiction that every outcome with positive probability has $f(x) < 0$, the product $q(x) f(x) \le 0$ for every $x$.
We proceed by contradiction (using classical logic), assuming that whenever $q(x) > 0$, we have $f(x) < 0$. For any $x$, we split into cases based on whether $q(x) > 0$ or $q(x) = 0$. If $q(x) > 0$, then $f(x) < 0$, so their product is nonpositive by `mul_nonpos_of_nonneg_of_nonpos` (weakening $q(x) > 0$ to $0 \le q(x)$ via `le_of_lt`). If $q(x) = 0$, the product is $0$. Hence, $q(x) f(x) \le 0$ everywhere.
uses
mul_nonpos_of_nonneg_of_nonpos,le_of_ltclassical by_contra! h have h_le : ∀ x, q x * f x ≤ 0 := by intro x rcases (hq_nonneg x).lt_or_eq with hpos | heq · exact mul_nonpos_of_nonneg_of_nonpos (le_of_lt hpos) (le_of_lt (h x hpos)) · simp [← heq]
There exists at least one outcome $x_0$ with strictly positive probability $q(x_0) > 0$.
If instead $q(x) \le 0$ for all $x$, then summing over the entire type gives $\sum_x q(x) \le \sum_x 0 = 0$ by `sum_le_sum`. But this contradicts the assumption that $q$ is a probability distribution with total sum $\sum_x q(x) = 1$. Thus, there must exist some $x_0$ with $q(x_0) > 0$. We fix such an outcome $x_0$.
uses
sum_le_sumhave hex : ∃ x, 0 < q x := by by_contra! hq_all have : ∑ x, q x ≤ 0 := by calc ∑ x, q x ≤ ∑ x : α, (0 : ℝ) := sum_le_sum (fun x _ => hq_all x) _ = 0 := by simp linarith rcases hex with ⟨x0, hx0⟩
There exists an outcome $x$ such that $q(x) > 0$ and $f(x) \ge 0$.
For the outcome $x_0$ with $q(x_0) > 0$, the contradiction hypothesis gives $f(x_0) < 0$, which makes $q(x_0) f(x_0) < 0$ strictly negative by `mul_neg_of_pos_of_neg`. The sum over the remaining outcomes, $\sum_{x \ne x_0} q(x) f(x)$, is at most $0$ by `sum_le_sum` applied to the bound $q(x) f(x) \le 0$. Recombining the total sum via `sum_erase_add` and `mem_univ` gives $\sum_x q(x) f(x) < 0$, contradicting the hypothesis $0 \le \sum_x q(x) f(x)$. This finishes the proof of the helper lemma.
uses
mul_neg_of_pos_of_neg,sum_le_sum,sum_erase_add,mem_univhave h_strict : q x0 * f x0 < 0 := mul_neg_of_pos_of_neg hx0 (h x0 hx0) have h_other : ∑ x ∈ univ.erase x0, q x * f x ≤ 0 := by calc ∑ x ∈ univ.erase x0, q x * f x ≤ ∑ x ∈ univ.erase x0, (0 : ℝ) := sum_le_sum (fun x _ => h_le x) _ = 0 := by simp have h_tot : ∑ x, q x * f x < 0 := by rw [← sum_erase_add (s := univ) (f := fun x => q x * f x) (mem_univ x0)] linarith linarith
For each agent, their rescaled expected surplus from their own bundle over the other agent's bundle is nonnegative.
We define the net surplus function $f(A) = [c_0 v_0(A_0) - c_0 v_0(A_1)] + [c_1 v_1(A_1) - c_1 v_1(A_0)]$. By ex-ante envy-freeness, agent 0 expects at least as much value from their own bundle as from agent 1's bundle: $\sum_A q(A) v_0(A_1) \le \sum_A q(A) v_0(A_0)$. Because $c_0 > 0$, the weighted difference $c_0 (\sum_A q(A) v_0(A_0) - \sum_A q(A) v_0(A_1))$ is nonnegative by `mul_nonneg` and `le_of_lt`. By the symmetric ex-ante envy-freeness condition for agent 1 and $c_1 > 0$, the term $c_1 (\sum_A q(A) v_1(A_1) - \sum_A q(A) v_1(A_0))$ is also nonnegative.
uses
mul_nonneg,le_of_ltopen Finset in let f : (M → Fin 2) → ℝ := fun A => (c 0 * v 0 (allocation_bundle A 0) - c 0 * v 0 (allocation_bundle A 1)) + (c 1 * v 1 (allocation_bundle A 1) - c 1 * v 1 (allocation_bundle A 0)) have h0 : 0 ≤ c 0 * ((∑ A, q A * v 0 (allocation_bundle A 0)) - (∑ A, q A * v 0 (allocation_bundle A 1))) := by apply mul_nonneg (le_of_lt (hc 0)) linarith [hef 0 1] have h1 : 0 ≤ c 1 * ((∑ A, q A * v 1 (allocation_bundle A 1)) - (∑ A, q A * v 1 (allocation_bundle A 0))) := by apply mul_nonneg (le_of_lt (hc 1)) linarith [hef 1 0]
The expected value of $f$ under the lottery $q$, $\sum_A q(A) f(A)$, is nonnegative.
Expanding $f(A)$ and distributing multiplication and summation via `Finset.sum_congr`, `Finset.sum_add_distrib`, `Finset.sum_sub_distrib`, and `Finset.mul_sum`, we rewrite $\sum_A q(A) f(A)$ as the sum of the two weighted surplus terms from the previous step: $c_0 (\sum_A q(A) v_0(A_0) - \sum_A q(A) v_0(A_1)) + c_1 (\sum_A q(A) v_1(A_1) - \sum_A q(A) v_1(A_0))$. Since both terms are nonnegative, linear arithmetic establishes that $\sum_A q(A) f(A) \ge 0$.
uses
Finset.sum_congr,Finset.sum_add_distrib,Finset.sum_sub_distrib,Finset.mul_sumhave hsum_eq : ∑ A, q A * f A = c 0 * ((∑ A, q A * v 0 (allocation_bundle A 0)) - (∑ A, q A * v 0 (allocation_bundle A 1))) + c 1 * ((∑ A, q A * v 1 (allocation_bundle A 1)) - (∑ A, q A * v 1 (allocation_bundle A 0))) := by calc ∑ A, q A * f A = ∑ A, (c 0 * (q A * v 0 (allocation_bundle A 0)) - c 0 * (q A * v 0 (allocation_bundle A 1)) + (c 1 * (q A * v 1 (allocation_bundle A 1)) - c 1 * (q A * v 1 (allocation_bundle A 0)))) := by apply Finset.sum_congr rfl; intro A _; dsimp [f]; ring _ = (c 0 * ∑ A, q A * v 0 (allocation_bundle A 0) - c 0 * ∑ A, q A * v 0 (allocation_bundle A 1)) + (c 1 * ∑ A, q A * v 1 (allocation_bundle A 1) - c 1 * ∑ A, q A * v 1 (allocation_bundle A 0)) := by simp only [Finset.sum_add_distrib, Finset.sum_sub_distrib, ← Finset.mul_sum] _ = c 0 * (∑ A, q A * v 0 (allocation_bundle A 0) - ∑ A, q A * v 0 (allocation_bundle A 1)) + c 1 * (∑ A, q A * v 1 (allocation_bundle A 1) - ∑ A, q A * v 1 (allocation_bundle A 0)) := by ring have hf_sum : 0 ≤ ∑ A, q A * f A := by rw [hsum_eq] linarith
There exists an allocation $A$ in the support of $q$ that is envy-freeable under the rescaled valuations $c \odot v$.
Applying the helper lemma `two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling_helper` to the distribution $q$ and function $f$, there is an allocation $A$ with $q(A) > 0$ and $f(A) \ge 0$. By `two_agent_envy_freeable_iff`, the condition $f(A) \ge 0$ is necessary and sufficient for $A$ to be envy-freeable under the rescaled valuations $(i, S) \mapsto c_i v_i(S)$.
uses
two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling_helper,two_agent_envy_freeable_iffrcases two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling_helper q f hq_nonneg hq_sum hf_sum with ⟨A, hqA, hfA⟩ use A, hqA rw [two_agent_envy_freeable_iff] exact hfA
mul_nonpos_of_nonneg_of_nonpos- If $a \ge 0$ and $b \le 0$, then $a \cdot b \le 0$.
le_of_lt- If $a < b$, then $a \le b$.
sum_le_sum- If $f(i) \le g(i)$ for all $i$ in a finite set $s$, then $\sum_{i \in s} f(i) \le \sum_{i \in s} g(i)$.
mul_neg_of_pos_of_neg- If $a > 0$ and $b < 0$, then $a \cdot b < 0$.
sum_erase_add- For any element $a \in s$, $\sum_{x \in s \setminus \{a\}} f(x) + f(a) = \sum_{x \in s} f(x)$.
mem_univ- Every element of a finite type belongs to its universal finset.
mul_nonneg- If $a \ge 0$ and $b \ge 0$, then $a \cdot b \ge 0$.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree at every element.
Finset.sum_add_distrib- The sum of a sum of functions over a finite set equals the sum of the individual sums: $\sum_{x \in s} (f(x) + g(x)) = \sum_{x \in s} f(x) + \sum_{x \in s} g(x)$.
Finset.sum_sub_distrib- The sum of a difference of functions over a finite set equals the difference of the individual sums: $\sum_{x \in s} (f(x) - g(x)) = \sum_{x \in s} f(x) - \sum_{x \in s} g(x)$.
Finset.mul_sum- Multiplication by a scalar distributes over a finite sum: $a \cdot \sum_{i \in s} f(i) = \sum_{i \in s} a \cdot f(i)$.
two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling_helper- If $q$ is a probability distribution on a finite set and $\sum_x q(x) f(x) \ge 0$, then there exists some $x$ with $q(x) > 0$ and $f(x) \ge 0$.
two_agent_envy_freeable_iff- For two agents, an allocation is envy-freeable under valuation profile $v$ if and only if the sum of both agents' surpluses from their own bundle over the other agent's bundle is nonnegative.
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.
open Finset inlemma two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling_helper {α : Type*} [Fintype α] (q : α → ℝ) (f : α → ℝ) (hq_nonneg : ∀ x, 0 ≤ q x) (hq_sum : ∑ x, q x = 1) (h_sum : 0 ≤ ∑ x, q x * f x) : ∃ x, 0 < q x ∧ 0 ≤ f x := by classical by_contra! h have h_le : ∀ x, q x * f x ≤ 0 := by intro x rcases (hq_nonneg x).lt_or_eq with hpos | heq · exact mul_nonpos_of_nonneg_of_nonpos (le_of_lt hpos) (le_of_lt (h x hpos)) · simp [← heq] have hex : ∃ x, 0 < q x := by by_contra! hq_all have : ∑ x, q x ≤ 0 := by calc ∑ x, q x ≤ ∑ x : α, (0 : ℝ) := sum_le_sum (fun x _ => hq_all x) _ = 0 := by simp linarith rcases hex with ⟨x0, hx0⟩ have h_strict : q x0 * f x0 < 0 := mul_neg_of_pos_of_neg hx0 (h x0 hx0) have h_other : ∑ x ∈ univ.erase x0, q x * f x ≤ 0 := by calc ∑ x ∈ univ.erase x0, q x * f x ≤ ∑ x ∈ univ.erase x0, (0 : ℝ) := sum_le_sum (fun x _ => h_le x) _ = 0 := by simp have h_tot : ∑ x, q x * f x < 0 := by rw [← sum_erase_add (s := univ) (f := fun x => q x * f x) (mem_univ x0)] linarith linarith/-- For two agents, every ex-ante envy-free lottery contains in its support an allocation that is envy-freeable under any positive rescaling of valuations. -/theorem two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling {M : Type*} [Fintype M] [DecidableEq M] (v : Fin 2 → Finset M → ℝ) (q : (M → Fin 2) → ℝ) (hq_nonneg : ∀ A, 0 ≤ q A) (hq_sum : ∑ A, q A = 1) (hef : ∀ i j, ∑ A, q A * v i (allocation_bundle A j) ≤ ∑ A, q A * v i (allocation_bundle A i)) (c : Fin 2 → ℝ) (hc : ∀ i, 0 < c i) : ∃ A : M → Fin 2, 0 < q A ∧ allocation_is_envy_freeable (fun i S => c i * v i S) A := by open Finset in let f : (M → Fin 2) → ℝ := fun A => (c 0 * v 0 (allocation_bundle A 0) - c 0 * v 0 (allocation_bundle A 1)) + (c 1 * v 1 (allocation_bundle A 1) - c 1 * v 1 (allocation_bundle A 0)) have h0 : 0 ≤ c 0 * ((∑ A, q A * v 0 (allocation_bundle A 0)) - (∑ A, q A * v 0 (allocation_bundle A 1))) := by apply mul_nonneg (le_of_lt (hc 0)) linarith [hef 0 1] have h1 : 0 ≤ c 1 * ((∑ A, q A * v 1 (allocation_bundle A 1)) - (∑ A, q A * v 1 (allocation_bundle A 0))) := by apply mul_nonneg (le_of_lt (hc 1)) linarith [hef 1 0] have hsum_eq : ∑ A, q A * f A = c 0 * ((∑ A, q A * v 0 (allocation_bundle A 0)) - (∑ A, q A * v 0 (allocation_bundle A 1))) + c 1 * ((∑ A, q A * v 1 (allocation_bundle A 1)) - (∑ A, q A * v 1 (allocation_bundle A 0))) := by calc ∑ A, q A * f A = ∑ A, (c 0 * (q A * v 0 (allocation_bundle A 0)) - c 0 * (q A * v 0 (allocation_bundle A 1)) + (c 1 * (q A * v 1 (allocation_bundle A 1)) - c 1 * (q A * v 1 (allocation_bundle A 0)))) := by apply Finset.sum_congr rfl; intro A _; dsimp [f]; ring _ = (c 0 * ∑ A, q A * v 0 (allocation_bundle A 0) - c 0 * ∑ A, q A * v 0 (allocation_bundle A 1)) + (c 1 * ∑ A, q A * v 1 (allocation_bundle A 1) - c 1 * ∑ A, q A * v 1 (allocation_bundle A 0)) := by simp only [Finset.sum_add_distrib, Finset.sum_sub_distrib, ← Finset.mul_sum] _ = c 0 * (∑ A, q A * v 0 (allocation_bundle A 0) - ∑ A, q A * v 0 (allocation_bundle A 1)) + c 1 * (∑ A, q A * v 1 (allocation_bundle A 1) - ∑ A, q A * v 1 (allocation_bundle A 0)) := by ring have hf_sum : 0 ≤ ∑ A, q A * f A := by rw [hsum_eq] linarith rcases two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling_helper q f hq_nonneg hq_sum hf_sum with ⟨A, hqA, hfA⟩ use A, hqA rw [two_agent_envy_freeable_iff] exact hfA