AFTD Auto-Formalizing Theoretical Domains

is_maxcut_strong_deviation

def

A 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 ∈ S. (The paper also asks every member to change color; it notes this is without loss of generality, and the resulting notion of strong equilibrium is the same.)

Statement

def is_maxcut_strong_deviation {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (S : Finset V) (τ : V → Fin k) : Prop
Defined in
arXiv:2610.04948 (Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games), Sec. 1; the Lean version does not require every member to change color, which the paper notes is without loss of generality
Verified
06 Oct 2026
Axioms
none listed
Built on 1
  • 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 50

Lean source view module on GitHub

/-- A strong deviation from `σ` in the Max-k-Cut game: a nonempty coalition `S` and a coloring `τ` that agrees with `σ` outside `S` and strictly raises the utility of every member of `S`. -/
def is_maxcut_strong_deviation {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (S : Finset V) (τ : V → Fin k) : Prop :=
  S.Nonempty ∧ (∀ v, v ∉ S → τ v = σ v) ∧
    ∀ v ∈ S, maxcut_utility G σ v < maxcut_utility G τ v
See it in the graphDiscuss this resultChallenge it