AFTD Auto-Formalizing Theoretical Domains

finite_two_bonus_assignment

theoremverified

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

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.

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

    lines 12–20

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

    lines 21–36

    uses Equiv.trans_apply

      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]
  3. 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)$.

    lines 37–42

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

    lines 43–78

    uses le_add_of_nonneg_right, le_rfl, if_neg, add_zero, ite_true

      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)
  5. 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`.

    lines 79–84

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

    lines 85–97

    uses finite_unenvied_permutation, le_add_of_nonneg_right, le_rfl, Finset.exists_max_image, Finset.mem_filter.mp

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

    lines 98–109

    uses Finset.sum_lt_sum, Finset.mem_univ, not_lt_of_ge

      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
  8. 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`.

    lines 110–126

    uses finite_envy_cycle_improvement

      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)
  9. 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.

    lines 127–134

    uses finite_column_switch_improvement

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

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