maxcut_defect_two_nash_to_nash_equal_cut_escape
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.
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.
uses
maxcut_defect_two_nash_escape_graphdsimp [maxcut_defect_two_nash_escape_graph] infer_instance
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.
uses
is_maxcut_strong_deviationdsimp [is_maxcut_strong_deviation] infer_instance
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.
uses
Subsingleton.elim,maxcut_defect_two_nash_to_nash_equal_cut_escape_adjrename_i inst have : inst = maxcut_defect_two_nash_to_nash_equal_cut_escape_adj := Subsingleton.elim _ _ subst this
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.
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
- The entire combinatorial verification is carried out by the computational decision procedure `decide`, so the individual evaluations (defect counts, single-player deviations, coalitional utility gains, and total welfare) are not expanded into separate deduction steps.
- Replacing the arbitrary `DecidableRel` instance with `maxcut_defect_two_nash_to_nash_equal_cut_escape_adj` via `Subsingleton.elim` is a technical necessity to allow `decide` to compute, as kernel evaluation requires transparent, computable 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.
@[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