maxcut_nash_extension_with_profitable_pivot_coalition
theoremverified
A best-responding one-conflict vertex can extend a strong deletion equilibrium to a Nash profile that is not strongly stable. A two-vertex deviation has a neutral deletion pivot and a strictly improving partner.
Statement
theorem maxcut_nash_extension_with_profitable_pivot_coalition : is_maxcut_strong_equilibrium (maxcut_nash_pivot_obstruction_graph.induce (↑(Finset.univ.erase (1 : Fin 6)) : Set (Fin 6))) (fun x : (↑(Finset.univ.erase (1 : Fin 6)) : Set (Fin 6)) => maxcut_nash_pivot_obstruction_start x.1) ∧ (Finset.univ.filter fun w => maxcut_nash_pivot_obstruction_graph.Adj (1 : Fin 6) w ∧ maxcut_nash_pivot_obstruction_start w = maxcut_nash_pivot_obstruction_start 1) = {4} ∧ (∀ x : Fin 6, ∀ c : Fin 3, ¬ is_maxcut_strong_deviation maxcut_nash_pivot_obstruction_graph maxcut_nash_pivot_obstruction_start {x} (Function.update maxcut_nash_pivot_obstruction_start x c)) ∧ (∀ c : Fin 3, c ≠ maxcut_nash_pivot_obstruction_start 4 → ((Finset.univ.erase (1 : Fin 6)).filter fun w => maxcut_nash_pivot_obstruction_graph.Adj 4 w ∧ maxcut_nash_pivot_obstruction_start w = maxcut_nash_pivot_obstruction_start 4).card < ((Finset.univ.erase (1 : Fin 6)).filter fun w => maxcut_nash_pivot_obstruction_graph.Adj 4 w ∧ maxcut_nash_pivot_obstruction_start w = c).card) ∧ is_maxcut_strong_deviation maxcut_nash_pivot_obstruction_graph maxcut_nash_pivot_obstruction_start ({4, 5} : Finset (Fin 6)) maxcut_nash_pivot_obstruction_finish
- Source
- Atlas enumeration in experiment 16715; graph colorings and numerical utility values are printed there.
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- maxcut_nash_pivot_obstruction_graphA six-vertex unweighted graph testing vertex extension under Nash stability.
- maxcut_nash_pivot_obstruction_startThe initial three-color profile for the six-vertex pivot example.
- maxcut_nash_pivot_obstruction_finishThe destination three-color profile for the six-vertex pivot example.
- 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)…
Lean source view module on GitHub
instance : DecidableRel maxcut_nash_pivot_obstruction_graph.Adj := by unfold maxcut_nash_pivot_obstruction_graph infer_instance theorem maxcut_nash_extension_with_profitable_pivot_coalition : is_maxcut_strong_equilibrium (maxcut_nash_pivot_obstruction_graph.induce (↑(Finset.univ.erase (1 : Fin 6)) : Set (Fin 6))) (fun x : (↑(Finset.univ.erase (1 : Fin 6)) : Set (Fin 6)) => maxcut_nash_pivot_obstruction_start x.1) ∧ (Finset.univ.filter fun w => maxcut_nash_pivot_obstruction_graph.Adj (1 : Fin 6) w ∧ maxcut_nash_pivot_obstruction_start w = maxcut_nash_pivot_obstruction_start 1) = {4} ∧ (∀ x : Fin 6, ∀ c : Fin 3, ¬ is_maxcut_strong_deviation maxcut_nash_pivot_obstruction_graph maxcut_nash_pivot_obstruction_start {x} (Function.update maxcut_nash_pivot_obstruction_start x c)) ∧ (∀ c : Fin 3, c ≠ maxcut_nash_pivot_obstruction_start 4 → ((Finset.univ.erase (1 : Fin 6)).filter fun w => maxcut_nash_pivot_obstruction_graph.Adj 4 w ∧ maxcut_nash_pivot_obstruction_start w = maxcut_nash_pivot_obstruction_start 4).card < ((Finset.univ.erase (1 : Fin 6)).filter fun w => maxcut_nash_pivot_obstruction_graph.Adj 4 w ∧ maxcut_nash_pivot_obstruction_start w = c).card) ∧ is_maxcut_strong_deviation maxcut_nash_pivot_obstruction_graph maxcut_nash_pivot_obstruction_start ({4, 5} : Finset (Fin 6)) maxcut_nash_pivot_obstruction_finish := by refine ⟨by dsimp [is_maxcut_strong_equilibrium, is_maxcut_strong_deviation]; decide, by decide, by dsimp [is_maxcut_strong_deviation]; decide, by decide, by dsimp [is_maxcut_strong_deviation]; decide⟩