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
- 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_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
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) τ