Spatial game approach for the distributed k-path vertex cover of networks
QI Long
LI Xiang
Abstract：As a significant branch of covering problems on networks,many difficulties encountered in real-world complex systems can be viewed as instances of the k-path vertex cover problem.In distributed systems,one of the crucial research issues to achieve network covering optimization is how to design decentralized strategies for autonomous decision-making by agents.In this paper,the k-path vertex cover problem is modeled as a spatial game on networks,where individual vertices act as rational agents and communicate exclusively with their neighbors.This study analyzes the relationship between strong Nash equilibrium(SONE)and the k-path vertex cover state within the context of non-cooperative games.Additionally,the proposed game-based synchronous aspiration-driven algorithm(GSAA)is shown to converge to SONEs of the four-player coalitions within finite time.The effectiveness of the algorithm is validated through numerical simulations.In the context of the k-path vertex cover problem,the link between solutions and game equilibria is examined from a coalition-based perspective.This paper introduces a novel approach for solving distributed optimization problems with local coupling constraints on networks within the framework of game theory.
Keywords：complex networksk-path vertex coverspatial gamedistributed optimizationstrong Nash equilibrium
Publication Date：2026-02-28
Online Publishing Date：2026-04-08(First online date of this platform, not the publication date of the document)
Pages：10( 239-248 )