AFTD Auto-Formalizing Theoretical Domains

maxcut_defect_two_nash_to_nash_equal_cut_escape

theoremverified

A defect-two Nash coloring can strongly deviate at equal welfare to another Nash coloring of defect at least four.

Statement

theorem maxcut_defect_two_nash_to_nash_equal_cut_escape
    [DecidableRel maxcut_defect_two_nash_escape_graph.Adj] :
    (∀ v : Fin 27, (Finset.univ.filter fun w => maxcut_defect_two_nash_escape_graph.Adj v w ∧
      (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) w = (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) v).card ≤ 2) ∧
    (∀ v : Fin 27, ∀ d : Fin 3, ¬ is_maxcut_strong_deviation maxcut_defect_two_nash_escape_graph (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) {v} (Function.update (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) v d)) ∧ (∀ v : Fin 27, ∀ d : Fin 3, ¬ is_maxcut_strong_deviation maxcut_defect_two_nash_escape_graph (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) {v} (Function.update (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) v d)) ∧
    is_maxcut_strong_deviation maxcut_defect_two_nash_escape_graph (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3)
      (Finset.univ.filter fun v : Fin 27 => v.val < 12) (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) ∧
    maxcut_welfare maxcut_defect_two_nash_escape_graph (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) =
      maxcut_welfare maxcut_defect_two_nash_escape_graph (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) ∧
    ∃ v : Fin 27, 4 ≤ (Finset.univ.filter fun w => maxcut_defect_two_nash_escape_graph.Adj v w ∧
      (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) w = (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) v).card
Source
Independent exact checks 16337–16338.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • maxcut_defect_two_nash_escape_graphThe 27-vertex graph for a Nash-to-Nash equal-welfare strong deviation escaping defect two.
  • 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_welfareThe social welfare of a coloring σ in the Max-k-Cut game: the sum over all players v of u_v(σ), equal to twice the cut value.
  • 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)…

The proof, explained

The theorem is proven by constructing a 27-vertex graph and two explicit 3-colorings, then verifying all six claimed properties by finite computation (`decide`). The first coloring σ has defect at most two and is a Nash equilibrium. The coalition of the first twelve vertices strongly deviates to a second coloring τ at identical total cut welfare, which is also a Nash equilibrium but has defect at least four.

  1. Adjacency in the 27-vertex escape graph is computationally decidable.

    Unfolding the definition of `maxcut_defect_two_nash_escape_graph` simplifies graph adjacency to membership of vertex pairs in an explicit list of 60 directed edges. Typeclass synthesis (`infer_instance`) provides the decidability instance for membership in this finite list.

    lines 3–4

    uses maxcut_defect_two_nash_escape_graph

      dsimp [maxcut_defect_two_nash_escape_graph]
      infer_instance
  2. The strong deviation predicate for vertex colorings on the escape graph is computationally decidable.

    Unfolding `is_maxcut_strong_deviation` reduces the predicate to a finite conjunction: the deviating coalition is nonempty, non-deviating vertices retain their color, and every deviating vertex strictly increases its cut utility. Since the vertex set is finite (`Fin 27`) and graph adjacency is decidable, typeclass synthesis (`infer_instance`) produces the decision procedure for all bounded quantifiers and arithmetic comparisons.

    lines 10–11

    uses is_maxcut_strong_deviation

      dsimp [is_maxcut_strong_deviation]
      infer_instance
  3. The abstract decidability hypothesis is replaced by the concrete computable adjacency decider.

    The theorem introduces an arbitrary instance `inst` of `DecidableRel maxcut_defect_two_nash_escape_graph.Adj`. Because `Decidable` propositions are subsingletons, `Subsingleton.elim` proves that `inst` is equal to the concrete definition `maxcut_defect_two_nash_to_nash_equal_cut_escape_adj`. Substituting this equality throughout the goal equips it with the computable decider required for kernel evaluation.

    lines 24–26

    uses Subsingleton.elim, maxcut_defect_two_nash_to_nash_equal_cut_escape_adj

      rename_i inst
      have : inst = maxcut_defect_two_nash_to_nash_equal_cut_escape_adj := Subsingleton.elim _ _
      subst this
  4. All six properties hold: the defect-two Nash coloring strongly deviates at equal welfare to a defect-four Nash coloring. automation

    The decision procedure `decide` evaluates the entire finite combinatorial goal by computation: it verifies that σ has defect at most 2, that neither σ nor τ admits a profitable unilateral deviation (both are Nash equilibria), that the coalition of the first 12 vertices strictly increases cut utility for every member, that the total cut welfare of σ and τ is identical, and that τ has a vertex with defect at least 4.

    line 27

      decide
maxcut_defect_two_nash_escape_graph
the 27-vertex graph defined by an explicit list of edges connecting vertices 0 through 26
is_maxcut_strong_deviation
the predicate stating that a coalition of vertices is nonempty, players outside the coalition do not change strategy, and every player in the coalition strictly increases their cut utility
Subsingleton.elim
in any type with at most one element, any two terms are equal
maxcut_defect_two_nash_to_nash_equal_cut_escape_adj
the explicit, reducible decidability instance for adjacency in the 27-vertex escape 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

@[instance_reducible] def maxcut_defect_two_nash_to_nash_equal_cut_escape_adj :    DecidableRel maxcut_defect_two_nash_escape_graph.Adj := by  dsimp [maxcut_defect_two_nash_escape_graph]  infer_instanceinstance maxcut_defect_two_nash_to_nash_equal_cut_escape_dev    {k : ℕ} (σ : Fin 27 → Fin k) (S : Finset (Fin 27)) (τ : Fin 27 → Fin k) :    Decidable (@is_maxcut_strong_deviation (Fin 27) _ maxcut_defect_two_nash_escape_graph      maxcut_defect_two_nash_to_nash_equal_cut_escape_adj k σ S τ) := by  dsimp [is_maxcut_strong_deviation]  infer_instancetheorem maxcut_defect_two_nash_to_nash_equal_cut_escape    [DecidableRel maxcut_defect_two_nash_escape_graph.Adj] :    (∀ v : Fin 27, (Finset.univ.filter fun w => maxcut_defect_two_nash_escape_graph.Adj v w ∧      (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) w = (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) v).card ≤ 2) ∧    (∀ v : Fin 27, ∀ d : Fin 3, ¬ is_maxcut_strong_deviation maxcut_defect_two_nash_escape_graph (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) {v} (Function.update (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) v d)) ∧ (∀ v : Fin 27, ∀ d : Fin 3, ¬ is_maxcut_strong_deviation maxcut_defect_two_nash_escape_graph (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) {v} (Function.update (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) v d)) ∧    is_maxcut_strong_deviation maxcut_defect_two_nash_escape_graph (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3)      (Finset.univ.filter fun v : Fin 27 => v.val < 12) (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) ∧    maxcut_welfare maxcut_defect_two_nash_escape_graph (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) =      maxcut_welfare maxcut_defect_two_nash_escape_graph (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) ∧    ∃ v : Fin 27, 4 ≤ (Finset.univ.filter fun w => maxcut_defect_two_nash_escape_graph.Adj v w ∧      (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) w = (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2,1,1,2,2,0,0,2,2,0,0,1,1] : Fin 27 → Fin 3) v).card := by  rename_i inst  have : inst = maxcut_defect_two_nash_to_nash_equal_cut_escape_adj := Subsingleton.elim _ _  subst this  decide
See it in the graphDiscuss this resultChallenge it