AFTD Auto-Formalizing Theoretical Domains

maxcut_fair9_deviation

def

The target profile is a strong deviation from the source profile using exactly the vertices whose colors change.

Statement

def maxcut_fair9_deviation (σ τ : Fin 9 → Fin 3) : Prop
Source
Related work: arXiv:2610.04948, Section 4, asks whether all unweighted Max-k-Cut games have a strong equilibrium; this finite obstruction to selecting a fair Nash equilibrium was discovered in experiment 12959 and independently checked in 12961, 12964 and 12973.
Verified
02 Nov 2026
Axioms
none listed
Built on 2
  • maxcut_fair9_graphThe explicit nine-vertex simple graph used to obstruct fair Nash selection.
  • 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 2

Lean source view module on GitHub

private instance : DecidableRel maxcut_fair9_graph.Adj := by
  unfold maxcut_fair9_graph SimpleGraph.fromRel
  infer_instance

def maxcut_fair9_deviation (σ τ : Fin 9 → Fin 3) : Prop :=
  is_maxcut_strong_deviation maxcut_fair9_graph σ
    (Finset.univ.filter fun v => τ v ≠ σ v) τ
See it in the graphDiscuss this resultChallenge it