AFTD Auto-Formalizing Theoretical Domains

maxcut_fair9_stable_example

theoremverified

A specified three-color profile is a strong equilibrium of the nine-vertex graph.

Statement

theorem maxcut_fair9_stable_example :
    is_maxcut_strong_equilibrium maxcut_fair9_graph (maxcut_fair9_colors 1 1 2 0 1 0 2 0)
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
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • maxcut_fair9_graphThe explicit nine-vertex simple graph used to obstruct fair Nash selection.
  • maxcut_fair9_colorsThe nine-vertex three-color profile whose first color is zero and whose remaining colors are specified by eight arguments.
  • maxcut_strong_equilibrium_of_ranked_neighborsA coloring is a strong equilibrium if, for every alternative color at each vertex, the earlier-ranked neighbors of that color number at…
  • is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
Used by 1

The proof, explained

Testing steps range.

  1. Decidability of adjacency in the 9-vertex graph

    Unfolding the graph definition and deriving decidability.

    lines 5–6

      unfold maxcut_fair9_graph SimpleGraph.fromRel
      infer_instance
  2. Reduction to neighborhood inequality

    Using ranked neighbors criterion.

    lines 10–11

      apply maxcut_strong_equilibrium_of_ranked_neighbors maxcut_fair9_graph _
        (fun v => if v.val = 4 ∨ v.val = 8 then 1 else 0)
  3. Verification by computation automation

    decide +kernel checks the finite condition.

    line 12

      decide +kernel

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

set_option maxRecDepth 200000set_option maxHeartbeats 0set_option synthInstance.maxSize 200000private instance : DecidableRel maxcut_fair9_graph.Adj := by  unfold maxcut_fair9_graph SimpleGraph.fromRel  infer_instancetheorem maxcut_fair9_stable_example :    is_maxcut_strong_equilibrium maxcut_fair9_graph (maxcut_fair9_colors 1 1 2 0 1 0 2 0) := by  apply maxcut_strong_equilibrium_of_ranked_neighbors maxcut_fair9_graph _    (fun v => if v.val = 4 ∨ v.val = 8 then 1 else 0)  decide +kernel
See it in the graphDiscuss this resultChallenge it