finite_two_bonus_assignment
For any finite nonempty real matrix w and two nonnegative agent-dependent bonus values g(false), g(true), there is a permutation of the old columns and an assignment of each bonus to one recipient which weakly improves every original diagonal, and for either bonus, removing that bonus from its recipient column leaves no foreign agent envying that column relative to her final utility. Recipients may coincide, and the Boolean records which bonus is assigned first.
Statement
theorem finite_two_bonus_assignment {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] (w : α → α → ℝ) (g : Bool → α → ℝ) (hg : ∀ t i, 0 ≤ g t i) : ∃ (p : Equiv.Perm α) (r s : α) (t : Bool), (∀ i, w i i ≤ w i (p i) + (if i = r then g t i else 0) + (if i = s then g (!t) i else 0)) ∧ (∀ i, i ≠ r → w i (p r) + (if r = s then g (!t) i else 0) ≤ w i (p i) + (if i = r then g t i else 0) + (if i = s then g (!t) i else 0)) ∧ (∀ i, i ≠ s → w i (p s) + (if s = r then g t i else 0) ≤ w i (p i) + (if i = r then g t i else 0) + (if i = s then g (!t) i else 0))
- 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 3
- 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…
- finite_unenvied_permutationEvery finite nonempty matrix of real bundle values admits a permutation that weakly improves each diagonal value and has an unenvied…
- finite_column_switch_improvementIn a finite nonempty real matrix w, suppose each column other than s is strictly envied relative to diagonal values, and some agent other…
- Used by 1
- finite_two_bonus_ordered_assignmentFor any finite nonempty real matrix w and two nonnegative agent-dependent bonuses a and b, there is a permutation of the old columns, a…
The proof, explained
The proof proceeds by contradiction using an extremal potential-function argument. We consider the finite set of configurations consisting of a column permutation, an initial bonus recipient, and the order in which the two bonuses are assigned, subject to the condition that every agent's diagonal utility weakly improves upon their initial diagonal and no agent envies the recipient's column stripped of its bonus. Choosing a feasible configuration that maximizes the total sum of utilities, no Pareto improvement is possible. If neither that configuration with a distinct unenvied column nor that configuration with both bonuses assigned to the recipient solves the problem, then envy-cycle and column-switching lemmas yield a Pareto-improving permutation, contradicting maximality.
Define the configuration space X, the utility matrix U, the feasibility predicate F, and the permutation update operation.
We consider configurations $x = (p, r, t) \in X = \mathrm{Perm}(\alpha) \times \alpha \times \mathrm{Bool}$, where $p$ is a column permutation, $r$ is the recipient of the first bonus, and $t$ records whether bonus $g(\mathrm{true})$ or $g(\mathrm{false})$ is assigned first. The utility of agent $i$ for column $j$ is $U(x)(i, j) = w(i, p(j)) + [j = r] g(t)(i)$. A configuration is feasible, $F(x)$, if every agent weakly improves upon their original diagonal ($w(i, i) \le U(x)(i, i)$) and no agent envies column $r$ stripped of its bonus ($w(i, p(r)) \le U(x)(i, i)$). For a permutation $q$, updating $x$ by $q$ and bonus flag $t'$ yields $\mathrm{upd}(x, q, t') = (p \circ q, q^{-1}(r), t')$. The identity `hbase` checks that $(p \circ q)(q^{-1}(r)) = p(r)$, so updating does not change the recipient's underlying column.
classical let X := Equiv.Perm α × α × Bool let U (x : X) (i j : α) : ℝ := w i (x.1 j) + if j = x.2.1 then g x.2.2 i else 0 let F (x : X) : Prop := (∀ i, w i i ≤ U x i i) ∧ ∀ i, w i (x.1 x.2.1) ≤ U x i i let upd (x : X) (q : Equiv.Perm α) (t : Bool) : X := ⟨q.trans x.1, q.symm x.2.1, t⟩ have hbase (x : X) (q : Equiv.Perm α) (t : Bool) : (upd x q t).1 (upd x q t).2.1 = x.1 x.2.1 := by simp [upd]
Compute the utilities under updated configurations, showing column permutation when the bonus flag is held fixed and diagonal modification when flipped.
The lemma `hU` computes $U(\mathrm{upd}(x, q, t))(i, j) = w(i, p(q(j))) + [q(j) = r] g(t)(i)$ using the equivalence $j = q^{-1}(r) \iff q(j) = r$. When the bonus flag is preserved ($t = x.2.2$), `hsU` shows $U(\mathrm{upd}(x, q, t))(i, j) = U(x)(i, q(j))$, which permutes the columns of $U(x)$. When the flag is inverted ($t = \neg x.2.2$), `hcU` computes the new diagonal utilities: if $q(i) = r$, agent $i$ receives $w(i, p(r)) + g(\neg t)(i)$, and otherwise receives $U(x)(i, q(i))$.
uses
Equiv.trans_applyhave hU (x : X) (q : Equiv.Perm α) (t : Bool) (i j : α) : U (upd x q t) i j = w i (x.1 (q j)) + if q j = x.2.1 then g t i else 0 := by have he : (j = q.symm x.2.1) ↔ q j = x.2.1 := by constructor · intro h rw [h, q.apply_symm_apply] · intro h rw [← h, q.symm_apply_apply] simp only [U, upd, Equiv.trans_apply, he] have hsU (x : X) (q : Equiv.Perm α) (i j : α) : U (upd x q x.2.2) i j = U x i (q j) := by rw [hU] have hcU (x : X) (q : Equiv.Perm α) (i : α) : U (upd x q (!x.2.2)) i i = if q i = x.2.1 then w i (x.1 x.2.1) + g (!x.2.2) i else U x i (q i) := by rw [hU] by_cases hi : q i = x.2.1 <;> simp [U, hi]
Pareto-improving updates preserve feasibility.
The lemma `hF` shows that if $x$ is feasible and an update $\mathrm{upd}(x, q, t)$ weakly increases every agent's diagonal utility ($U(x)(i, i) \le U(\mathrm{upd}(x, q, t))(i, i)$), then the updated configuration is also feasible. This holds because $w(i, i) \le U(x)(i, i) \le U(\mathrm{upd}(x, q, t))(i, i)$, and by `hbase`, the stripped recipient column satisfies $w(i, p(r)) \le U(x)(i, i) \le U(\mathrm{upd}(x, q, t))(i, i)$.
have hF (x : X) (q : Equiv.Perm α) (t : Bool) (hx : F x) (hinc : ∀ i, U x i i ≤ U (upd x q t) i i) : F (upd x q t) := by refine ⟨fun i => (hx.1 i).trans (hinc i), ?_⟩ intro i rw [hbase] exact (hx.2 i).trans (hinc i)
Formulate the target condition C(x, s) and establish sufficiency criteria when recipients are distinct or identical.
Let $V(x, s, i) = U(x)(i, i) + [i = s] g(\neg t)(i)$ be agent $i$'s final utility after awarding the remaining bonus $g(\neg t)$ to recipient $s$. Since bonuses are nonnegative (`hg`), $U(x)(i, i) \le V(x, s, i)$ (`hV`). The predicate $C(x, s)$ asserts that all original diagonals weakly improve and that removing bonus $t$ from column $r$ or bonus $\neg t$ from column $s$ leaves no other agent envying that column relative to $V$. We prove two sufficiency lemmas: 1. `hdistinct`: If $s \ne r$ and column $s$ is unenvied under $U(x)$ ($\forall i, U(x)(i, s) \le U(x)(i, i)$), then $C(x, s)$ holds. Column $r$ without bonus $t$ is unenvied by feasibility $F(x)$, and column $s$ without bonus $\neg t$ is unenvied because its valuation is $w(i, p(s)) = U(x)(i, s) \le U(x)(i, i) \le V(x, s, i)$. 2. `hsame`: If both bonuses go to $r$ ($s = r$), column $r$ with bonus $t$ is unenvied under $U(x)$, and column $r$ with bonus $\neg t$ is not envied by any $i \ne r$ relative to $U(x)(i, i)$, then $C(x, r)$ holds.
uses
le_add_of_nonneg_right,le_rfl,if_neg,add_zero,ite_truelet V (x : X) (s i : α) := U x i i + if i = s then g (!x.2.2) i else 0 let C (x : X) (s : α) : Prop := (∀ i, w i i ≤ V x s i) ∧ (∀ i, i ≠ x.2.1 → w i (x.1 x.2.1) + (if x.2.1 = s then g (!x.2.2) i else 0) ≤ V x s i) ∧ (∀ i, i ≠ s → w i (x.1 s) + (if s = x.2.1 then g x.2.2 i else 0) ≤ V x s i) have hV (x : X) (s i : α) : U x i i ≤ V x s i := by dsimp [V] apply le_add_of_nonneg_right split_ifs · exact hg _ _ · exact le_rfl have hdistinct (x : X) (hx : F x) (s : α) (hs : s ≠ x.2.1) (hsource : ∀ i, U x i s ≤ U x i i) : C x s := by refine ⟨fun i => (hx.1 i).trans (hV x s i), ?_, ?_⟩ · intro i hi simp only [if_neg hs.symm, add_zero] exact (hx.2 i).trans (hV x s i) · intro i hi simp only [if_neg hs, add_zero] have he : U x i s = w i (x.1 s) := by simp [U, hs] rw [← he] exact (hsource i).trans (hV x s i) have hsame (x : X) (hx : F x) (hsource : ∀ i, U x i x.2.1 ≤ U x i i) (hnew : ∀ i, i ≠ x.2.1 → w i (x.1 x.2.1) + g (!x.2.2) i ≤ U x i i) : C x x.2.1 := by refine ⟨fun i => (hx.1 i).trans (hV x x.2.1 i), ?_, ?_⟩ · intro i hi simp only [ite_true] exact (hnew i hi).trans (hV x x.2.1 i) · intro i hi simp only [ite_true] have he : U x i x.2.1 = w i (x.1 x.2.1) + g x.2.2 i := by simp [U] rw [← he] exact (hsource i).trans (hV x x.2.1 i)
Reduce the theorem to finding a pair (x, s) satisfying C(x, s), and assume for contradiction that no such pair exists.
Any pair $(x, s)$ satisfying $C(x, s)$ immediately provides a witness $(p, r, s, t) = (x.1, x.2.1, s, x.2.2)$ solving the theorem. We assume for contradiction that no such pair exists, obtaining `hn : ∀ x s, ¬ C x s`.
suffices hex : ∃ (x : X) (s : α), C x s by obtain ⟨x, s, hx⟩ := hex exact ⟨x.1, x.2.1, s, x.2.2, hx⟩ by_contra hnone have hn (x : X) (s : α) : ¬ C x s := fun h => hnone ⟨x, s, h⟩ let S : Finset X := Finset.univ.filter F
The set S of feasible configurations is nonempty and contains a configuration maximizing total diagonal utility.
By `finite_unenvied_permutation`, there is a permutation $p$ weakly improving the diagonal entries and leaving some column $s$ unenvied. Setting $x = (p, s, \mathrm{false})$ gives a feasible configuration $F(x)$, so the set $S = \{x \in X \mid F(x)\}$ is nonempty (`hS`). Since $X$ is finite, `Finset.exists_max_image` yields a configuration $x \in S$ that maximizes the social welfare $\sum_i U(x)(i, i)$.
uses
finite_unenvied_permutation,le_add_of_nonneg_right,le_rfl,Finset.exists_max_image,Finset.mem_filter.mphave hS : S.Nonempty := by obtain ⟨p, hp, s, hs⟩ := finite_unenvied_permutation w let x : X := ⟨p, s, false⟩ have hge (i : α) : w i (p i) ≤ U x i i := by dsimp [U, x] apply le_add_of_nonneg_right split_ifs · exact hg _ _ · exact le_rfl have hx : F x := ⟨fun i => (hp i).trans (hge i), fun i => (hs i).trans (hge i)⟩ exact ⟨x, by simp [S, hx]⟩ obtain ⟨x, hxS, hmax⟩ := Finset.exists_max_image S (fun x => ∑ i, U x i i) hS have hx : F x := (Finset.mem_filter.mp hxS).2
The maximal configuration admits no Pareto-improving update, and in particular no Pareto-improving column permutation under the current bonus.
We prove `noimp`: if any update $\mathrm{upd}(x, q, t)$ weakly increases all diagonal utilities and strictly increases at least one, then by `hF` it belongs to $S$, and by `Finset.sum_lt_sum` its total utility is strictly greater than that of $x$, contradicting the maximality of $x$ via `not_lt_of_ge`. In particular, taking $t = x.2.2$, `noold` shows that no permutation $q$ of the columns can Pareto-improve the current utilities $U(x)(i, i)$.
uses
Finset.sum_lt_sum,Finset.mem_univ,not_lt_of_gehave noimp (q : Equiv.Perm α) (t : Bool) (hinc : ∀ i, U x i i ≤ U (upd x q t) i i) (hlt : ∃ i, U x i i < U (upd x q t) i i) : False := by have hy := hF x q t hx hinc have htot : (∑ i, U x i i) < ∑ i, U (upd x q t) i i := Finset.sum_lt_sum (fun i _ => hinc i) (by obtain ⟨i, hi⟩ := hlt; exact ⟨i, Finset.mem_univ _, hi⟩) exact (not_lt_of_ge (hmax _ (by simp [S, hy]))) htot have noold (q : Equiv.Perm α) (hinc : ∀ i, U x i i ≤ U x i (q i)) (hlt : ∃ i, U x i i < U x i (q i)) : False := by apply noimp q x.2.2 · simpa only [hsU] using hinc · simpa only [hsU] using hlt
Every non-recipient column is strictly envied, the recipient column is unenvied, and the alternative bonus on the recipient column is strictly envied by some other agent.
At the utility maximizer $x$: 1. `hother`: For every column $j \ne r$, some agent strictly envies $j$ ($U(x)(i, i) < U(x)(i, j)$); otherwise $j$ would be unenvied, and `hdistinct` would give $C(x, j)$, contradicting `hn`. 2. `hsource`: The recipient column $r$ is unenvied ($\forall i, U(x)(i, r) \le U(x)(i, i)$). Indeed, if $r$ were envied, every column would be strictly envied, and `finite_envy_cycle_improvement` would find an envy cycle yielding a Pareto-improving permutation, contradicting `noold`. 3. `hnew`: Some agent $i \ne r$ strictly envies column $r$ with the alternative bonus $\neg t$ ($U(x)(i, i) < w(i, p(r)) + g(\neg t)(i)$); otherwise column $r$ with bonus $\neg t$ would not be envied by any other agent, and together with `hsource`, `hsame` would give $C(x, r)$, contradicting `hn`.
uses
finite_envy_cycle_improvementhave hother (j : α) (hj : j ≠ x.2.1) : ∃ i, U x i i < U x i j := by by_contra h push Not at h exact hn x j (hdistinct x hx j hj h) have hsource : ∀ i, U x i x.2.1 ≤ U x i i := by by_contra h push Not at h have hall (j : α) : ∃ i, U x i i < U x i j := by by_cases hj : j = x.2.1 · simpa only [hj] using h · exact hother j hj obtain ⟨q, hq, i, hi⟩ := finite_envy_cycle_improvement (U x) hall exact noold q hq ⟨i, hi⟩ have hnew : ∃ i, i ≠ x.2.1 ∧ U x i i < w i (x.1 x.2.1) + g (!x.2.2) i := by by_contra h push Not at h exact hn x x.2.1 (hsame x hx hsource h)
Applying the column-switch improvement theorem produces a Pareto improvement, concluding the contradiction.
We apply `finite_column_switch_improvement` to matrix $U(x)$, column $r$, and the alternative column $c(i) = w(i, p(r)) + g(\neg t)(i)$. Since all other columns are envied (`hother`) and $c$ is envied by some $i \ne r$ (`hnew`), the lemma yields two possibilities: 1. A Pareto-improving permutation on the original matrix $U(x)$, which contradicts `noold`. 2. A Pareto-improving permutation on the matrix where column $r$ is replaced by $c$. By `hcU`, this corresponds exactly to the diagonal utilities of $\mathrm{upd}(x, q, \neg t)$, which contradicts `noimp`. Both cases are ruled out, completing the proof.
uses
finite_column_switch_improvementobtain hold | hswap := finite_column_switch_improvement (U x) x.2.1 (fun i => w i (x.1 x.2.1) + g (!x.2.2) i) hother hnew · obtain ⟨q, hq, i, hi⟩ := hold exact noold q hq ⟨i, hi⟩ · obtain ⟨q, hq, i, hi⟩ := hswap apply noimp q (!x.2.2) · simpa only [hcU] using hq · exact ⟨i, by simpa only [hcU] using hi⟩
Equiv.trans_apply- The composition of equivalences `f.trans g` applies `f` and then `g`, so `(f.trans g) a = g (f a)`.
le_add_of_nonneg_right- Adding a nonnegative quantity to a number yields a value greater than or equal to the original number (`0 ≤ b → a ≤ a + b`).
le_rfl- Any element is less than or equal to itself (`a ≤ a`).
if_neg- If a proposition `c` is false, the conditional `if c then t else e` evaluates to `e`.
add_zero- Adding zero to any number leaves it unchanged (`a + 0 = a`).
ite_true- If the condition is True, `if True then a else b` reduces to `a`.
finite_unenvied_permutation- For any finite matrix, there exists a permutation weakly improving all diagonal entries such that some column is envied by no agent over their assigned column.
Finset.exists_max_image- Any nonempty finite set contains an element that maximizes a given real-valued function.
Finset.mem_filter.mp- An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies property `p`.
Finset.sum_lt_sum- If one function is pointwise weakly bounded by another on a finite set and strictly smaller at at least one element, its sum is strictly smaller.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
not_lt_of_ge- If `a ≤ b`, then `b < a` cannot hold.
finite_envy_cycle_improvement- If every column of a matrix is strictly envied by some agent over their diagonal, then there is a permutation that weakly improves all diagonals and strictly improves at least one.
finite_column_switch_improvement- If every column other than `s` is strictly envied and an alternative column `c` is envied by some agent other than `s`, then either the original matrix or the matrix with column `s` replaced by `c` admits a Pareto-improving permutation.
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_two_bonus_assignment {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] (w : α → α → ℝ) (g : Bool → α → ℝ) (hg : ∀ t i, 0 ≤ g t i) : ∃ (p : Equiv.Perm α) (r s : α) (t : Bool), (∀ i, w i i ≤ w i (p i) + (if i = r then g t i else 0) + (if i = s then g (!t) i else 0)) ∧ (∀ i, i ≠ r → w i (p r) + (if r = s then g (!t) i else 0) ≤ w i (p i) + (if i = r then g t i else 0) + (if i = s then g (!t) i else 0)) ∧ (∀ i, i ≠ s → w i (p s) + (if s = r then g t i else 0) ≤ w i (p i) + (if i = r then g t i else 0) + (if i = s then g (!t) i else 0)) := by classical let X := Equiv.Perm α × α × Bool let U (x : X) (i j : α) : ℝ := w i (x.1 j) + if j = x.2.1 then g x.2.2 i else 0 let F (x : X) : Prop := (∀ i, w i i ≤ U x i i) ∧ ∀ i, w i (x.1 x.2.1) ≤ U x i i let upd (x : X) (q : Equiv.Perm α) (t : Bool) : X := ⟨q.trans x.1, q.symm x.2.1, t⟩ have hbase (x : X) (q : Equiv.Perm α) (t : Bool) : (upd x q t).1 (upd x q t).2.1 = x.1 x.2.1 := by simp [upd] have hU (x : X) (q : Equiv.Perm α) (t : Bool) (i j : α) : U (upd x q t) i j = w i (x.1 (q j)) + if q j = x.2.1 then g t i else 0 := by have he : (j = q.symm x.2.1) ↔ q j = x.2.1 := by constructor · intro h rw [h, q.apply_symm_apply] · intro h rw [← h, q.symm_apply_apply] simp only [U, upd, Equiv.trans_apply, he] have hsU (x : X) (q : Equiv.Perm α) (i j : α) : U (upd x q x.2.2) i j = U x i (q j) := by rw [hU] have hcU (x : X) (q : Equiv.Perm α) (i : α) : U (upd x q (!x.2.2)) i i = if q i = x.2.1 then w i (x.1 x.2.1) + g (!x.2.2) i else U x i (q i) := by rw [hU] by_cases hi : q i = x.2.1 <;> simp [U, hi] have hF (x : X) (q : Equiv.Perm α) (t : Bool) (hx : F x) (hinc : ∀ i, U x i i ≤ U (upd x q t) i i) : F (upd x q t) := by refine ⟨fun i => (hx.1 i).trans (hinc i), ?_⟩ intro i rw [hbase] exact (hx.2 i).trans (hinc i) let V (x : X) (s i : α) := U x i i + if i = s then g (!x.2.2) i else 0 let C (x : X) (s : α) : Prop := (∀ i, w i i ≤ V x s i) ∧ (∀ i, i ≠ x.2.1 → w i (x.1 x.2.1) + (if x.2.1 = s then g (!x.2.2) i else 0) ≤ V x s i) ∧ (∀ i, i ≠ s → w i (x.1 s) + (if s = x.2.1 then g x.2.2 i else 0) ≤ V x s i) have hV (x : X) (s i : α) : U x i i ≤ V x s i := by dsimp [V] apply le_add_of_nonneg_right split_ifs · exact hg _ _ · exact le_rfl have hdistinct (x : X) (hx : F x) (s : α) (hs : s ≠ x.2.1) (hsource : ∀ i, U x i s ≤ U x i i) : C x s := by refine ⟨fun i => (hx.1 i).trans (hV x s i), ?_, ?_⟩ · intro i hi simp only [if_neg hs.symm, add_zero] exact (hx.2 i).trans (hV x s i) · intro i hi simp only [if_neg hs, add_zero] have he : U x i s = w i (x.1 s) := by simp [U, hs] rw [← he] exact (hsource i).trans (hV x s i) have hsame (x : X) (hx : F x) (hsource : ∀ i, U x i x.2.1 ≤ U x i i) (hnew : ∀ i, i ≠ x.2.1 → w i (x.1 x.2.1) + g (!x.2.2) i ≤ U x i i) : C x x.2.1 := by refine ⟨fun i => (hx.1 i).trans (hV x x.2.1 i), ?_, ?_⟩ · intro i hi simp only [ite_true] exact (hnew i hi).trans (hV x x.2.1 i) · intro i hi simp only [ite_true] have he : U x i x.2.1 = w i (x.1 x.2.1) + g x.2.2 i := by simp [U] rw [← he] exact (hsource i).trans (hV x x.2.1 i) suffices hex : ∃ (x : X) (s : α), C x s by obtain ⟨x, s, hx⟩ := hex exact ⟨x.1, x.2.1, s, x.2.2, hx⟩ by_contra hnone have hn (x : X) (s : α) : ¬ C x s := fun h => hnone ⟨x, s, h⟩ let S : Finset X := Finset.univ.filter F have hS : S.Nonempty := by obtain ⟨p, hp, s, hs⟩ := finite_unenvied_permutation w let x : X := ⟨p, s, false⟩ have hge (i : α) : w i (p i) ≤ U x i i := by dsimp [U, x] apply le_add_of_nonneg_right split_ifs · exact hg _ _ · exact le_rfl have hx : F x := ⟨fun i => (hp i).trans (hge i), fun i => (hs i).trans (hge i)⟩ exact ⟨x, by simp [S, hx]⟩ obtain ⟨x, hxS, hmax⟩ := Finset.exists_max_image S (fun x => ∑ i, U x i i) hS have hx : F x := (Finset.mem_filter.mp hxS).2 have noimp (q : Equiv.Perm α) (t : Bool) (hinc : ∀ i, U x i i ≤ U (upd x q t) i i) (hlt : ∃ i, U x i i < U (upd x q t) i i) : False := by have hy := hF x q t hx hinc have htot : (∑ i, U x i i) < ∑ i, U (upd x q t) i i := Finset.sum_lt_sum (fun i _ => hinc i) (by obtain ⟨i, hi⟩ := hlt; exact ⟨i, Finset.mem_univ _, hi⟩) exact (not_lt_of_ge (hmax _ (by simp [S, hy]))) htot have noold (q : Equiv.Perm α) (hinc : ∀ i, U x i i ≤ U x i (q i)) (hlt : ∃ i, U x i i < U x i (q i)) : False := by apply noimp q x.2.2 · simpa only [hsU] using hinc · simpa only [hsU] using hlt have hother (j : α) (hj : j ≠ x.2.1) : ∃ i, U x i i < U x i j := by by_contra h push Not at h exact hn x j (hdistinct x hx j hj h) have hsource : ∀ i, U x i x.2.1 ≤ U x i i := by by_contra h push Not at h have hall (j : α) : ∃ i, U x i i < U x i j := by by_cases hj : j = x.2.1 · simpa only [hj] using h · exact hother j hj obtain ⟨q, hq, i, hi⟩ := finite_envy_cycle_improvement (U x) hall exact noold q hq ⟨i, hi⟩ have hnew : ∃ i, i ≠ x.2.1 ∧ U x i i < w i (x.1 x.2.1) + g (!x.2.2) i := by by_contra h push Not at h exact hn x x.2.1 (hsame x hx hsource h) obtain hold | hswap := finite_column_switch_improvement (U x) x.2.1 (fun i => w i (x.1 x.2.1) + g (!x.2.2) i) hother hnew · obtain ⟨q, hq, i, hi⟩ := hold exact noold q hq ⟨i, hi⟩ · obtain ⟨q, hq, i, hi⟩ := hswap apply noimp q (!x.2.2) · simpa only [hcU] using hq · exact ⟨i, by simpa only [hcU] using hi⟩