Potential Game Theoretic Learning for the Minimal Weighted Vertex Cover in Distributed Networking Systems
将最小加权顶点覆盖问题转化为势博弈，提出一种基于松弛贪婪和有限记忆的分布式学习算法，证明其收敛到纳什均衡，并通过调整记忆长度和突变概率提升系统目标，在加权和未加权版本中均优于典型方法。
Toward the minimal weighted vertex cover (MWVC) in agent-based networking systems, this paper recasts it as a potential game and proposes a distributed learning algorithm based on relaxed greed and finite memory. With the concept of convention, we prove that our algorithm converges with probability 1 to Nash equilibria, which serve as the bridge connecting the game and the MWVC. More importantly, an additional degree of freedom is also provided for equilibrium refinement, such that increasing memory lengths and mutation probabilities contributes to the improvement of system-level objectives. Comparisons with typical methods, centralized and distributed, demonstrate the advantage of our algorithm for both weighted and unweighted versions. This paper not only provides a useful tool for the MWVC problem in decentralized environments but also paves an effective way for distributed coordination and optimization that could be modeled as potential games.