maxcut_fair9_no_maxmin_strong_nash
On the specified nine-vertex graph, no strong equilibrium has minimum utility at least that of every singleton-stable three-coloring.
Statement
theorem maxcut_fair9_no_maxmin_strong_nash :
¬ ∃ σ : Fin 9 → Fin 3,
is_maxcut_strong_equilibrium maxcut_fair9_graph σ ∧
∀ τ : Fin 9 → Fin 3,
(∀ v : Fin 9, ∀ q : Fin 3, ¬ is_maxcut_strong_deviation maxcut_fair9_graph τ {v} (Function.update τ v q)) →
∀ m : ℕ, (∀ v : Fin 9, m ≤ maxcut_utility maxcut_fair9_graph τ v) →
(∀ v : Fin 9, m ≤ maxcut_utility maxcut_fair9_graph σ v)- Source
- A consequence of the nine-vertex finite obstruction to max-min Nash selection in the OP-85 campaign, related to arXiv:2610.04948, Section 4.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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_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_strong_with_min_fourNo strong equilibrium of the nine-vertex graph with three colors gives every vertex utility at least four.
- 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)…
- is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
- 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…
The proof, explained
We argue by contradiction. Suppose there exists a strong equilibrium 3-coloring σ whose minimum vertex utility is at least that of every singleton-stable 3-coloring. We evaluate this condition on an explicit witness coloring, which is known to be singleton-stable and to give every vertex utility at least 4. This forces every vertex under σ to have utility at least 4, which contradicts an established theorem that no strong equilibrium on this graph has minimum utility at least 4.
Adjacency in maxcut_fair9_graph is decidable.
Unfolding the definitions of maxcut_fair9_graph and SimpleGraph.fromRel reveals that adjacency is given by membership in an explicit list of vertex pairs. Typeclass inference automatically synthesizes the decidability of this relation.
unfold maxcut_fair9_graph SimpleGraph.fromRel infer_instance
Assume for contradiction that there exists a strong equilibrium σ whose minimum vertex utility is at least that of every singleton-stable 3-coloring.
We introduce the assumed coloring σ, the hypothesis (hσ) that σ is a strong equilibrium, and the hypothesis (h) that whenever τ is a singleton-stable coloring with minimum utility at least m, every vertex under σ also receives utility at least m.
rintro ⟨σ, hσ, h⟩
A contradiction is derived from the impossibility of any strong equilibrium achieving minimum utility 4.
We instantiate the max-min hypothesis (h) using the explicit witness coloring maxcut_fair9_colors 1 2 2 1 2 1 0 0 and threshold m = 4. By maxcut_fair9_witness.2, this witness coloring is singleton-stable, and by maxcut_fair9_witness.1, every vertex achieves utility at least 4. Applying h implies that every vertex under σ must achieve utility at least 4. But maxcut_fair9_no_strong_with_min_four states that no strong equilibrium on this graph can have minimum utility at least 4, contradicting that σ is a strong equilibrium (hσ).
uses
maxcut_fair9_no_strong_with_min_four,maxcut_fair9_witness.2,maxcut_fair9_witness.1exact maxcut_fair9_no_strong_with_min_four σ (h (maxcut_fair9_colors 1 2 2 1 2 1 0 0) maxcut_fair9_witness.2 4 maxcut_fair9_witness.1) hσ
maxcut_fair9_no_strong_with_min_four- On maxcut_fair9_graph, no 3-coloring in which every vertex achieves utility at least 4 can be a strong equilibrium.
maxcut_fair9_witness.1- Under the explicit witness coloring, every vertex achieves utility at least 4.
maxcut_fair9_witness.2- The explicit witness coloring is singleton-stable: no individual vertex can strictly increase its utility by unilaterally changing its color.
- Lines 1–3 define a private typeclass instance establishing the decidability of graph adjacency, which is required formally by the Max-Cut game definitions.
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.
private instance : DecidableRel maxcut_fair9_graph.Adj := by unfold maxcut_fair9_graph SimpleGraph.fromRel infer_instancetheorem maxcut_fair9_no_maxmin_strong_nash : ¬ ∃ σ : Fin 9 → Fin 3, is_maxcut_strong_equilibrium maxcut_fair9_graph σ ∧ ∀ τ : Fin 9 → Fin 3, (∀ v : Fin 9, ∀ q : Fin 3, ¬ is_maxcut_strong_deviation maxcut_fair9_graph τ {v} (Function.update τ v q)) → ∀ m : ℕ, (∀ v : Fin 9, m ≤ maxcut_utility maxcut_fair9_graph τ v) → (∀ v : Fin 9, m ≤ maxcut_utility maxcut_fair9_graph σ v) := by rintro ⟨σ, hσ, h⟩ exact maxcut_fair9_no_strong_with_min_four σ (h (maxcut_fair9_colors 1 2 2 1 2 1 0 0) maxcut_fair9_witness.2 4 maxcut_fair9_witness.1) hσ