AFTD Auto-Formalizing Theoretical Domains

two_agent_welfare_regret_nonneg

theoremverified

For any number of goods m : ℕ, any drafting schedule s : Fin m → Fin 2 of length m, and any nonnegative valuation profile v : Fin 2 → Fin m → ℝ, the utilitarian welfare regret two_agent_welfare_regret m s v is nonnegative.

Statement

theorem two_agent_welfare_regret_nonneg (m : ℕ) (s : Fin m → Fin 2) (v : Fin 2 → Fin m → ℝ)
    (hv : ∀ i g, 0 ≤ v i g) :
    0 ≤ two_agent_welfare_regret m s v
Source
arXiv:2611.09685
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • two_agent_welfare_regretGiven a number of goods m : ℕ, a drafting schedule s : Fin m → Fin 2 of length m, and valuations v : Fin 2 → Fin m → ℝ, the utilitarian…
  • two_agent_draft_welfareGiven a number of goods m : ℕ, a drafting schedule s : Fin m → Fin 2 of length m, and a valuation profile v : Fin 2 → Fin m → ℝ, the…
  • two_agent_first_best_welfareThe first-best utilitarian welfare for two agents over m goods, defined as the sum over all goods of the maximum value assigned by either…
  • draft_allocGiven a preference profile assigning each agent a linear order on objects, a list of agents representing the turn order, and a finite set…
  • draft_ruleGiven types Agent and Object with decidable equality and finite Object, an implicit natural number T, a picking sequence s : Fin T ->…
  • balanced_draft_value_orderThe strict preference order induced by a real value vector, ordered first by increasing value and then by increasing good index; hence a…

Read back from the Lean

For every natural number $m$, every draft turn sequence $s : \text{Fin } m \to \text{Fin } 2$, and every valuation profile $v : \text{Fin } 2 \to \text{Fin } m \to \mathbb{R}$, if $v(i, g) \ge 0$ for all agents $i : \text{Fin } 2$ and all items $g : \text{Fin } m$, then the two-agent welfare regret two_agent_welfare_regret m s v is greater than or equal to $0$.

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

