AFTD Auto-Formalizing Theoretical Domains

finite_column_switch_improvement

theoremverified

In a finite nonempty real matrix w, suppose each column other than s is strictly envied relative to diagonal values, and some agent other than s strictly prefers replacement value c(i) to her diagonal. Then either a permutation of the original columns or a permutation after replacing column s by c weakly improves all diagonal values and strictly improves one.

Statement

theorem finite_column_switch_improvement {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α]
    (w : α → α → ℝ) (s : α) (c : α → ℝ)
    (hother : ∀ j, j ≠ s → ∃ i, w i i < w i j)
    (hc : ∃ i, i ≠ s ∧ w i i < c i) :
    (∃ p : Equiv.Perm α, (∀ i, w i i ≤ w i (p i)) ∧ ∃ i, w i i < w i (p i)) ∨
    (∃ p : Equiv.Perm α,
      (∀ i, w i i ≤ if p i = s then c i else w i (p i)) ∧
        ∃ i, w i i < if p i = s then c i else w i (p i))
Source
Structural helper for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • finite_envy_cycle_improvementFor a finite nonempty matrix of real bundle values, if every bundle is strictly envied by an agent relative to her own bundle, some bundle…
Used by 1
  • finite_two_bonus_assignmentFor any finite nonempty real matrix w and two nonnegative agent-dependent bonus values g(false), g(true), there is a permutation of the…

The proof, explained

We define an auxiliary valuation matrix v that agrees with w on row s and on all entries outside column s, but replaces column s with the alternative values c(i) for agents i ≠ s. Because v shares the diagonal of w and satisfies the envy condition in every column (column s by hypothesis hc and all other columns by hother), the lemma finite_envy_cycle_improvement yields an improving permutation p on v. Depending on whether p fixes s, p either improves w directly or improves w after replacing column s with c.

  1. Define an auxiliary matrix v and show that its diagonal matches that of w: v(i, i) = w(i, i) for all i.

    We define v(i, j) to be w(i, j) if i = s, c(i) if j = s (and i ≠ s), and w(i, j) otherwise. On the diagonal j = i, if i = s then v(s, s) = w(s, s), and if i ≠ s then neither condition applies, so v(i, i) = w(i, i) as well.

    lines 11–13

      classical
      let v : α → α → ℝ := fun i j => if i = s then w i j else if j = s then c i else w i j
      have hd (i : α) : v i i = w i i := by by_cases hi : i = s <;> simp [v, hi]
  2. Every column of v is strictly envied by some agent relative to their diagonal: for every j, there exists i such that v(i, i) < v(i, j).

    We consider whether j = s. If j = s, the hypothesis hc provides an agent i ≠ s with w(i, i) < c(i); since i ≠ s and j = s, v(i, s) = c(i), giving v(i, i) < v(i, s). If j ≠ s, the hypothesis hother provides an agent i with w(i, i) < w(i, j); since j ≠ s, v(i, j) = w(i, j) regardless of whether i = s or not, so v(i, i) < v(i, j).

    lines 14–20

      have he (j : α) : ∃ i, v i i < v i j := by
        by_cases hj : j = s
        · obtain ⟨i, hi, hic⟩ := hc
          exact ⟨i, by simpa [hd, v, hi, hj] using hic⟩
        · obtain ⟨i, hi⟩ := hother j hj
          refine ⟨i, ?_⟩
          by_cases his : i = s <;> simpa [hd, v, his, hj] using hi
  3. There exists a permutation p such that v(i, i) ≤ v(i, p(i)) for all i, with a strict improvement v(k, k) < v(k, p(k)) for some agent k.

    Because every column in the finite nonempty matrix v is strictly envied, the cycle-improvement theorem finite_envy_cycle_improvement yields a permutation p that weakly improves all diagonal values and strictly improves at least one agent k.

    line 21

    uses finite_envy_cycle_improvement

      obtain ⟨p, hp, k, hk⟩ := finite_envy_cycle_improvement v he
  4. If p(s) = s, then p weakly improves all diagonal values in w and strictly improves agent k's diagonal value.

    Assume p(s) = s. Since p is injective, no other agent maps to s (p(i) ≠ s whenever i ≠ s). Therefore, v(i, p(i)) = w(i, p(i)) for every i: when i = s this holds because p(s) = s, and when i ≠ s this holds because p(i) ≠ s. Together with v(i, i) = w(i, i), the inequalities for v translate directly into the first alternative of the disjunction for w.

    lines 22–30

      by_cases hps : p s = s
      · left
        have hv (i : α) : v i (p i) = w i (p i) := by
          by_cases hi : i = s
          · simp [v, hi]
          · have hpi : p i ≠ s := fun h => hi (p.injective (h.trans hps.symm))
            simp [v, hi, hpi]
        exact ⟨p, fun i => by simpa only [hd, hv] using hp i,
          k, by simpa only [hd, hv] using hk⟩
  5. If p(s) ≠ s, then p weakly improves all diagonal values after replacing column s by c and strictly improves agent k's diagonal value.

    Assume p(s) ≠ s. For any agent i, if p(i) = s, then i ≠ s (since p(s) ≠ s), so v(i, p(i)) = c(i). If p(i) ≠ s, then v(i, p(i)) = w(i, p(i)) whether i = s or not. Hence, v(i, p(i)) equals the conditional expression (if p(i) = s then c(i) else w(i, p(i))). Since v(i, i) = w(i, i), the inequalities for v establish the second alternative of the disjunction.

    lines 31–38

      · right
        have hv (i : α) : v i (p i) = if p i = s then c i else w i (p i) := by
          by_cases hi : i = s
          · subst i
            simp [v, hps]
          · simp [v, hi]
        exact ⟨p, fun i => by simpa only [hd, hv] using hp i,
          k, by simpa only [hd, hv] using hk⟩
