AFTD Auto-Formalizing Theoretical Domains

maxcut_strong_deviation_carrier

theoremverified

Every strong deviation contains a carrier deviation: the subset of players who actually change color forms a valid strong deviation.

Statement

theorem maxcut_strong_deviation_carrier {V : Type} [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ τ : V → Fin k) (S : Finset V)
    (hdev : is_maxcut_strong_deviation G σ S τ) :
    is_maxcut_strong_deviation G σ (Finset.univ.filter fun v => τ v ≠ σ v) τ
Source
step towards maxcut_game_strong_equilibrium_exists
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_maxcut_strong_deviationA strong deviation from σ is a nonempty coalition S ⊆ V with a coloring τ agreeing with σ outside S such that u_v(τ) > u_v(σ) for every v…
  • maxcut_utilityIn the unweighted Max-k-Cut game on a finite simple graph G, a coloring σ : V → [k] gives player v the utility u_v(σ) = |{w ∈ N(v) : σ(w)…
Used by 2

The proof, explained

To prove that the carrier set of players who actually change color forms a valid strong deviation, the proof verifies the three defining conditions of a strong deviation. First, any player who changes color must belong to the original deviation set S, so every member of the carrier set inherits a strict utility increase from S. Second, the carrier set cannot be empty, because if no player changed color, the strategy profile would remain unchanged, contradicting the strict utility gain guaranteed for members of the nonempty set S. Finally, by construction, players outside the carrier set do not change color.

  1. Extract the three components of the strong deviation hypothesis for S.

    By definition, the hypothesis that S forms a strong deviation from σ to τ provides three facts: S is nonempty (`hne`), players outside S do not change strategy (`hout`, so τ v = σ v for all v ∉ S), and every player in S strictly increases their utility (`hgain`).

    lines 6–7

      classical
      obtain ⟨hne, hout, hgain⟩ := hdev
  2. Any player whose color changes must belong to S.

    Suppose for contradiction that a player v satisfies τ v ≠ σ v but does not belong to S. By `hout`, every player outside S must satisfy τ v = σ v, directly contradicting τ v ≠ σ v.

    lines 8–11

      have hsub : ∀ v, τ v ≠ σ v → v ∈ S := by
        intro v hv
        by_contra hn
        exact hv (hout v hn)
  3. At least one player changes color between σ and τ.

    Assume for contradiction that no player changes color. Then τ v = σ v for every vertex v, which by function extensionality means τ = σ. But S is nonempty, so we can pick some v ∈ S. By `hgain`, v strictly improves its utility from σ to τ; substituting τ = σ would mean the utility of v under σ is strictly less than itself, which is impossible.

    lines 12–17

    uses not_exists.mp

      have hdiff : ∃ v, τ v ≠ σ v := by
        by_contra h
        have heq : τ = σ := funext fun v => by simpa using not_exists.mp h v
        obtain ⟨v, hv⟩ := hne
        have := hgain v hv
        simpa [heq] using this
  4. The carrier set of players who change color is nonempty.

    We split the goal of showing that the carrier set {v | τ v ≠ σ v} is a strong deviation into its three defining conditions. For the first condition, the witness produced in the previous step guarantees that the carrier set has at least one element.

    lines 18–20

      refine ⟨?_, ?_, ?_⟩
      · obtain ⟨v, hv⟩ := hdiff
        exact ⟨v, by simp [hv]⟩
  5. Players outside the carrier set do not change color.

    If a vertex v is not in {w | τ w ≠ σ w}, then the negation ¬(τ v ≠ σ v) holds, which simplifies directly to τ v = σ v.

    lines 21–22

      · intro v hv
        simpa using hv
  6. Every player in the carrier set strictly increases their utility.

    Let v be in the carrier set, so τ v ≠ σ v. By the earlier lemma that any vertex with changed color belongs to S, v must belong to S. Therefore, the utility gain condition for S applies, showing that v strictly improves its utility from σ to τ.

    lines 23–24

    uses Finset.mem_filter.mp

      · intro v hv
        exact hgain v (hsub v (Finset.mem_filter.mp hv).2)
not_exists.mp
If there does not exist an element satisfying a predicate, then every element satisfies the negation of that predicate.
Finset.mem_filter.mp
An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies `p`.

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

/-- Every strong deviation contains a carrier deviation: the subset of players who actually change color forms a valid strong deviation. -/theorem maxcut_strong_deviation_carrier {V : Type} [Fintype V]    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ τ : V → Fin k) (S : Finset V)    (hdev : is_maxcut_strong_deviation G σ S τ) :    is_maxcut_strong_deviation G σ (Finset.univ.filter fun v => τ v ≠ σ v) τ := by  classical  obtain ⟨hne, hout, hgain⟩ := hdev  have hsub : ∀ v, τ v ≠ σ v → v ∈ S := by    intro v hv    by_contra hn    exact hv (hout v hn)  have hdiff : ∃ v, τ v ≠ σ v := by    by_contra h    have heq : τ = σ := funext fun v => by simpa using not_exists.mp h v    obtain ⟨v, hv⟩ := hne    have := hgain v hv    simpa [heq] using this  refine ⟨?_, ?_, ?_⟩  · obtain ⟨v, hv⟩ := hdiff    exact ⟨v, by simp [hv]⟩  · intro v hv    simpa using hv  · intro v hv    exact hgain v (hsub v (Finset.mem_filter.mp hv).2)
See it in the graphDiscuss this resultChallenge it