The proof shows that two-agent utilitarian welfare regret is nonnegative by establishing that the draft welfare is bounded above by the first-best welfare. First, induction on the drafting sequence proves that the mechanism allocates mutually disjoint sets of goods to distinct agents. Second, each agent's valuation for any assigned item is bounded by the maximum valuation between the two agents for that item. Because the bundles are disjoint and valuations are nonnegative, the sum of values over both drafted bundles is bounded by the sum of pairwise maximums over all goods, which is the first-best welfare.

  1. When the list of turns is empty, any agent's draft allocation is a subset of the remaining items

    We proceed by induction on the list l of agent turns. In the base case l = [], draft_alloc allocates the empty set to each agent, which is a subset of rem.

    lines 5–8

      induction l generalizing rem i with
      | nil =>
        intro x hx
        simp [draft_alloc] at hx
  2. In the inductive step, the draft allocation to each agent remains a subset of the remaining items

    When the turn list starts with agent a, if rem is empty the allocation is empty. If rem is nonempty, agent a takes the maximum available item under their order (which belongs to rem by Finset.max'_mem), and the remaining items are drafted recursively from rem with that item removed. By the induction hypothesis and Finset.mem_of_mem_erase, recursive allocations are subsets of rem. Thus all allocations are subsets of rem.

    lines 9–22

    uses Finset.max'_mem, Finset.mem_of_mem_erase

      | cons a rest ih =>
        intro x hx
        unfold draft_alloc at hx
        split_ifs at hx with h
        · dsimp only at hx
          rcases eq_or_ne i a with rfl | hne
          · simp only [Function.update_apply, ite_true, Finset.mem_insert] at hx
            rcases hx with rfl | hx
            · exact @Finset.max'_mem Object (succ i) rem h
            · exact Finset.mem_of_mem_erase (ih (rem.erase (@Finset.max' Object (succ i) rem h)) i hx)
          · have hne' : (i = a) = False := by simp [hne]
            simp only [Function.update_apply, hne', ite_false] at hx
            exact Finset.mem_of_mem_erase (ih (rem.erase (@Finset.max' Object (succ a) rem h)) i hx)
        · simp at hx
  3. When the list of turns is empty, distinct agents receive disjoint allocations

    We proceed by induction on the turn list l. In the base case l = [], draft_alloc allocates the empty set to everyone, and the empty set is disjoint from any set by Finset.disjoint_empty_left.

    lines 29–32

    uses Finset.disjoint_empty_left

      induction l generalizing rem i j with
      | nil =>
        unfold draft_alloc
        exact Finset.disjoint_empty_left _
  4. In the inductive step, if the first turn belongs to agent i, the allocations to i and j (with i ≠ j) are disjoint

    Suppose for contradiction that an item x belongs to both allocations with i = a. Since i ≠ j, agent j is not active, so by two_agent_welfare_regret_nonneg_draft_alloc_subset agent j only receives items from the recursive draft on rem without the maximum item. Hence x cannot be the maximum item and must come from the recursive allocation for both i and j, contradicting the induction hypothesis via Finset.disjoint_iff_ne.

    lines 33–57

    uses Finset.disjoint_iff_ne, two_agent_welfare_regret_nonneg_draft_alloc_subset

      | cons a rest ih =>
        unfold draft_alloc
        split_ifs with h
        · dsimp only
          rw [Finset.disjoint_iff_ne]
          intro x hx y hy hxy
          subst hxy
          by_cases hia : i = a
          · have hja : ¬ j = a := by intro h; subst h; exact hij hia
            have h1 : (i = a) = True := by simp [hia]
            have h2 : (j = a) = False := by simp [hja]
            simp only [Function.update_apply, h1, ite_true, Finset.mem_insert] at hx
            simp only [Function.update_apply, h2, ite_false] at hy
            have hy_rem := two_agent_welfare_regret_nonneg_draft_alloc_subset succ rest
              (rem.erase (@Finset.max' Object (succ a) rem h)) j hy
            have hy_ne_max : x ≠ @Finset.max' Object (succ a) rem h := by
              intro h_eq
              subst h_eq
              exact (Finset.mem_erase.mp hy_rem).1 rfl
            rcases hx with rfl | hx'
            · exact hy_ne_max rfl
            · have hx'' : x ∈ draft_alloc succ rest (rem.erase (@Finset.max' Object (succ a) rem h)) i := by
                cases hia; exact hx'
              have hd := ih (rem := rem.erase (@Finset.max' Object (succ a) rem h)) hij
              exact Finset.disjoint_iff_ne.mp hd x hx'' x hy rfl
  5. In the inductive step, if the first turn belongs to agent j, the allocations to i and j are disjoint

    Symmetrically, if j = a and i ≠ a, agent i only receives items from the recursive draft. Hence a shared item x cannot be the maximum item and must belong to both agents' recursive allocations, which contradicts the induction hypothesis.

    lines 58–74

    uses two_agent_welfare_regret_nonneg_draft_alloc_subset

          · by_cases hja : j = a
            · have h1 : (i = a) = False := by simp [hia]
              have h2 : (j = a) = True := by simp [hja]
              simp only [Function.update_apply, h1, ite_false] at hx
              simp only [Function.update_apply, h2, ite_true, Finset.mem_insert] at hy
              have hx_rem := two_agent_welfare_regret_nonneg_draft_alloc_subset succ rest
                (rem.erase (@Finset.max' Object (succ a) rem h)) i hx
              have hx_ne_max : x ≠ @Finset.max' Object (succ a) rem h := by
                intro h_eq
                subst h_eq
                exact (Finset.mem_erase.mp hx_rem).1 rfl
              rcases hy with rfl | hy'
              · exact hx_ne_max rfl
              · have hy'' : x ∈ draft_alloc succ rest (rem.erase (@Finset.max' Object (succ a) rem h)) j := by
                  cases hja; exact hy'
                have hd := ih (rem := rem.erase (@Finset.max' Object (succ a) rem h)) hij
                exact Finset.disjoint_iff_ne.mp hd x hx x hy'' rfl
  6. In all other cases of the inductive step, the allocations to i and j are disjoint

    If neither i nor j is the active agent a, both receive only recursive allocations, which are disjoint by the induction hypothesis. If rem is empty, both allocations are empty and disjoint by Finset.disjoint_empty_left.

    lines 75–82

    uses Finset.disjoint_empty_left

            · have h1 : (i = a) = False := by simp [hia]
              have h2 : (j = a) = False := by simp [hja]
              simp only [Function.update_apply, h1, ite_false] at hx
              simp only [Function.update_apply, h2, ite_false] at hy
              have hd := ih (rem := rem.erase (@Finset.max' Object (succ a) rem h)) hij
              exact Finset.disjoint_iff_ne.mp hd x hx x hy rfl
        · simp only
          exact Finset.disjoint_empty_left _
  7. Nonnegativity of welfare regret reduces to showing that draft welfare is at most first-best welfare

    By definition, regret is first-best welfare minus draft welfare, and by sub_nonneg, 0 ≤ A - B is equivalent to B ≤ A. Unfolding the definitions and expanding the two-agent sum with Fin.sum_univ_two, the goal is to bound the sum of agent 0's and agent 1's draft valuations by the sum of pairwise maximum valuations.

    lines 88–91

    uses Fin.sum_univ_two, sub_nonneg

      rw [two_agent_welfare_regret, sub_nonneg]
      unfold two_agent_draft_welfare two_agent_first_best_welfare
      rw [Fin.sum_univ_two]
      let succ := fun j => balanced_draft_value_order (v j)
  8. The bundles of goods drafted by agent 0 and agent 1 are disjoint

    By two_agent_welfare_regret_nonneg_draft_alloc_disjoint applied to the draft schedule s and initial goods set Finset.univ, the allocations to agent 0 and agent 1 are disjoint since 0 ≠ 1.

    lines 92–93

    uses two_agent_welfare_regret_nonneg_draft_alloc_disjoint

      have hd : Disjoint (draft_rule s succ 0) (draft_rule s succ 1) := by
        exact two_agent_welfare_regret_nonneg_draft_alloc_disjoint succ (List.ofFn s) Finset.univ (by decide)
  9. Each agent's draft welfare is bounded by the sum of maximum valuations over their bundle

    For each agent (0 and 1), their valuation for any good g is bounded above by max (v 0 g) (v 1 g) via le_max_left and le_max_right. Summing these over each agent's bundle with Finset.sum_le_sum bounds each agent's draft welfare.

    lines 94–101

    uses Finset.sum_le_sum, le_max_left, le_max_right

      have h0 : (∑ g ∈ draft_rule s succ 0, v 0 g) ≤ ∑ g ∈ draft_rule s succ 0, max (v 0 g) (v 1 g) := by
        apply Finset.sum_le_sum
        intro g _
        exact le_max_left (v 0 g) (v 1 g)
      have h1 : (∑ g ∈ draft_rule s succ 1, v 1 g) ≤ ∑ g ∈ draft_rule s succ 1, max (v 0 g) (v 1 g) := by
        apply Finset.sum_le_sum
        intro g _
        exact le_max_right (v 0 g) (v 1 g)
  10. The sum of maximum valuations over both bundles equals the sum over their union

    Because the two bundles are disjoint, Finset.sum_union merges the two sums into a single sum of max (v 0 g) (v 1 g) over the union of the two drafted bundles.

    lines 102–105

    uses Finset.sum_union

      have h_union : (∑ g ∈ draft_rule s succ 0, max (v 0 g) (v 1 g)) +
          (∑ g ∈ draft_rule s succ 1, max (v 0 g) (v 1 g)) =
          ∑ g ∈ draft_rule s succ 0 ∪ draft_rule s succ 1, max (v 0 g) (v 1 g) := by
        rw [Finset.sum_union hd]
  11. The sum of maximum valuations over the union of bundles is bounded by the first-best welfare

    The union of the drafted bundles is a subset of all goods Finset.univ by Finset.subset_univ. Since valuations are nonnegative, max (v 0 g) (v 1 g) ≥ v 0 g ≥ 0 by le_trans and le_max_left. By Finset.sum_le_sum_of_subset_of_nonneg, the sum over the subset is bounded by the sum over all goods (the first-best welfare).

    lines 106–110

    uses Finset.subset_univ, Finset.sum_le_sum_of_subset_of_nonneg, le_max_left, le_trans

      have h_sub : (∑ g ∈ draft_rule s succ 0 ∪ draft_rule s succ 1, max (v 0 g) (v 1 g)) ≤
          ∑ g : Fin m, max (v 0 g) (v 1 g) := by
        apply Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ _)
        intro g _ _
        exact le_trans (hv 0 g) (le_max_left (v 0 g) (v 1 g))
  12. The utilitarian welfare regret is nonnegative automation

    Linear arithmetic (linarith) chains the inequalities: total draft welfare is at most the sum of maximums over the union, which is at most the first-best welfare. Hence first-best welfare minus draft welfare is nonnegative.

    line 111

      linarith
Fin.sum_univ_two
The sum of a function over the two-element type Fin 2 equals the sum of its values at 0 and 1: ∑ i, f i = f 0 + f 1
Finset.disjoint_empty_left
The empty set is disjoint from any set: Disjoint ∅ s
Finset.disjoint_iff_ne
Two sets are disjoint if and only if no element in the first equals any element in the second: Disjoint s t ↔ ∀ a ∈ s, ∀ b ∈ t, a ≠ b
Finset.max'_mem
The maximum element of a nonempty finite set belongs to that set: s.max' H ∈ s
Finset.mem_of_mem_erase
An element belonging to s with an element removed also belongs to s: b ∈ s.erase a → b ∈ s
Finset.subset_univ
Every finite set in a finite type is a subset of the universal set: s ⊆ Finset.univ
Finset.sum_le_sum
If f(i) ≤ g(i) for all i in s, then the sum of f over s is at most the sum of g over s
Finset.sum_le_sum_of_subset_of_nonneg
If s ⊆ t and f is nonnegative on t \ s, then the sum of f over s is at most the sum over t
Finset.sum_union
The sum of a function over the union of two disjoint sets equals the sum of the sums over each set
le_max_left
Any value a is less than or equal to max a b
le_max_right
Any value b is less than or equal to max a b
le_trans
If a ≤ b and b ≤ c, then a ≤ c
sub_nonneg
The difference a - b is nonnegative if and only if b ≤ a
two_agent_welfare_regret_nonneg_draft_alloc_disjoint
Goods allocated to distinct agents during the drafting process are disjoint
two_agent_welfare_regret_nonneg_draft_alloc_subset
Goods allocated to an agent during the drafting process from a set of remaining items form a subset of those items

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

lemma two_agent_welfare_regret_nonneg_draft_alloc_subset    {Agent Object : Type*} [DecidableEq Agent] [DecidableEq Object]    (succ : Agent → LinearOrder Object) (l : List Agent) (rem : Finset Object) (i : Agent) :    draft_alloc succ l rem i ⊆ rem := by  induction l generalizing rem i with  | nil =>    intro x hx    simp [draft_alloc] at hx  | cons a rest ih =>    intro x hx    unfold draft_alloc at hx    split_ifs at hx with h    · dsimp only at hx      rcases eq_or_ne i a with rfl | hne      · simp only [Function.update_apply, ite_true, Finset.mem_insert] at hx        rcases hx with rfl | hx        · exact @Finset.max'_mem Object (succ i) rem h        · exact Finset.mem_of_mem_erase (ih (rem.erase (@Finset.max' Object (succ i) rem h)) i hx)      · have hne' : (i = a) = False := by simp [hne]        simp only [Function.update_apply, hne', ite_false] at hx        exact Finset.mem_of_mem_erase (ih (rem.erase (@Finset.max' Object (succ a) rem h)) i hx)    · simp at hxlemma two_agent_welfare_regret_nonneg_draft_alloc_disjoint    {Agent Object : Type*} [DecidableEq Agent] [DecidableEq Object]    (succ : Agent → LinearOrder Object) (l : List Agent) (rem : Finset Object)    {i j : Agent} (hij : i ≠ j) :    Disjoint (draft_alloc succ l rem i) (draft_alloc succ l rem j) := by  induction l generalizing rem i j with  | nil =>    unfold draft_alloc    exact Finset.disjoint_empty_left _  | cons a rest ih =>    unfold draft_alloc    split_ifs with h    · dsimp only      rw [Finset.disjoint_iff_ne]      intro x hx y hy hxy      subst hxy      by_cases hia : i = a      · have hja : ¬ j = a := by intro h; subst h; exact hij hia        have h1 : (i = a) = True := by simp [hia]        have h2 : (j = a) = False := by simp [hja]        simp only [Function.update_apply, h1, ite_true, Finset.mem_insert] at hx        simp only [Function.update_apply, h2, ite_false] at hy        have hy_rem := two_agent_welfare_regret_nonneg_draft_alloc_subset succ rest          (rem.erase (@Finset.max' Object (succ a) rem h)) j hy        have hy_ne_max : x ≠ @Finset.max' Object (succ a) rem h := by          intro h_eq          subst h_eq          exact (Finset.mem_erase.mp hy_rem).1 rfl        rcases hx with rfl | hx'        · exact hy_ne_max rfl        · have hx'' : x ∈ draft_alloc succ rest (rem.erase (@Finset.max' Object (succ a) rem h)) i := by            cases hia; exact hx'          have hd := ih (rem := rem.erase (@Finset.max' Object (succ a) rem h)) hij          exact Finset.disjoint_iff_ne.mp hd x hx'' x hy rfl      · by_cases hja : j = a        · have h1 : (i = a) = False := by simp [hia]          have h2 : (j = a) = True := by simp [hja]          simp only [Function.update_apply, h1, ite_false] at hx          simp only [Function.update_apply, h2, ite_true, Finset.mem_insert] at hy          have hx_rem := two_agent_welfare_regret_nonneg_draft_alloc_subset succ rest            (rem.erase (@Finset.max' Object (succ a) rem h)) i hx          have hx_ne_max : x ≠ @Finset.max' Object (succ a) rem h := by            intro h_eq            subst h_eq            exact (Finset.mem_erase.mp hx_rem).1 rfl          rcases hy with rfl | hy'          · exact hx_ne_max rfl          · have hy'' : x ∈ draft_alloc succ rest (rem.erase (@Finset.max' Object (succ a) rem h)) j := by              cases hja; exact hy'            have hd := ih (rem := rem.erase (@Finset.max' Object (succ a) rem h)) hij            exact Finset.disjoint_iff_ne.mp hd x hx x hy'' rfl        · have h1 : (i = a) = False := by simp [hia]          have h2 : (j = a) = False := by simp [hja]          simp only [Function.update_apply, h1, ite_false] at hx          simp only [Function.update_apply, h2, ite_false] at hy          have hd := ih (rem := rem.erase (@Finset.max' Object (succ a) rem h)) hij          exact Finset.disjoint_iff_ne.mp hd x hx x hy rfl    · simp only      exact Finset.disjoint_empty_left _/-- Utilitarian welfare regret in two-agent sincere drafting is nonnegative for nonnegative valuations. -/theorem two_agent_welfare_regret_nonneg (m : ℕ) (s : Fin m → Fin 2) (v : Fin 2 → Fin m → ℝ)    (hv : ∀ i g, 0 ≤ v i g) :    0 ≤ two_agent_welfare_regret m s v := by  rw [two_agent_welfare_regret, sub_nonneg]  unfold two_agent_draft_welfare two_agent_first_best_welfare  rw [Fin.sum_univ_two]  let succ := fun j => balanced_draft_value_order (v j)  have hd : Disjoint (draft_rule s succ 0) (draft_rule s succ 1) := by    exact two_agent_welfare_regret_nonneg_draft_alloc_disjoint succ (List.ofFn s) Finset.univ (by decide)  have h0 : (∑ g ∈ draft_rule s succ 0, v 0 g) ≤ ∑ g ∈ draft_rule s succ 0, max (v 0 g) (v 1 g) := by    apply Finset.sum_le_sum    intro g _    exact le_max_left (v 0 g) (v 1 g)  have h1 : (∑ g ∈ draft_rule s succ 1, v 1 g) ≤ ∑ g ∈ draft_rule s succ 1, max (v 0 g) (v 1 g) := by    apply Finset.sum_le_sum    intro g _    exact le_max_right (v 0 g) (v 1 g)  have h_union : (∑ g ∈ draft_rule s succ 0, max (v 0 g) (v 1 g)) +      (∑ g ∈ draft_rule s succ 1, max (v 0 g) (v 1 g)) =      ∑ g ∈ draft_rule s succ 0 ∪ draft_rule s succ 1, max (v 0 g) (v 1 g) := by    rw [Finset.sum_union hd]  have h_sub : (∑ g ∈ draft_rule s succ 0 ∪ draft_rule s succ 1, max (v 0 g) (v 1 g)) ≤      ∑ g : Fin m, max (v 0 g) (v 1 g) := by    apply Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ _)    intro g _ _    exact le_trans (hv 0 g) (le_max_left (v 0 g) (v 1 g))  linarith
See it in the graphDiscuss this resultChallenge it