finite_envy_cycle_improvement
In a finite nonempty type with a valuation matrix, if every column is strictly envied by some agent relative to her diagonal value, then there exists a permutation that weakly improves every agent's diagonal value and strictly improves at least one.

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 Function Finsettheorem finite_column_switch_improvement {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α]    (w : α → α → ℝ) (s : α) (c : α → ℝ)    (hother : ∀ j, j ≠ s → ∃ i, w i i < w i j)    (hc : ∃ i, i ≠ s ∧ w i i < c i) :    (∃ p : Equiv.Perm α, (∀ i, w i i ≤ w i (p i)) ∧ ∃ i, w i i < w i (p i)) ∨    (∃ p : Equiv.Perm α,      (∀ i, w i i ≤ if p i = s then c i else w i (p i)) ∧        ∃ i, w i i < if p i = s then c i else w i (p i)) := by  classical  let v : α → α → ℝ := fun i j => if i = s then w i j else if j = s then c i else w i j  have hd (i : α) : v i i = w i i := by by_cases hi : i = s <;> simp [v, hi]  have he (j : α) : ∃ i, v i i < v i j := by    by_cases hj : j = s    · obtain ⟨i, hi, hic⟩ := hc      exact ⟨i, by simpa [hd, v, hi, hj] using hic⟩    · obtain ⟨i, hi⟩ := hother j hj      refine ⟨i, ?_⟩      by_cases his : i = s <;> simpa [hd, v, his, hj] using hi  obtain ⟨p, hp, k, hk⟩ := finite_envy_cycle_improvement v he  by_cases hps : p s = s  · left    have hv (i : α) : v i (p i) = w i (p i) := by      by_cases hi : i = s      · simp [v, hi]      · have hpi : p i ≠ s := fun h => hi (p.injective (h.trans hps.symm))        simp [v, hi, hpi]    exact ⟨p, fun i => by simpa only [hd, hv] using hp i,      k, by simpa only [hd, hv] using hk⟩  · right    have hv (i : α) : v i (p i) = if p i = s then c i else w i (p i) := by      by_cases hi : i = s      · subst i        simp [v, hps]      · simp [v, hi]    exact ⟨p, fun i => by simpa only [hd, hv] using hp i,      k, by simpa only [hd, hv] using hk⟩
See it in the graphDiscuss this resultChallenge it