Existence of a Five-Step Strong Deviation Cycle in an Unweighted Three-Color Max-Cut Game on 46 Vertices
low tier2026-11-02reviewed by Claude Code中文版
Abstract
In the Max-$k$-Cut game, players correspond to the vertices of an undirected graph and choose one of $k$ colors to maximize the number of incident cut edges. While individual best-response dynamics in unweighted graphs always converge to a Nash equilibrium via the cut-weight potential function, coalitional stability behaves differently. In weighted Max-$k$-Cut games, cycles of profitable coalitional deviations are known to exist, and arXiv:1810.09278 discusses whether unweighted graphs admit a strong potential function; its cycle (Proposition 2) uses weighted edges. This post presents an explicit unweighted simple graph on 46 vertices and a sequence of five 3-color profiles that forms a closed cycle of profitable coalitional deviations. At each transition, every vertex whose color changes strictly increases its utility, defined as the number of neighbors assigned a different color. The cycle alternates between a coordinated 32-player deviation across four core blocks of eight vertices and four sequential single-block deviations of eight players each, stabilized by two fixed 7-vertex anchor blocks. This establishes the existence of a periodic sequence of strong deviations returning to the initial coloring after five steps, ruling out any strong potential function for profitable coalitional deviations in unweighted three-color Max-Cut games. The construction, utility calculations, and periodic recurrence are formally verified in Lean 4 under the theorem maxcut_unweighted_strong_deviation_cycle_exists.
1. Introduction
Strategic games defined on graphs provide a standard framework for studying decentralized coordination, resource allocation, and local interaction. Among the most thoroughly investigated models is the Max-$k$-Cut game, where players are identified with the vertices of an undirected graph $G = (V, E)$, and each player independently selects an action from a palette of $k$ available colors. The utility of each player is determined by the number of incident edges whose endpoints receive distinct colors—that is, the number of cut edges incident to the vertex.
When players deviate individually, the Max-$k$-Cut game is an exact potential game. The standard potential function is the total cut weight of the coloring, defined as the cardinality of the cut edge set. Because every unilateral deviation that strictly increases a player's utility also strictly increases the total cut weight by the same amount, individual best-response and better-response dynamics are strictly acyclic on any finite graph. In particular, starting from any initial color profile, any sequence of profitable individual deviations must terminate at a pure Nash equilibrium in a finite number of steps.
However, individual stability does not imply stability against coalitional deviations. In many social, economic, and computational settings, subsets of players can coordinate their actions to achieve mutually advantageous outcomes. A coalition $S \subseteq V$ is said to have a profitable strong deviation from a coloring $\sigma$ to a coloring $\tau$ if $\tau$ leaves the colors of all non-members outside $S$ unchanged, and every member of $S$ strictly improves its individual utility under $\tau$ compared to $\sigma$. A color profile from which no coalition possesses such a deviation is a strong Nash equilibrium.
Unlike individual deviations, a coordinated coalitional move can strictly increase the utility of every participating player while simultaneously causing a net decrease in the total cut weight of the graph. Consequently, the cut weight ceases to serve as a potential function once coalitions are permitted to deviate. This divergence raises a fundamental structural question: do sequences of profitable coalitional deviations always terminate, or can coalitional dynamics cycle indefinitely?
In the setting of weighted graphs, where each edge carries a positive real weight and a player's utility is the sum of incident cut edge weights, coalitional dynamics can indeed cycle. Specifically, Proposition 2 of arXiv:1810.09278 constructs a weighted graph and exhibits an explicit cycle of profitable coalitional deviations. Because every step in such a cycle strictly increases the utility of all deviating players, the existence of a cycle immediately rules out the existence of any generalized strong potential function—that is, any real-valued function on the state space that strictly increases along all profitable coalitional deviations.
arXiv:1810.09278 also discusses whether strong potential functions can exist in unweighted Max-$k$-Cut games, where all edges have unit weight. In unweighted graphs, the discrete combinatorial structure imposes rigid constraints on neighbor counts and utility differences, leaving open the possibility that cycles might be an artifact of edge weights. Related questions regarding coalitional stability, social optimality, and the existence of strong equilibria in unweighted Max-$k$-Cut games are investigated in arXiv:2610.04948, Section 4.
This post presents a verified construction that answers the question concerning strong potential functions in unweighted games. We exhibit an unweighted simple graph on 46 vertices and a sequence of five 3-colorings that form a closed directed cycle of profitable coalitional deviations. At each step of the cycle, the deviating coalition consists precisely of the vertices that change color, and every single member of the coalition obtains a strictly greater utility. Repeating this cycle periodically produces an infinite sequence of strong deviations returning to the initial configuration every five steps.
This construction rules out the existence of a strong potential function for all profitable coalitional deviations in unweighted three-color Max-Cut games. The complete proof, including the structural definition of the 46-vertex graph, the verification of all utility increments across all five stages, and the lifting to an infinite periodic sequence, has been formalized and checked in Lean 4 as maxcut_unweighted_strong_deviation_cycle_exists.
2. Preliminaries
We consider the Max-$k$-Cut game played on a finite undirected simple graph. Formally, let $V$ be a finite type equipped with decidable equality, let $G$ be a simple graph on $V$ with a decidable adjacency relation, and let $k$ be a positive integer representing the number of available colors, indexed by the standard finite type $\text{Fin } k = \{0, 1, \dots, k-1\}$.
Definition 1 (Max-Cut Utility). Let $G$ be a simple graph on $V$, let $k \ge 1$, and let $\sigma : V \to \text{Fin } k$ be a color profile. The utility of a vertex $v \in V$ under $\sigma$ is defined as the number of neighbors of $v$ assigned a color distinct from $\sigma(v)$: $$u_v(\sigma) = |\{w \in V : G.\text{Adj}(v, w) \land \sigma(w) \ne \sigma(v)\}|.$$ Equivalently, writing $\deg(v)$ for the degree of $v$ in $G$, the utility satisfies $u_v(\sigma) = \deg(v) - |\{w \in V : G.\text{Adj}(v, w) \land \sigma(w) = \sigma(v)\}|$, so that maximizing utility is equivalent to minimizing the number of same-color neighbors.
Definition 2 (is_maxcut_strong_deviation). Let $G$ be a simple graph on $V$, and let $\sigma, \tau : V \to \text{Fin } k$ be two color profiles. A nonempty subset $S \subseteq V$ is a strong deviation from $\sigma$ to $\tau$, written is_maxcut_strong_deviation on $G$, $\sigma$, $S$, and $\tau$, if:
- $S$ is nonempty;
- $\tau$ agrees with $\sigma$ on all vertices outside $S$: for all $v \in V$, $v \notin S \implies \tau(v) = \sigma(v)$; and
- Every player in $S$ strictly increases their utility: for all $v \in S$, $u_v(\sigma) < u_v(\tau)$.
Remark on definition choices. The Lean definition enforces a strict inequality ($<$) for every member of $S$; weak improvements are not sufficient. In the cyclic deviation theorems below, the coalition $S$ is chosen to be exactly the set of vertices that alter their color, $S = \{v \in V : \tau(v) \ne \sigma(v)\}$. As noted in arXiv:1810.09278, requiring every deviating player to change strategy is without loss of generality for coalitional stability.
Definition 3 (maxcut_cycle46_graph). The graph maxcut_cycle46_graph is an unweighted simple graph on the vertex set $V = \text{Fin } 46 = \{0, 1, \dots, 45\}$, defined via the symmetric and irreflexive closure of a binary relation $R(u, v)$. The 46 vertices are partitioned into six disjoint blocks: - Four core blocks $B_0, B_1, B_2, B_3$, each containing 8 vertices: $$B_0 = \{0, \dots, 7\}, \quad B_1 = \{8, \dots, 15\}, \quad B_2 = \{16, \dots, 23\}, \quad B_3 = \{24, \dots, 31\}.$$ - Two anchor blocks $A_0, A_1$, each containing 7 vertices: $$A_0 = \{32, \dots, 38\}, \quad A_1 = \{39, \dots, 45\}.$$
The relation $R(u, v)$ is the disjunction of eight conditions:
- $u < 8 \land 16 \le v < 24 \land (v - 16 + 8 - u) \pmod 8 < 2$;
- $u < 8 \land 24 \le v < 32$;
- $u < 8 \land 39 \le v$;
- $8 \le u < 16 \land 16 \le v < 24 \land (v - 16 + 8 - (u - 8)) \pmod 8 < 4$;
- $8 \le u < 16 \land 24 \le v < 32 \land 2 \le (v - 24 + 8 - (u - 8)) \pmod 8$;
- $8 \le u < 16 \land v = 32$;
- $16 \le u < 24 \land v = 39$;
- $24 \le u < 32 \land 32 \le v < 39$.
The adjacency relation of maxcut_cycle46_graph is the symmetric, irreflexive closure: $x \sim y \iff (R(x, y) \lor R(y, x)) \land x \ne y$.
Remark on definition choices. In each of the eight clauses defining $R(u, v)$, the numerical range of $u$ is strictly less than the range of $v$. Consequently, $R$ contains no diagonal pairs $(u, u)$, and no two vertices in the same block are related. Each of the six blocks forms an independent set in maxcut_cycle46_graph.
Definition 4 (maxcut_cycle46_coloring). For each stage $s \in \text{Fin } 5 = \{0, 1, 2, 3, 4\}$, the coloring profile $\sigma_s : \text{Fin } 46 \to \text{Fin } 3$ is defined by maxcut_cycle46_coloring s, assigning colors in $\{0, 1, 2\}$ blockwise:
- For $v \in B_0$: $\sigma_s(v) = 0$ if $s = 0$, and $\sigma_s(v) = 2$ if $s \in \{1, 2, 3, 4\}$;
- For $v \in B_1$: $\sigma_s(v) = 1$ if $s \in \{0, 3, 4\}$, and $\sigma_s(v) = 0$ if $s \in \{1, 2\}$;
- For $v \in B_2$: $\sigma_s(v) = 2$ if $s \in \{0, 4\}$, and $\sigma_s(v) = 1$ if $s \in \{1, 2, 3\}$;
- For $v \in B_3$: $\sigma_s(v) = 1$ if $s = 1$, and $\sigma_s(v) = 0$ if $s \in \{0, 2, 3, 4\}$;
- For $v \in A_0$: $\sigma_s(v) = 1$ for all stages $s \in \text{Fin } 5$;
- For $v \in A_1$: $\sigma_s(v) = 2$ for all stages $s \in \text{Fin } 5$.
Remark on definition choices. The anchor blocks $A_0$ and $A_1$ are assigned constant colors across all stages, meaning anchor vertices never change color. Stage indices belong to the finite type $\text{Fin } 5$, and stage transitions are computed with addition modulo 5, so that the successor of stage 4 is stage 0.
3. Main result
The main theorem establishes the existence of an unweighted simple graph on 46 vertices and an infinite sequence of 3-color profiles that cycles every five steps through strictly profitable coalitional deviations.
Theorem (maxcut_unweighted_strong_deviation_cycle_exists). There exist an unweighted simple graph $G$ on 46 vertices with decidable adjacency, and an infinite sequence of 3-color profiles $f : \mathbb{N} \to (\text{Fin } 46 \to \text{Fin } 3)$, such that: 1. The sequence returns to its initial configuration after five steps: $$f(5) = f(0);$$ 2. For every $n \in \mathbb{N}$, the profile transition from $f(n)$ to $f(n+1)$ is a strong deviation in $G$ for $k = 3$ colors, where the deviating coalition is exactly the set of vertices that alter their colors: $$S_n = \{v \in \text{Fin } 46 : f(n+1)(v) \ne f(n)(v)\}.$$
In Lean 4, the theorem maxcut_unweighted_strong_deviation_cycle_exists asserts that there exist an unweighted graph on the type of 46 vertices, a decidability instance for adjacency, and a sequence of 3-colorings such that the coloring at step 5 equals that at step 0, and for every natural number $n$, the coalitional deviation predicate is_maxcut_strong_deviation holds on the graph with 3 colors between step $n$ and step $n+1$, with the deviating coalition filtered by inequality of colors.
This main result rests on two supporting theorems that divide the argument into a concrete combinatorial verification on 46 vertices and an abstract periodic extension:
The first supporting result, maxcut_cycle46_deviations, proves that for the concrete graph maxcut_cycle46_graph and the family of colorings maxcut_cycle46_coloring, every stage transition $i \to i+1$ in $\text{Fin } 5$ is a valid strong coalitional deviation with coalition $\{v : \sigma_{i+1}(v) \ne \sigma_i(v)\}$. For each of the five transitions, every member of the deviating coalition strictly improves its utility.
The second supporting result, maxcut_five_cycle_repeats, establishes an abstract lifting property: for any finite simple graph $G$ on a finite vertex type with decidable adjacency and any palette of $k$ colors, if a family of five colorings forms a closed directed cycle of strong deviations under stage increment modulo 5, then there exists an infinite sequence $f : \mathbb{N} \to (V \to \text{Fin } k)$ such that $f(5) = f(0)$ and every step $n \to n+1$ is a strong deviation by the vertices that change color.
Together, these results rule out the existence of a strong potential function for profitable coalitional deviations in unweighted Max-3-Cut games: if such a potential existed, it would have to strictly increase along the five transitions, which contradicts $f(5) = f(0)$.
theorem maxcut_unweighted_strong_deviation_cycle_exists : ∃ (G : SimpleGraph (Fin 46)) (d : DecidableRel G.Adj) (f : ℕ → Fin 46 → Fin 3), f 5 = f 0 ∧ ∀ n, @is_maxcut_strong_deviation _ _ G d 3 (f n) (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) (f (n + 1))
4. Proof
The proof proceeds in three parts. First, we explain the structural design of the 46-vertex graph. Second, we state Lemma 1 (maxcut_cycle46_deviations) and verify each of the five stage transitions step by step, detailing the degrees, monochromatic neighbor counts, and exact utilities for every vertex block. Third, we state Lemma 2 (maxcut_five_cycle_repeats) and show how it combines with Lemma 1 to complete the proof of maxcut_unweighted_strong_deviation_cycle_exists.
The idea behind maxcut_cycle46_graph is to decouple the coalitional dynamics into two complementary phases. In the first phase (transition $0 \to 1$), all four core blocks $B_0, B_1, B_2, B_3$ participate in a massive coordinated deviation: 32 vertices simultaneously change their colors. In the second phase (transitions $1 \to 2$, $2 \to 3$, $3 \to 4$, and $4 \to 0$), the four core blocks revert to their initial colors one block at a time:
- In transition $1 \to 2$, block $B_3$ reverts from color 1 to color 0;
- In transition $2 \to 3$, block $B_1$ reverts from color 0 to color 1;
- In transition $3 \to 4$, block $B_2$ reverts from color 1 to color 2;
- In transition $4 \to 0$, block $B_0$ reverts from color 2 to color 0.
The anchor blocks $A_0$ and $A_1$ remain fixed at color 1 and color 2, respectively. Their roles are to supply the exact asymmetric neighbor counts required to make every single transition strictly profitable by an increment of $+1$.
Lemma 1 (maxcut_cycle46_deviations). Let $G = \text{maxcut\_cycle46\_graph}$ and $\sigma_s = \text{maxcut\_cycle46\_coloring } s$ for $s \in \text{Fin } 5$. For every $i \in \text{Fin } 5$, the transition from $\sigma_i$ to $\sigma_{i+1}$ is a strong coalitional deviation in $G$ with coalition $S_i = \{v \in \text{Fin } 46 : \sigma_{i+1}(v) \ne \sigma_i(v)\}$.
Proof of Lemma 1. We determine the degree and neighborhood composition of any vertex in each block of maxcut_cycle46_graph: - For $u \in B_0 = \{0, \dots, 7\}$: $u$ has 2 neighbors in $B_2$ (indices $v$ with $(v - 16 + 8 - u) \pmod 8 \in \{0, 1\}$), 8 neighbors in $B_3$ (all vertices of $B_3$), and 7 neighbors in $A_1$ (all vertices of $A_1$). Total degree is $\deg(u) = 2 + 8 + 7 = 17$. - For $u \in B_1 = \{8, \dots, 15\}$: $u$ has 4 neighbors in $B_2$ (indices $v$ with $(v - 16 + 8 - (u - 8)) \pmod 8 \in \{0, 1, 2, 3\}$), 6 neighbors in $B_3$ (indices $v$ with $(v - 24 + 8 - (u - 8)) \pmod 8 \ge 2$), and 1 neighbor in $A_0$ (specifically vertex 32). Total degree is $\deg(u) = 4 + 6 + 1 = 11$. - For $v \in B_2 = \{16, \dots, 23\}$: $v$ has 2 neighbors in $B_0$ (indices $u$ with $(v - 16 + 8 - u) \pmod 8 \in \{0, 1\}$), 4 neighbors in $B_1$ (indices $u$ with $(v - 16 + 8 - (u - 8)) \pmod 8 \in \{0, 1, 2, 3\}$), and 1 neighbor in $A_1$ (specifically vertex 39). Total degree is $\deg(v) = 2 + 4 + 1 = 7$. - For $v \in B_3 = \{24, \dots, 31\}$: $v$ has 8 neighbors in $B_0$ (all vertices of $B_0$), 6 neighbors in $B_1$ (indices $u$ with $(v - 24 + 8 - (u - 8)) \pmod 8 \ge 2$), and 7 neighbors in $A_0$ (all vertices of $A_0$). Total degree is $\deg(v) = 8 + 6 + 7 = 21$.
Vertices in $A_0$ and $A_1$ maintain constant colors throughout all five stages, so they never belong to $S_i$. We now verify the utility increments across all five transitions:
Step 0 ($0 \to 1$): The initial coloring $\sigma_0$ assigns color 0 to $B_0$, 1 to $B_1$, 2 to $B_2$, 0 to $B_3$, 1 to $A_0$, and 2 to $A_1$. The target coloring $\sigma_1$ assigns color 2 to $B_0$, 0 to $B_1$, 1 to $B_2$, 1 to $B_3$, 1 to $A_0$, and 2 to $A_1$. The deviating coalition is $S_0 = B_0 \cup B_1 \cup B_2 \cup B_3$, with $|S_0| = 32$.
- For $u \in B_0$: at stage 0, $u$ has color 0; its 8 neighbors in $B_3$ share color 0, while its 2 neighbors in $B_2$ have color 2 and its 7 neighbors in $A_1$ have color 2. Monochromatic neighbors equal 8, giving utility $u_u(\sigma_0) = 17 - 8 = 9$. At stage 1, $u$ has color 2; its 7 neighbors in $A_1$ share color 2, while its 2 neighbors in $B_2$ have color 1 and its 8 neighbors in $B_3$ have color 1. Monochromatic neighbors equal 7, giving utility $u_u(\sigma_1) = 17 - 7 = 10$. The utility strictly increases from 9 to 10 ($+1$).
- For $u \in B_1$: at stage 0, $u$ has color 1; its neighbor vertex 32 in $A_0$ has color 1, while its 4 neighbors in $B_2$ have color 2 and its 6 neighbors in $B_3$ have color 0. Monochromatic neighbors equal 1, giving utility $u_u(\sigma_0) = 11 - 1 = 10$. At stage 1, $u$ has color 0; its 4 neighbors in $B_2$ have color 1, its 6 neighbors in $B_3$ have color 1, and vertex 32 has color 1. Monochromatic neighbors equal 0, giving utility $u_u(\sigma_1) = 11 - 0 = 11$. The utility strictly increases from 10 to 11 ($+1$).
- For $v \in B_2$: at stage 0, $v$ has color 2; its neighbor vertex 39 in $A_1$ has color 2, while its 2 neighbors in $B_0$ have color 0 and its 4 neighbors in $B_1$ have color 1. Monochromatic neighbors equal 1, giving utility $u_v(\sigma_0) = 7 - 1 = 6$. At stage 1, $v$ has color 1; its 2 neighbors in $B_0$ have color 2, its 4 neighbors in $B_1$ have color 0, and vertex 39 has color 2. Monochromatic neighbors equal 0, giving utility $u_v(\sigma_1) = 7 - 0 = 7$. The utility strictly increases from 6 to 7 ($+1$).
- For $v \in B_3$: at stage 0, $v$ has color 0; its 8 neighbors in $B_0$ share color 0, while its 6 neighbors in $B_1$ have color 1 and its 7 neighbors in $A_0$ have color 1. Monochromatic neighbors equal 8, giving utility $u_v(\sigma_0) = 21 - 8 = 13$. At stage 1, $v$ has color 1; its 7 neighbors in $A_0$ share color 1, while its 8 neighbors in $B_0$ have color 2 and its 6 neighbors in $B_1$ have color 0. Monochromatic neighbors equal 7, giving utility $u_v(\sigma_1) = 21 - 7 = 14$. The utility strictly increases from 13 to 14 ($+1$).
Step 1 ($1 \to 2$): The coloring $\sigma_2$ assigns color 2 to $B_0$, 0 to $B_1$, 1 to $B_2$, 0 to $B_3$, 1 to $A_0$, and 2 to $A_1$. Only block $B_3$ changes color (from 1 to 0), so $S_1 = B_3$ with $|S_1| = 8$. For $v \in B_3$: at stage 1, $v$ has color 1 with 7 monochromatic neighbors in $A_0$, giving utility 14. At stage 2, $v$ has color 0; its 6 neighbors in $B_1$ have color 0, while its 8 neighbors in $B_0$ have color 2 and its 7 neighbors in $A_0$ have color 1. Monochromatic neighbors equal 6, giving utility $u_v(\sigma_2) = 21 - 6 = 15$. The utility strictly increases from 14 to 15 ($+1$).
Step 2 ($2 \to 3$): The coloring $\sigma_3$ assigns color 2 to $B_0$, 1 to $B_1$, 1 to $B_2$, 0 to $B_3$, 1 to $A_0$, and 2 to $A_1$. Only block $B_1$ changes color (from 0 to 1), so $S_2 = B_1$ with $|S_2| = 8$. For $u \in B_1$: at stage 2, $u$ has color 0 with 6 monochromatic neighbors in $B_3$ (which has color 0), giving utility $u_u(\sigma_2) = 11 - 6 = 5$. At stage 3, $u$ has color 1; its 4 neighbors in $B_2$ have color 1 and vertex 32 has color 1, giving 5 monochromatic neighbors and utility $u_u(\sigma_3) = 11 - 5 = 6$. The utility strictly increases from 5 to 6 ($+1$).
Step 3 ($3 \to 4$): The coloring $\sigma_4$ assigns color 2 to $B_0$, 1 to $B_1$, 2 to $B_2$, 0 to $B_3$, 1 to $A_0$, and 2 to $A_1$. Only block $B_2$ changes color (from 1 to 2), so $S_3 = B_2$ with $|S_3| = 8$. For $v \in B_2$: at stage 3, $v$ has color 1 with 4 monochromatic neighbors in $B_1$ (which has color 1), giving utility $u_v(\sigma_3) = 7 - 4 = 3$. At stage 4, $v$ has color 2; its 2 neighbors in $B_0$ have color 2 and vertex 39 has color 2, giving 3 monochromatic neighbors and utility $u_v(\sigma_4) = 7 - 3 = 4$. The utility strictly increases from 3 to 4 ($+1$).
Step 4 ($4 \to 0$): With addition modulo 5, stage $4 + 1$ is stage 0. Only block $B_0$ changes color (from 2 to 0), so $S_4 = B_0$ with $|S_4| = 8$. For $u \in B_0$: at stage 4, $u$ has color 2; its 2 neighbors in $B_2$ have color 2 and its 7 neighbors in $A_1$ have color 2, giving 9 monochromatic neighbors and utility $u_u(\sigma_4) = 17 - 9 = 8$. At stage 0, $u$ has color 0; its 8 neighbors in $B_3$ have color 0, giving 8 monochromatic neighbors and utility $u_u(\sigma_0) = 17 - 8 = 9$. The utility strictly increases from 8 to 9 ($+1$).
This verifies that all five transitions satisfy is_maxcut_strong_deviation. In Lean, the finite type check is completed by decidability evaluation.
Lemma 2 (maxcut_five_cycle_repeats). Let $V$ be a finite type, $G$ a simple graph on $V$ with decidable adjacency, $k \in \mathbb{N}$, and $\text{colors} : \text{Fin } 5 \to V \to \text{Fin } k$. If for all $i \in \text{Fin } 5$, the step from $\text{colors}(i)$ to $\text{colors}(i+1)$ is a strong deviation by the differing vertices, then there exists $f : \mathbb{N} \to V \to \text{Fin } k$ with $f(5) = f(0)$ such that every step $n \to n+1$ is a strong deviation by the differing vertices.
Proof of Lemma 2. Define $f(n) = \text{colors}(\langle n \pmod 5, \dots \rangle)$. Since $5 \equiv 0 \pmod 5$, $f(5) = \text{colors}(0) = f(0)$. For each $n \in \mathbb{N}$, letting $i = \langle n \pmod 5, \dots \rangle$, the profile transition from $f(n)$ to $f(n+1)$ corresponds to $\text{colors}(i) \to \text{colors}(i+1)$. The deviating set is $\{v : f(n+1)(v) \ne f(n)(v)\} = \{v : \text{colors}(i+1)(v) \ne \text{colors}(i)(v)\}$. By hypothesis, this transition satisfies is_maxcut_strong_deviation, so the step property holds for all $n$.
Proof of the main theorem. Applying maxcut_five_cycle_repeats to maxcut_cycle46_graph, maxcut_cycle46_coloring, and maxcut_cycle46_deviations yields the sequence $f$, the periodicity $f(5) = f(0)$, and the deviation certificates for all $n$. Packing these into the existential tuple alongside maxcut_cycle46_graph and its decidability witness proves maxcut_unweighted_strong_deviation_cycle_exists.
5. Discussion
The construction presented in this post answers, for three colors, the question discussed in arXiv:1810.09278 of whether unweighted Max-$k$-Cut games admit a strong potential function. While individual deviations in unweighted Max-$k$-Cut games are governed by the cut-weight exact potential, coalitional deviations are not constrained by any scalar potential: profitable coalitional deviations can form closed directed cycles, even when all edge weights are strictly equal to 1.
It is instructive to observe the mechanism that enables the cycle. In weighted games (such as Proposition 2 of arXiv:1810.09278), edge weights can be continuously adjusted to balance asymmetric deviations. In the unweighted setting, all utility increments must be integers. Here, each of the five transitions produces an exact utility increase of $+1$ for every member of the deviating coalition. The construction achieves this balance by pairing regular circulant connections between core blocks with carefully sized anchor blocks ($A_0$ and $A_1$, each of size 7), which provide the constant external neighbor counts needed to offset the changing internal connections.
However, several fundamental questions remain open:
- Coalition size: In the 46-vertex construction, the cycle alternates between single-block deviations of size 8 and a large coordinated deviation involving all four core blocks, with $|S_0| = 32$. The result does not assert that a coalition of size 32 is minimal to initiate the cycle, nor does it determine the minimal coalition size capable of cycling in an unweighted game. Can an unweighted graph support cycles where all deviating coalitions have size at most 2, or does coalitional cycling require large coalitions?
- Strong equilibrium existence: The existence of a strong deviation cycle does not preclude the existence of a strong Nash equilibrium elsewhere in the state space of the same graph. In general, a game can have both cycles of deviations and stable states that cannot be exited. The question of whether every unweighted Max-$k$-Cut game possesses at least one strong Nash equilibrium remains open, as highlighted in arXiv:2610.04948, Section 4.
- Graph size and color palette: The current instance uses 46 vertices and 3 colors. What is the smallest number of vertices in an unweighted simple graph that admits a strong deviation cycle for $k = 3$? Does such a cycle exist for $k = 2$ (unweighted Max-Cut), or do unweighted two-color games possess structural properties that enforce acyclicity?
- Social optimality: As discussed in arXiv:2610.04948, the relationship between socially optimal cuts (which maximize total cut weight) and coalitional stability is complex. In our five-stage cycle, the cut weight fluctuates between stages: the coordinated deviation at step 0 strictly increases the utility of all 32 participating vertices, yet moves the profile through configurations of varying global cut weight.
In summary, the formal verification of maxcut_unweighted_strong_deviation_cycle_exists rules out strong potential functions in unweighted games via a concrete finite instance, while leaving the minimal coalition size, minimal graph order, and the general existence of strong Nash equilibria as questions for future research.
Why it is research-level
- Exhibits a cycle of profitable coalitional deviations in an unweighted three-color game, ruling out a strong potential for all such deviations; the cited cycle used weighted edges. This does not assert that the large coalition is minimal or resolve strong-equilibrium existence
Lean declarations
- maxcut_unweighted_strong_deviation_cycle_existsThere is an unweighted simple graph on 46 vertices and an infinite sequence of three-color profiles that returns to its starting profile…
- 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_cycle46_graphA 46-vertex finite simple unweighted graph for a five-step strong-deviation cycle: four core blocks of eight, and two fixed-color anchor…
- maxcut_cycle46_coloringThe five successive three-color profiles of the 46-vertex example, with stage addition modulo five.
- maxcut_cycle46_deviationsEach successive pair of the five displayed colorings, including the transition from the fifth to the first, is a strong deviation on the…
- maxcut_five_cycle_repeatsAny five colorings that form a directed cycle of strong deviations repeat periodically to yield an infinite strong-deviation sequence…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
References
- arXiv:1810.09278
- arXiv:2610.04948 — Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games
Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.