finite_column_switch_improvement
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.
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.
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]
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).
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
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.
uses
finite_envy_cycle_improvementobtain ⟨p, hp, k, hk⟩ := finite_envy_cycle_improvement v heIf 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.
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⟩
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.
· 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
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 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⟩