AFTD Auto-Formalizing Theoretical Domains

Research Blogs

Unweighted Max-$k$-Cut Games Do Not Always Admit Optimal Strong Equilibria: A 182-Vertex Counterexample for Three Colors

medium tier2026-10-28OP-89reviewed by Claude Code中文版

Abstract

In an unweighted Max-$k$-Cut game on a finite simple graph, each vertex chooses one of $k$ colors to maximize the number of incident edges whose endpoints have different colors. A coloring is optimal if it achieves the maximum cut value, and it is a strong equilibrium if no non-empty coalition of vertices can jointly recolor such that every member strictly improves its utility. While it was established in arXiv:2610.04948 that not every optimal coloring is a strong equilibrium, the paper left open whether every unweighted Max-$k$-Cut game admits at least one optimal coloring that is a strong equilibrium. This post presents a formal negative answer to this question for $k = 3$. We construct a 182-vertex graph, denoted maxcut_pinned_twins_graph, formed by replacing each vertex of the 91-vertex counterexample graph from arXiv:2610.04948 with a pair of independent twin vertices and adding specific pinning edges from core twins to designated anchor twins. We prove that this graph exhibits optimum rigidity: every welfare-maximizing 3-coloring is equal to the doubled initial coloring up to a global permutation of the three colors. Because this unique optimal coloring profile admits a profitable coalitional deviation, the graph possesses no optimal strong equilibrium whatsoever. The main theorem maxcut_op89_optimal_strong_equilibrium_negation and its supporting rigidity lemmas are formally verified in Lean 4.

1. Introduction

In coalitional game theory, unweighted cut games model decentralized resource allocation and partition problems where agents occupy the vertices of a network and seek to distinguish their choices from those of their neighbors. Given a finite simple graph $G = (V, E)$ and an integer $k \ge 3$, the unweighted Max-$k$-Cut game assigns to each vertex $v \in V$ the strategy space of $k$ colors, $\{0, \dots, k-1\}$. The payoff or utility of a vertex $v$ under a coloring profile $\sigma : V \to \{0, \dots, k-1\}$ is defined as the number of neighbors of $v$ in $G$ that are assigned a different color from $\sigma(v)$. The sum of all individual utilities across the vertex set is exactly twice the cut value of the partition, meaning that social welfare maximization in this game coincides with the classical Max-$k$-Cut optimization problem.

A central issue at the intersection of game theory and combinatorial optimization is whether socially optimal configurations can withstand strategic deviations by groups of players. A coloring profile is called a strong equilibrium if no non-empty coalition of vertices can jointly alter their colors in such a way that every participating member strictly increases its individual utility. Because social optimality maximizes the total cut weight, one might ask whether social optimality implies coalitional stability, or at least whether social welfare maximization is compatible with coalitional stability.

In arXiv:2610.04948, Theorem 2 demonstrated that social optimality does not imply coalitional stability: the paper constructed an explicit 91-vertex graph $G_3$ with an optimal 3-coloring $\sigma_0$ from which a coalition of its sixteen core vertices can jointly recolor to a coloring $\tau_0$ so that every member gains one unit of utility, while the cut value stays the same. However, that result demonstrated only that a particular optimal coloring could fail to be coalitionally stable. As noted in Remark 6 and Section 4 of arXiv:2610.04948, the graph $G_3$ does not rule out the existence of another, stable optimum on its graph. Indeed, on $G_3$ itself the deviated coloring $\tau_0$ has the same cut value as $\sigma_0$, so it is optimal, and it is a strong equilibrium (maxcut_anchor_three_coloring_strong): $G_3$ does have an optimal strong equilibrium.

Consequently, Section 4 of arXiv:2610.04948 left open two distinct questions:

  • Does every unweighted Max-$k$-Cut game admit a strong equilibrium?
  • Does every unweighted Max-$k$-Cut game admit an optimal coloring that is a strong equilibrium?

