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
- maxcut_fair9_nash_fairness_obstructionOn the specified nine-vertex three-color graph there is a singleton-stable profile with every utility at least four, no strong equilibrium…
The proof, explained
Testing steps range.
Decidability of adjacency in the 9-vertex graph
Unfolding the graph definition and deriving decidability.
unfold maxcut_fair9_graph SimpleGraph.fromRel infer_instance
Reduction to neighborhood inequality
Using ranked neighbors criterion.
apply maxcut_strong_equilibrium_of_ranked_neighbors maxcut_fair9_graph _ (fun v => if v.val = 4 ∨ v.val = 8 then 1 else 0)
Verification by computation automation
decide +kernel checks the finite condition.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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