AFTD Auto-Formalizing Theoretical Domains

maxcut_fair9_nash_fairness_obstruction

theoremverifiedoriginal

On the specified nine-vertex three-color graph there is a singleton-stable profile with every utility at least four, no strong equilibrium has every utility at least four, and a strong equilibrium exists.

Statement

theorem maxcut_fair9_nash_fairness_obstruction :
    (∃ σ : Fin 9 → Fin 3,
      (∀ v : Fin 9, 4 ≤ maxcut_utility maxcut_fair9_graph σ v) ∧
      (∀ v : Fin 9, ∀ q : Fin 3, ¬ is_maxcut_strong_deviation maxcut_fair9_graph σ {v} (Function.update σ v q))) ∧
    (∀ σ : Fin 9 → Fin 3, (∀ v : Fin 9, 4 ≤ maxcut_utility maxcut_fair9_graph σ v) →
      ¬ is_maxcut_strong_equilibrium maxcut_fair9_graph σ) ∧
    ∃ σ : Fin 9 → Fin 3, is_maxcut_strong_equilibrium maxcut_fair9_graph σ
Related work
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 8
  • 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_fair9_stable_exampleA specified three-color profile is a strong equilibrium of the nine-vertex graph.
  • 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…
  • 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)…

Read back from the Lean

The declaration asserts the conjunction of three statements regarding 3-colorings (or 3-partition strategy profiles) $\sigma : \text{Fin } 9 \to \text{Fin } 3$ on the graph maxcut_fair9_graph (a specific 9-vertex simple graph with 25 edges): 1. **Existence of a "fair" Nash equilibrium**: There exists a coloring $\sigma : \text{Fin } 9 \to \text{Fin } 3$ such that: - every vertex $v \in \text{Fin } 9$ has cut utility at least 4 (i.e., at least 4 neighbors have a color different from $\sigma(v)$), and - $\sigma$ is a Nash equilibrium under unilateral deviations: for every vertex $v \in \text{Fin } 9$ and every color $q \in \text{Fin } 3$, the single-vertex deviation $\{v\}$ updating $v$ to $q$ does not strictly increase $v$'s cut utility. 2. **Fairness-strong equilibrium obstruction**: For every coloring $\sigma : \text{Fin } 9 \to \text{Fin } 3$, if every vertex $v \in \text{Fin } 9$ has cut utility at least 4, then $\sigma$ is not a strong equilibrium (that is, there exists a nonempty coalition $S \subseteq \text{Fin } 9$ and an alternate coloring $\tau$ agreeing with $\sigma$ outside $S$ such that every vertex in $S$ strictly increases its cut utility). 3. **Existence of a strong equilibrium**: There exists at least one coloring $\sigma : \text{Fin } 9 \to \text{Fin } 3$ that is a strong equilibrium (no nonempty coalition can deviate such that all its members strictly increase their cut utility).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem shows that in a specific 9-vertex 3-color Max-Cut game, high fairness (every vertex receiving utility at least four) is compatible with singleton stability (Nash equilibrium) but mutually exclusive with strong stability (immunity to coalitional deviations), even though a strong equilibrium exists. The proof directly combines three lemmas: it witnesses a fair singleton-stable coloring with maxcut_fair9_witness, proves the impossibility of a fair strong equilibrium with maxcut_fair9_no_strong_with_min_four, and provides an explicit strong equilibrium via maxcut_fair9_stable_example.

  1. The adjacency relation of maxcut_fair9_graph is decidable.

    Unfolding the definitions of maxcut_fair9_graph and SimpleGraph.fromRel exposes adjacency as membership in an explicit finite list of 25 vertex pairs (modulo symmetry and irreflexivity). Lean's typeclass resolution automatically derives decidability for this finite check on Fin 9 via infer_instance.

    lines 5–6

      unfold maxcut_fair9_graph SimpleGraph.fromRel
      infer_instance
  2. There exists a singleton-stable coloring with every vertex receiving utility at least 4, and no coloring achieving utility at least 4 everywhere is a strong equilibrium.

    The proof instantiates the first existential statement with the coloring maxcut_fair9_colors 1 2 2 1 2 1 0 0, whose fairness (utility at least 4) and immunity to single-vertex deviations are established by maxcut_fair9_witness. It discharges the second conjunct using maxcut_fair9_no_strong_with_min_four, leaving the existence of a strong equilibrium as the remaining goal.

    lines 15–16

    uses maxcut_fair9_witness, maxcut_fair9_no_strong_with_min_four

      refine ⟨⟨maxcut_fair9_colors 1 2 2 1 2 1 0 0, maxcut_fair9_witness⟩,
        maxcut_fair9_no_strong_with_min_four, ?_⟩
  3. A strong equilibrium exists for the 9-vertex Max-Cut game.

    The remaining goal is witnessed by the coloring maxcut_fair9_colors 1 1 2 0 1 0 2 0, which is certified to be coalition-proof by maxcut_fair9_stable_example.

    line 17

    uses maxcut_fair9_stable_example

      exact ⟨maxcut_fair9_colors 1 1 2 0 1 0 2 0, maxcut_fair9_stable_example⟩
maxcut_fair9_witness
For the coloring assigning colors (0, 1, 2, 2, 1, 2, 1, 0, 0) to the nine vertices, every vertex achieves utility at least 4, and no single vertex can strictly improve its utility by unilaterally changing its color.
maxcut_fair9_no_strong_with_min_four
In the 9-vertex graph, any 3-coloring where every vertex achieves utility at least 4 admits a profitable coalitional deviation, and thus cannot be a strong equilibrium.
maxcut_fair9_stable_example
The coloring assigning colors (0, 1, 1, 2, 0, 1, 0, 2, 0) to the nine vertices is a strong equilibrium of the 3-color Max-Cut game on the graph.

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

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_instancetheorem maxcut_fair9_nash_fairness_obstruction :    (∃ σ : Fin 9 → Fin 3,      (∀ v : Fin 9, 4 ≤ maxcut_utility maxcut_fair9_graph σ v) ∧      (∀ v : Fin 9, ∀ q : Fin 3, ¬ is_maxcut_strong_deviation maxcut_fair9_graph σ {v} (Function.update σ v q))) ∧    (∀ σ : Fin 9 → Fin 3, (∀ v : Fin 9, 4 ≤ maxcut_utility maxcut_fair9_graph σ v) →      ¬ is_maxcut_strong_equilibrium maxcut_fair9_graph σ) ∧    ∃ σ : Fin 9 → Fin 3, is_maxcut_strong_equilibrium maxcut_fair9_graph σ := by  refine ⟨⟨maxcut_fair9_colors 1 2 2 1 2 1 0 0, maxcut_fair9_witness⟩,    maxcut_fair9_no_strong_with_min_four, ?_⟩  exact ⟨maxcut_fair9_colors 1 1 2 0 1 0 2 0, maxcut_fair9_stable_example⟩
See it in the graphDiscuss this resultChallenge it