New game theory math reveals limits on AI decision-making in complex systems
Researchers have proven that determining optimal strategies in a competitive graph-coloring game is computationally intractable on most network structures. The finding has implications for AI systems that must make real-time decisions in adversarial environments, suggesting certain optimization problems may require fundamentally different algorithmic approaches regardless of computational power.
Originaltitel: On the complexity of the Maker-Breaker happy vertex game
<p>Given a c-colored graph G, a vertex v of G is said to be happy if it has the same color as all its neighbors. The notion of happy vertices was introduced by Zhang and Li [27] to compute the homophily of a graph. Eto, Fujimoto, Kiya, Matsushita, Miyano, Murao and Saitoh [11] introduced the Maker-Maker version of the Happy vertex game, where two players compete to claim more happy vertices than their opponent. We introduce here the Maker-Breaker happy vertex game: two players, Maker and Breaker, alternately color the vertices of a graph with their respective colors. Maker aims to maximize the number of happy vertices at the end, while Breaker aims to prevent her. This game is also a scoring version of the Maker-Breaker domination game introduced by Duchene, Gledel, Parreau and Renault [8], as a happy vertex corresponds exactly to a vertex that is not dominated in the domination game. Therefore, this game is a very natural game on graphs and can be studied within the scope of scoring positional games [3]. We initiate here the complexity study of this game, by proving that computing its score is PSPACE-complete on trees, NP-hard on caterpillars, and polynomial on subdivided stars. Finally, we provide the exact value of the score on graphs of maximum degree 2, and we provide an FPT-algorithm to compute the score on graphs of bounded neighborhood diversity. An important contribution of the paper is that, to achieve our hardness results, we introduce a new type of incidence graph called the literal-clause incidence graph for 2-SAT formulas. We prove that QMAX 2-SAT remains PSPACE-complete even if this graph is acyclic, and that MAX 2-SAT remains NP-complete, even if this graph is acyclic and has maximum degree 2, i.e. is a union of paths. We demonstrate the importance of this contribution by proving that Incidence, the scoring positional game played on a graph is also PSPACE-complete when restricted to forests.</p>