AFTD Auto-Formalizing Theoretical Domains

is_maxcut_strong_equilibrium

def

A coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.

Statement

def is_maxcut_strong_equilibrium {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) : Prop
Defined in
arXiv:2610.04948 (Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games), Sec. 1
Verified
06 Oct 2026
Axioms
none listed
Built on 1
  • 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…
Used by 39

Lean source view module on GitHub

/-- A strong equilibrium of the Max-k-Cut game: a coloring admitting no strong deviation. -/
def is_maxcut_strong_equilibrium {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) : Prop :=
  ∀ (S : Finset V) (τ : V → Fin k), ¬ is_maxcut_strong_deviation G σ S τ
See it in the graphDiscuss this resultChallenge it