AFTD Auto-Formalizing Theoretical Domains

maxcut_strong_equilibrium_color_permutation

theoremverified

A global permutation of colors maps a strong equilibrium to a strong equilibrium.

Statement

theorem maxcut_strong_equilibrium_color_permutation {V : Type} [Fintype V] (G : SimpleGraph V)
    [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (p : Equiv.Perm (Fin k))
    (h : is_maxcut_strong_equilibrium G σ) :
    is_maxcut_strong_equilibrium G (fun v => p (σ v))
Source
Structural reduction for OP-85, the strong-equilibrium existence problem; the two-piece gluing step is maxcut_single_vertex_sum_strong_equilibrium.
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • maxcut_utility_color_permutationPermuting all color labels preserves every player’s utility in the Max-k-Cut game.
  • is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
  • 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

Suppose for contradiction that the permuted coloring $p \circ \sigma$ is not a strong equilibrium, so some coalition $S$ has a profitable deviation $\tau$. By pulling $\tau$ back through the inverse permutation $p^{-1}$, coalition $S$ would also have a profitable deviation $p^{-1} \circ \tau$ from the original coloring $\sigma$. Because Max-Cut utility depends solely on whether adjacent vertices have different colors, it is invariant under color permutations, ensuring that the utility gains under $\tau$ over $p \circ \sigma$ match those under $p^{-1} \circ \tau$ over $\sigma$. This shows that $p^{-1} \circ \tau$ is a valid strong deviation from $\sigma$, contradicting the assumption that $\sigma$ is a strong equilibrium.

  1. To derive a contradiction, it suffices to show that the pulled-back coloring $p^{-1} \circ \tau$ is a strong deviation from $\sigma$ for coalition $S$, which reduces to showing that $p^{-1} \circ \tau$ agrees with $\sigma$ outside $S$ and strictly increases utility on $S$.

    We assume for contradiction that the permuted coloring $p \circ \sigma$ admits a strong deviation $\tau$ by a coalition $S$ (line 5). Since $\sigma$ is assumed to be a strong equilibrium, applying this hypothesis to $S$ and the pulled-back strategy $p^{-1} \circ \tau$ leaves the goal of proving that $(S, p^{-1} \circ \tau)$ would be a strong deviation from $\sigma$ (line 6). Because $S$ is already known to be nonempty from the deviation $\tau$, this requirement decomposes into two obligations: verifying that vertices outside $S$ keep their original colors, and that vertices in $S$ strictly improve their utility (line 7).

    lines 5–7

      intro S τ hd
      apply h S (fun v => p.symm (τ v))
      refine ⟨hd.1, ?_, ?_⟩
  2. For every vertex $v \notin S$, the pulled-back coloring satisfies $(p^{-1} \circ \tau)(v) = \sigma(v)$.

    Let $v \notin S$ (line 8). We need to show that $p^{-1}(\tau(v)) = \sigma(v)$ (line 9). Because $\tau$ is a deviation on $S$, it does not alter vertices outside $S$, meaning $\tau(v) = p(\sigma(v))$ (line 10). Applying $p^{-1}$ to both sides then yields $p^{-1}(p(\sigma(v))) = \sigma(v)$ by `p.symm_apply_apply` (line 11).

    lines 8–11

    uses p.symm_apply_apply

      · intro v hv
        change p.symm (τ v) = σ v
        rw [hd.2.1 v hv]
        exact p.symm_apply_apply (σ v)
  3. For every vertex $v \in S$, the utility under $p^{-1} \circ \tau$ is strictly greater than under $\sigma$.

    Let $v \in S$ (line 12). By assumption that $\tau$ is a profitable deviation from $p \circ \sigma$, the utility of $v$ strictly increases: $\text{maxcut\_utility}(G, p \circ \sigma, v) < \text{maxcut\_utility}(G, \tau, v)$ (line 13). By `maxcut_utility_color_permutation`, permuting the colors of $\sigma$ by $p$ does not change utilities, so $\text{maxcut\_utility}(G, \sigma, v) < \text{maxcut\_utility}(G, \tau, v)$ (line 14). Similarly, applying $p$ to $p^{-1} \circ \tau$ recovers $\tau$ via `Equiv.apply_symm_apply`, which establishes that $\text{maxcut\_utility}(G, \tau, v) = \text{maxcut\_utility}(G, p^{-1} \circ \tau, v)$ (lines 15–16). Rewriting the inequality with this equality yields $\text{maxcut\_utility}(G, \sigma, v) < \text{maxcut\_utility}(G, p^{-1} \circ \tau, v)$ (lines 17–18).

    lines 12–18

    uses maxcut_utility_color_permutation, Equiv.apply_symm_apply

      · intro v hv
        have hg := hd.2.2 v hv
        rw [maxcut_utility_color_permutation G σ p v] at hg
        have heq := maxcut_utility_color_permutation G (fun v => p.symm (τ v)) p v
        simp only [Equiv.apply_symm_apply] at heq
        rw [← heq]
        exact hg
p.symm_apply_apply
Applying a permutation and then its inverse yields the original element: $p^{-1}(p(x)) = x$.
maxcut_utility_color_permutation
The Max-Cut utility of a vertex is invariant under applying a global permutation to the color classes.
Equiv.apply_symm_apply
Applying an equivalence to the result of its inverse yields the original element: $e(e^{-1}(x)) = x$.

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

theorem maxcut_strong_equilibrium_color_permutation {V : Type} [Fintype V] (G : SimpleGraph V)    [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (p : Equiv.Perm (Fin k))    (h : is_maxcut_strong_equilibrium G σ) :    is_maxcut_strong_equilibrium G (fun v => p (σ v)) := by  intro S τ hd  apply h S (fun v => p.symm (τ v))  refine ⟨hd.1, ?_, ?_⟩  · intro v hv    change p.symm (τ v) = σ v    rw [hd.2.1 v hv]    exact p.symm_apply_apply (σ v)  · intro v hv    have hg := hd.2.2 v hv    rw [maxcut_utility_color_permutation G σ p v] at hg    have heq := maxcut_utility_color_permutation G (fun v => p.symm (τ v)) p v    simp only [Equiv.apply_symm_apply] at heq    rw [← heq]    exact hg
See it in the graphDiscuss this resultChallenge it