AFTD Auto-Formalizing Theoretical Domains

two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling

theoremverifiedformalization

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.

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

    lines 7–13

    uses mul_nonpos_of_nonneg_of_nonpos, le_of_lt

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

    lines 14–20

    uses sum_le_sum

      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⟩
  3. 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.

    lines 21–29

    uses mul_neg_of_pos_of_neg, sum_le_sum, sum_erase_add, mem_univ

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

    lines 40–49

    uses mul_nonneg, le_of_lt

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

    lines 50–66

    uses Finset.sum_congr, Finset.sum_add_distrib, Finset.sum_sub_distrib, Finset.mul_sum

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

    lines 67–70

    uses two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling_helper, two_agent_envy_freeable_iff

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

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