A Distributed Symmetric Game Optimization to 3-Path Vertex Cover of Networks

As a typical combinatorial optimization problem, the 3-path vertex cover problem has wide applications in practice. To solve the 3-path vertex cover problem from the perspective of distributed optimization, we treat each vertex as an agent (i.e., player) with computation, and decision-making capabilities. First, we establish a 3-player symmetric game model to describe the 3-path vertex cover problem, and design the corresponding cost function for each player. Then, we prove that under the established game model, strict Nash equilibriums (SNEs) act as the basis of the connection between 3-path vertex cover states and minimum 3-path vertex cover states. Next, we propose a novel memory-based synchronous learning (MSL) algorithm, where the initial profile strategy generation of players relies on the designed degree preference rule, and each player has a memory length for recording strategies and independently update their strategies concurrently based on the accessed local information. After that, we prove that our proposed MSL algorithm can guarantee that any strategy profile converges to an SNE, and provide a theoretical analysis of the algorithm’s complexity. Finally, we present numerous numerical simulations to demonstrate the performance of our proposed algorithm on various networks. Moreover, we find that increasing the memory length and adopting the degree preference initialization can yield a better SNE.