Regarding the existence of optimal strong equilibria, several positive results are known from the literature and formal developments. By Corollary 9 of arXiv:2610.04948, formalized as maxcut_op89_exists_of_max_degree_le, every finite simple graph whose maximum degree satisfies $\Delta(G) \le 2k - 1$ admits an optimal coloring that is a strong equilibrium. In particular, for $k = 3$, any graph with maximum degree at most 5 admits an optimal strong equilibrium, as recorded in maxcut_op89_exists_of_max_degree_five. Furthermore, for small graphs satisfying $|V| \le 2k$, an optimal strong equilibrium is always guaranteed to exist (maxcut_op89_exists_of_card_le). Beyond these degree and cardinality bounds, however, the general compatibility of social optimality and coalitional stability remained unresolved.

This post presents the negative resolution of the second question for $k = 3$, formalized in Lean 4 as maxcut_op89_optimal_strong_equilibrium_negation. We show that it is not true that every unweighted Max-$k$-Cut game on a finite simple graph admits an optimal coloring that is a strong equilibrium. The counterexample is an explicit 182-vertex graph, maxcut_pinned_twins_graph. The graph is constructed by doubling every vertex of the 91-vertex graph from arXiv:2610.04948 into two independent twin vertices and adding pin edges between core twins and designated anchor vertices.

The doubling transformation converts every edge of the base graph into a complete bipartite graph $K_{2,2}$ between the corresponding twin pairs, while the pin edges rigidly fix the optimal 3-colorings. Specifically, we establish an optimum rigidity theorem (maxcut_pinned_twins_optimum_rigidity): every optimal 3-coloring of maxcut_pinned_twins_graph is identical to the doubled base coloring up to a global permutation of the three colors. Because this optimal coloring profile inherits the instability of the original construction under a doubled coalition, no optimal coloring can be a strong equilibrium (maxcut_pinned_twins_refutes_of_rigidity). Thus, for $k = 3$, social optimality and coalitional stability cannot always be achieved together.

2. Preliminaries

We review the formal setting of unweighted Max-$k$-Cut games on finite simple graphs and specify the graph constructions and stability concepts used in the formalization.

Definition 1 (Unweighted Max-$k$-Cut Game). Let $G = (V, E)$ be a finite simple graph where adjacency is decidable, and let $k \ge 3$ be an integer. A coloring is a function $\sigma : V \to \{0, \dots, k-1\}$, represented in Lean as $\sigma : V \to \text{Fin } k$. The utility of a vertex $v \in V$ under coloring $\sigma$ is the number of neighbors of $v$ assigned a color distinct from $\sigma(v)$: $$u_v(\sigma) = \sum_{u \in V, \, G.\text{Adj } u \, v} \mathbf{1}_{\sigma(u) \ne \sigma(v)}.$$ The cut value of $\sigma$ is the cardinality of the cut edge set $E(\sigma) = \{\{u, v\} \in E : \sigma(u) \ne \sigma(v)\}$. The total social welfare of the coloring profile is $\sum_{v \in V} u_v(\sigma) = 2 |E(\sigma)|$.

Definition 2 (Optimal Coloring). A coloring $\sigma : V \to \text{Fin } k$ is optimal in the Max-$k$-Cut game on $G$ if it maximizes the cut value over all colorings: $$\sum_{v \in V} u_v(\sigma) \ge \sum_{v \in V} u_v(\sigma') \quad \text{for all } \sigma' : V \to \text{Fin } k.$$

Definition 3 (Strong Equilibrium). A coloring profile $\sigma : V \to \text{Fin } k$ is a strong equilibrium if no non-empty coalition $C \subseteq V$ can jointly deviate to a coloring $\tau : C \to \text{Fin } k$ such that every member of $C$ strictly gains. That is, letting $\sigma' : V \to \text{Fin } k$ be defined by $\sigma'(v) = \tau(v)$ for $v \in C$ and $\sigma'(v) = \sigma(v)$ for $v \notin C$, there does not exist any non-empty $C \subseteq V$ and $\tau : C \to \text{Fin } k$ such that $$u_v(\sigma') > u_v(\sigma) \quad \text{for all } v \in C.$$

