AFTD Auto-Formalizing Theoretical Domains

maxcut_fair9_no_maxmin_strong_nash

theoremverified

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.

  1. 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.

    lines 2–3

      unfold maxcut_fair9_graph SimpleGraph.fromRel
      infer_instance
  2. 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.

    line 12

      rintro ⟨σ, hσ, h⟩
  3. 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σ).

    lines 13–15

    uses maxcut_fair9_no_strong_with_min_four, maxcut_fair9_witness.2, maxcut_fair9_witness.1

      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σ
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.

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

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σ
See it in the graphDiscuss this resultChallenge it