maxcut_fair9_graph
def
The explicit nine-vertex simple graph used to obstruct fair Nash selection.
Statement
def maxcut_fair9_graph : SimpleGraph (Fin 9)- 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
- Used by 8
- maxcut_fair9_stable_exampleA specified three-color profile is a strong equilibrium of the nine-vertex graph.
- 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…
- maxcut_fair9_not_three_colorableThe specified nine-vertex fairness-obstruction graph does not admit a proper coloring with three colors.
- maxcut_fair9_witnessA specified three-color profile on the nine-vertex graph has utility at least four for every vertex and admits no profitable singleton…
- maxcut_fair9_no_maxmin_strong_nashOn the specified nine-vertex graph, no strong equilibrium has minimum utility at least that of every singleton-stable three-coloring.
- maxcut_fair9_normalized_certificatesFor every three-color profile on the nine-vertex graph whose first vertex has color zero, if all utilities are at least four and no…
- maxcut_fair9_deviationThe target profile is a strong deviation from the source profile using exactly the vertices whose colors change.
- maxcut_fair9_no_strong_with_min_fourNo strong equilibrium of the nine-vertex graph with three colors gives every vertex utility at least four.
Lean source view module on GitHub
def maxcut_fair9_graph : SimpleGraph (Fin 9) := SimpleGraph.fromRel (fun (u v : Fin 9) => (u.val, v.val) ∈ [(0,1),(0,2),(0,3),(0,5),(0,7),(1,3),(1,6),(1,7),(1,8), (2,3),(2,6),(2,7),(2,8),(3,4),(3,5),(3,6),(3,8), (4,5),(4,7),(4,8),(5,6),(5,7),(5,8),(6,7),(7,8)])