Definition 4 (Optimal Strong Equilibrium Property, maxcut_has_optimal_strong_equilibrium). A finite simple graph $G$ admits an optimal strong equilibrium in the unweighted Max-$k$-Cut game if there exists a coloring $\sigma : V \to \text{Fin } k$ that is simultaneously optimal and a strong equilibrium: $$\text{maxcut\_has\_optimal\_strong\_equilibrium } G \, k \iff \exists \sigma : V \to \text{Fin } k, \, \sigma \text{ is optimal} \wedge \sigma \text{ is a strong equilibrium}.$$

Definition 5 (The Base Anchor Graph and Base Initial Coloring). The base graph $G_3$ is defined on the disjoint sum type: $$V_0 = \text{Fin } 16 \oplus (\text{Fin } 3 \times \text{Fin } 25).$$ The vertex set contains $16 + 3 \times 25 = 91$ vertices, consisting of 16 core vertices indexed by $\text{inl } i$ for $i \in \{0, \dots, 15\}$, and 75 anchor vertices indexed by $\text{inr } (j, a)$ for $j \in \{0, 1, 2\}$ and $a \in \{0, \dots, 24\}$. The base coloring $\sigma_0$ assigns to each vertex in $V_0$ an initial color in $\text{Fin } 3$.

Definition 6 (The Pinned Twins Graph, maxcut_pinned_twins_graph). The candidate counterexample graph is constructed on the Cartesian product type: $$V = V_0 \times \text{Fin } 2 = (\text{Fin } 16 \oplus (\text{Fin } 3 \times \text{Fin } 25)) \times \text{Fin } 2,$$ comprising $91 \times 2 = 182$ vertices. For each vertex $w \in V_0$, the elements $(w, 0)$ and $(w, 1)$ represent independent twin vertices. The edge relation is generated from a binary relation where $u$ and $v$ are related if and only if $u.1$ and $v.1$ are adjacent in the base graph $G_3$, or the pin relation holds between $u$ and $v$. The pin relation is defined to hold when $u.1 = \text{inl } i$ is a core vertex, $v.1 = \text{inr } (j, a)$ is an anchor vertex, and the following three conditions are met:

  1. $a = 24$, designating the final anchor vertex of the branch;
  2. $v.2 = 0$, selecting the first twin of that anchor;
  3. $j \ne \sigma_0(\text{inl } i)$, connecting only to branches corresponding to colors different from the core vertex's initial color.

Remark on Definitions. The simple graph constructor in Lean automatically removes self-loops and enforces symmetry. Under this definition, twin vertices $(w, 0)$ and $(w, 1)$ of the same vertex $w$ have no base edge between them, as $G_3$ is irreflexive; hence, twin vertices form independent sets of size 2. An edge between $w$ and $z$ in $G_3$ induces a complete bipartite graph $K_{2,2}$ between $\{(w, 0), (w, 1)\}$ and $\{(z, 0), (z, 1)\}$. The pin relation is asymmetric in its definition but becomes symmetric upon applying the simple graph generator.

3. Main result

The main theorem refutes the universal conjecture that every unweighted Max-$k$-Cut game on a finite simple graph admits an optimal coloring that is also a strong equilibrium.

Theorem (Negative Resolution of Optimal Strong Equilibrium Existence, maxcut_op89_optimal_strong_equilibrium_negation). It is not true that for every finite type $V$, every simple graph $G$ on $V$ with decidable adjacency, and every integer $k \ge 3$, the unweighted Max-$k$-Cut game on $G$ admits an optimal coloring that is a strong equilibrium: $$\neg \, \forall (V : \text{Type}) \, [\text{Fintype } V] \, (G : \text{SimpleGraph } V) \, [\text{DecidableRel } G.\text{Adj}] \, (k : \mathbb{N}), \, 3 \le k \to \text{maxcut\_has\_optimal\_strong\_equilibrium } G \, k.$$

