maxcut_fair9_no_strong_with_min_four
No strong equilibrium of the nine-vertex graph with three colors gives every vertex utility at least four.
Statement
theorem maxcut_fair9_no_strong_with_min_four : ∀ σ : Fin 9 → Fin 3,
(∀ v : Fin 9, 4 ≤ maxcut_utility maxcut_fair9_graph σ v) →
¬ is_maxcut_strong_equilibrium maxcut_fair9_graph σ- 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 10
- 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_fair9_targetsSix explicit three-color profiles used as finite deviation targets.
- maxcut_fair9_deviationThe target profile is a strong deviation from the source profile using exactly the vertices whose colors change.
- 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_strong_equilibrium_color_permutationA global permutation of colors maps a strong equilibrium to a strong equilibrium.
- maxcut_utility_color_permutationPermuting all color labels preserves every player’s utility in the Max-k-Cut game.
- 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…
- is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
- maxcut_utilityIn the unweighted Max-k-Cut game on a finite simple graph G, a coloring σ : V → [k] gives player v the utility u_v(σ) = |{w ∈ N(v) : σ(w)…
- Used by 2
- 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_no_maxmin_strong_nashOn the specified nine-vertex graph, no strong equilibrium has minimum utility at least that of every singleton-stable three-coloring.
The proof, explained
The proof proceeds by contradiction. Assuming there is a strong equilibrium where every vertex has utility at least 4, we permute colors so that vertex 0 is colored 0, which preserves both the strong equilibrium property and vertex utilities. Because this normalized coloring is a strong equilibrium, it is in particular a Nash equilibrium resistant to single-vertex deviations. We then invoke a precomputed certificate theorem, maxcut_fair9_normalized_certificates, which establishes that every such normalized coloring admits a profitable coalitional deviation from a finite list of targets, yielding a contradiction.
Graph adjacency and coalitional deviation relations are decidable. automation
By unfolding the definitions of the graph, utility, and deviations into finite set and cardinality conditions, Lean's typeclass synthesis automatically constructs decidability instances for adjacency and deviation predicates.
private instance : DecidableRel maxcut_fair9_graph.Adj := by unfold maxcut_fair9_graph SimpleGraph.fromRel infer_instance private instance (σ τ : Fin 9 → Fin 3) (S : Finset (Fin 9)) : Decidable (is_maxcut_strong_deviation maxcut_fair9_graph σ S τ) := by unfold is_maxcut_strong_deviation maxcut_utility infer_instance private instance (σ τ : Fin 9 → Fin 3) : Decidable (maxcut_fair9_deviation σ τ) := by unfold maxcut_fair9_deviation is_maxcut_strong_deviation maxcut_utility infer_instance
Assuming a counterexample exists, color normalization yields a strong equilibrium ρ where vertex 0 has color 0 and every vertex still has utility at least 4.
Suppose for contradiction that σ is a strong equilibrium where every vertex achieves utility at least 4. By applying the transposition swapping σ(0) with 0 across all vertices, we obtain a coloring ρ with ρ(0) = 0. Because permuting colors preserves strong equilibria (by maxcut_strong_equilibrium_color_permutation) and preserves vertex utilities (by maxcut_utility_color_permutation), ρ is also a strong equilibrium with minimum utility at least 4.
uses
maxcut_strong_equilibrium_color_permutation,maxcut_utility_color_permutationintro σ hmin hstable let p : Equiv.Perm (Fin 3) := Equiv.swap (σ 0) 0 let ρ : Fin 9 → Fin 3 := fun v => p (σ v) have h0 : ρ 0 = 0 := by simp [ρ, p] have hρstable : is_maxcut_strong_equilibrium maxcut_fair9_graph ρ := maxcut_strong_equilibrium_color_permutation maxcut_fair9_graph σ p hstable have hρmin : ∀ v, 4 ≤ maxcut_utility maxcut_fair9_graph ρ v := by intro v simpa [ρ, maxcut_utility_color_permutation] using hmin v
The coloring ρ is a Nash equilibrium: no single vertex can improve its utility by changing color.
Since ρ is a strong equilibrium, it is immune to deviations by any coalition, and in particular to deviations by any singleton coalition {v} switching to a new color q.
have hρnash : ∀ v q, ¬ is_maxcut_strong_deviation maxcut_fair9_graph ρ {v} (Function.update ρ v q) := by intro v q exact hρstable {v} (Function.update ρ v q)
The coloring ρ equals the canonical 8-parameter representation maxcut_fair9_colors applied to its values on vertices 1 through 8.
By function extensionality, we verify equality on each vertex. Vertex 0 has color 0, matching the fixed first entry of maxcut_fair9_colors, and vertices 1 through 8 match by definition.
have hvec : ρ = maxcut_fair9_colors (ρ 1) (ρ 2) (ρ 3) (ρ 4) (ρ 5) (ρ 6) (ρ 7) (ρ 8) := by funext v fin_cases v <;> simp [maxcut_fair9_colors, h0]
A certified strong deviation from ρ exists in the precomputed targets, contradicting that ρ is a strong equilibrium.
The precomputed lemma maxcut_fair9_normalized_certificates asserts that any normalized coloring satisfying the minimum utility of 4 and the Nash property admits a certified deviation in maxcut_fair9_targets. Rewriting with the canonical representation of ρ and supplying the utility and Nash hypotheses yields such a target τ via List.any_eq_true.mp. Converting the boolean decision to a proposition using of_decide_eq_true exhibits a profitable strong deviation from ρ, contradicting that ρ is a strong equilibrium.
uses
maxcut_fair9_normalized_certificates,List.any_eq_true.mp,of_decide_eq_truehave hc := maxcut_fair9_normalized_certificates (ρ 1) (ρ 2) (ρ 3) (ρ 4) (ρ 5) (ρ 6) (ρ 7) (ρ 8) rw [← hvec] at hc have ht := hc hρmin hρnash obtain ⟨τ, _, hτ⟩ := List.any_eq_true.mp ht have hdev : maxcut_fair9_deviation ρ τ := of_decide_eq_true hτ exact hρstable _ τ hdev
maxcut_strong_equilibrium_color_permutation- Permuting the colors of a coloring preserves the property of being a strong equilibrium.
maxcut_utility_color_permutation- Permuting colors does not change the utility of any vertex.
maxcut_fair9_normalized_certificates- For any 3-coloring with vertex 0 assigned color 0 that has minimum utility at least 4 and no profitable single-vertex deviation, at least one candidate coloring in the target list is a valid strong deviation.
List.any_eq_true.mp- If a boolean predicate evaluates to true for some element of a list, then there exists an element in the list satisfying the predicate.
of_decide_eq_true- If the decision procedure for a decidable proposition returns true, then the proposition is true.
- Decidability instances on lines 4–14 are computational plumbing that enable Lean to evaluate coalitional deviations mechanically.
- The exhaustive search over all normalized colorings is handled by the precomputed lemma `maxcut_fair9_normalized_certificates`.
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_instanceprivate instance (σ τ : Fin 9 → Fin 3) (S : Finset (Fin 9)) : Decidable (is_maxcut_strong_deviation maxcut_fair9_graph σ S τ) := by unfold is_maxcut_strong_deviation maxcut_utility infer_instanceprivate instance (σ τ : Fin 9 → Fin 3) : Decidable (maxcut_fair9_deviation σ τ) := by unfold maxcut_fair9_deviation is_maxcut_strong_deviation maxcut_utility infer_instancetheorem maxcut_fair9_no_strong_with_min_four : ∀ σ : Fin 9 → Fin 3, (∀ v : Fin 9, 4 ≤ maxcut_utility maxcut_fair9_graph σ v) → ¬ is_maxcut_strong_equilibrium maxcut_fair9_graph σ := by intro σ hmin hstable let p : Equiv.Perm (Fin 3) := Equiv.swap (σ 0) 0 let ρ : Fin 9 → Fin 3 := fun v => p (σ v) have h0 : ρ 0 = 0 := by simp [ρ, p] have hρstable : is_maxcut_strong_equilibrium maxcut_fair9_graph ρ := maxcut_strong_equilibrium_color_permutation maxcut_fair9_graph σ p hstable have hρmin : ∀ v, 4 ≤ maxcut_utility maxcut_fair9_graph ρ v := by intro v simpa [ρ, maxcut_utility_color_permutation] using hmin v have hρnash : ∀ v q, ¬ is_maxcut_strong_deviation maxcut_fair9_graph ρ {v} (Function.update ρ v q) := by intro v q exact hρstable {v} (Function.update ρ v q) have hvec : ρ = maxcut_fair9_colors (ρ 1) (ρ 2) (ρ 3) (ρ 4) (ρ 5) (ρ 6) (ρ 7) (ρ 8) := by funext v fin_cases v <;> simp [maxcut_fair9_colors, h0] have hc := maxcut_fair9_normalized_certificates (ρ 1) (ρ 2) (ρ 3) (ρ 4) (ρ 5) (ρ 6) (ρ 7) (ρ 8) rw [← hvec] at hc have ht := hc hρmin hρnash obtain ⟨τ, _, hτ⟩ := List.any_eq_true.mp ht have hdev : maxcut_fair9_deviation ρ τ := of_decide_eq_true hτ exact hρstable _ τ hdev