The Lean statement of the theorem translates the English claim by quantifying universally over the vertex universe $V$ endowed with a finite type structure, the simple graph $G$ with decidable adjacency, and the color parameter $k \ge 3$, asserting the negation of the proposition maxcut_has_optimal_strong_equilibrium on $G$ and $k$.

The theorem is proved by exhibiting an explicit counterexample at $k = 3$, namely the 182-vertex graph maxcut_pinned_twins_graph. The formal proof rests on two foundational lemmas:

To place this result in context, previous formalizations in the project established several positive existence results under structural restrictions:

The theorem maxcut_op89_optimal_strong_equilibrium_negation shows that, beyond these degree and size bounds, an optimal strong equilibrium need not exist.

Theorem maxcut_op89_optimal_strong_equilibrium_negation (Lean 4, verified)
theorem maxcut_op89_optimal_strong_equilibrium_negation :
    ¬ ∀ (V : Type) [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ),
      3 ≤ k → maxcut_has_optimal_strong_equilibrium G k

4. Proof

Proof idea. On $G_3$ the deviation from $\sigma_0$ to $\tau_0$ is harmless for the question, because $\tau_0$ is another optimum and it is stable. The pinned twins graph is built so that the doubled $\sigma_0$ becomes the only optimum up to renaming colors, while the doubled deviation still pays every coalition member.

The construction has two parts. First, every vertex $w$ of $G_3$ becomes two non-adjacent twins $(w,0)$ and $(w,1)$, and every edge of $G_3$ becomes a complete bipartite graph $K_{2,2}$ between the twin pairs. Second, each of the 32 core twins $(\mathrm{inl}\ i, t)$ is joined by a pin edge to the anchor twin $(\mathrm{inr}\ (j,24), 0)$ for each of the two colors $j \ne \sigma_0(\mathrm{inl}\ i)$; these are 64 new edges. Under the doubled coloring $\sigma(w,t) = \sigma_0(w)$ no pin edge is monochromatic.

Lemma 1 (maxcut_pinned_twins_optimum_rigidity). Every welfare-maximizing 3-coloring $\rho$ of maxcut_pinned_twins_graph satisfies $\rho = \lambda v,\ p(\sigma_0(v.1))$ for some permutation $p$ of the three colors.

Proof of Lemma 1. Welfare plus the number of ordered monochromatic pairs is the degree sum, so an optimal coloring minimizes ordered monochromatic pairs. On $G_3$ the minimum is 48 (24 monochromatic edges), attained by $\sigma_0$, by the paper's optimality theorem, which is formalized. On the twin graph the doubled $\sigma$ has exactly $4 \cdot 48 = 192$ ordered monochromatic pairs, all on doubled edges. So an optimal $\rho$ has at most 192.

The key step is an averaging identity. For each choice $c$ of one twin $c(w) \in \{0,1\}$ at every vertex $w$ of $G_3$, the slice $w \mapsto \rho(w, c(w))$ is a 3-coloring of $G_3$, so it has at least 48 ordered monochromatic pairs. For an edge $uw$ of $G_3$, each of the four twin pairs $(s,t)$ is selected by exactly a quarter of all $2^{91}$ choices. In Lean this is an involution argument: flipping $c$ at $u$ and at $w$ permutes the choices. Summing over all choices gives $$4 \sum_c \mathrm{mono}_{G_3}(\text{slice}_c) = 2^{91} \cdot B(\rho),$$ where $B(\rho)$ counts the ordered monochromatic pairs of $\rho$ on doubled edges. Hence $B(\rho) \ge 4 \cdot 48 = 192$. With the upper bound, $B(\rho) = 192$, no pin edge is monochromatic, and every slice has exactly 48 ordered monochromatic pairs.

Next comes the paper's conflict-gap lemma. Each anchor class of $G_3$ is an independent set of 25 vertices, and a slice has only 24 monochromatic edges. So each anchor class contains a vertex on no monochromatic edge, these three vertices form a triangle, and every anchor class is monochromatic with three distinct colors. Every slice therefore colors the anchors canonically up to a permutation. Comparing the slice that picks twin 0 everywhere with slices that differ from it in a single twin shows that all 150 anchor twins follow one permutation $p$. Finally, each core twin $(\mathrm{inl}\ i, t)$ has pin neighbors colored $p(j)$ for both $j \ne \sigma_0(\mathrm{inl}\ i)$, and these pin edges are not monochromatic. So its color is $p(\sigma_0(\mathrm{inl}\ i))$.

Lemma 2 (maxcut_pinned_twins_refutes_of_rigidity). If every optimal 3-coloring of maxcut_pinned_twins_graph is a color permutation of the doubled $\sigma_0$, then the graph has no optimal strong equilibrium.

Proof of Lemma 2. By rigidity an optimal coloring has the form $\rho = p \circ \sigma$. Take the coalition of all 32 core twins and let them move to $p \circ \tau$, where $\tau(w,t) = \tau_0(w)$. On the doubled edges each core twin sees every neighbor of $G_3$ twice, so its gain of one unit in $G_3$ becomes a gain of two. Since $\tau_0$ changes the color of every core vertex to one of the two pinned anchor colors, exactly one of its two pin edges becomes monochromatic, a loss of one. Every coalition member therefore gains exactly one unit; this is checked by kernel computation over the whole graph. Utilities are invariant under a global color permutation, so the same deviation works from $p \circ \sigma$, and $\rho$ is not a strong equilibrium.

Proof of the main theorem. Instantiate the universal statement at the vertex type $(\mathrm{Fin}\ 16 \oplus (\mathrm{Fin}\ 3 \times \mathrm{Fin}\ 25)) \times \mathrm{Fin}\ 2$, the graph maxcut_pinned_twins_graph and $k = 3$. This gives an optimal strong equilibrium, which Lemma 2 applied to Lemma 1 excludes.

5. Discussion

The resolution of Question 2 from arXiv:2610.04948 clarifies the boundary between social optimality and coalitional stability in network games. The original paper established that an optimal coloring can fail to be a strong equilibrium, but left open whether every game still possesses at least one optimal coloring that is stable. The construction of maxcut_pinned_twins_graph settles this question negatively for $k = 3$, showing that there exist games where every optimal coloring is coalitionally unstable.

It is instructive to examine how this result delineates the limits of existing positive guarantees. Previous work identified three regimes where optimal strong equilibria are guaranteed to exist:

The same graph is not 3-colorable, has far more than $2k+2 = 8$ vertices and maximum degree far above $2k = 6$. So the case left open by the degree bound (graphs that are not $k$-colorable and have a vertex of degree at least $2k$) does not always admit an optimal strong equilibrium; this is also formalized.

Several natural questions remain open:

  • Question 1 of arXiv:2610.04948: Does every unweighted Max-$k$-Cut game admit a strong equilibrium (not necessarily optimal)? The counterexample here refutes the existence of an optimal strong equilibrium, but does not address whether maxcut_pinned_twins_graph or other graphs admit suboptimal strong equilibria.
  • Higher color numbers ($k \ge 4$): The present counterexample operates specifically at $k = 3$. The paper's graph $G_k$ exists for every $k \ge 3$; whether doubling and pinning it gives the same rigidity for every $k$ is not proved here.
  • Minimal counterexample size: The graph maxcut_pinned_twins_graph contains 182 vertices. Determining the minimum number of vertices required for an unweighted Max-3-Cut game to lack an optimal strong equilibrium remains an open question, spanning the gap between the small-cardinality bound $|V| \le 6$ and the 182-vertex construction.

Why it is research-level

  • Answers the paper's Question 2 negatively for k = 3: a 182-vertex graph (the paper's 91-vertex G_3 with every vertex doubled into independent twins, plus pin edges from each core twin to two anchors) has an optimal Max-3-Cut coloring that is unique up to color permutation and not a strong equilibrium, so no optimal coloring is a strong equilibrium. The paper only shows that some optimal coloring can fail

Lean declarations

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

References

  1. 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.