引用本文:齐龙,李翔.网络分布式k路点覆盖的空间博弈方法[J].控制理论与应用,2026,43(2):239~248.[点击复制]
QI Long,LI Xiang.Spatial game approach for the distributed k-path vertex cover of networks[J].Control Theory & Applications,2026,43(2):239~248.[点击复制]
网络分布式k路点覆盖的空间博弈方法
Spatial game approach for the distributed k-path vertex cover of networks
摘要点击 155  全文点击 23  投稿时间：2023-11-09  修订日期：2025-05-23
查看全文  查看/发表评论  下载PDF阅读器   HTML
DOI编号  10.7641/CTA.2024.30734
  2026,43(2):239-248
中文关键词  复杂网络  k路点覆盖  空间博弈  分布式优化  强纳什均衡
英文关键词  complex networks  k-path vertex cover  spatial game  distributed optimization  strong Nash equilibrium
基金项目  
作者单位E-mail
齐龙 复旦大学,信息科学与工程学院,自适应网络与控制研究室 21110720115@m.fudan.edu.cn 
李翔* 同济大学,上海自主智能无人系统科学中心,复杂网络与智能系统研究所 lix2021@tongji.edu.cn 
中文摘要
      作为网络覆盖问题的重要分支, 许多真实世界复杂系统的难题可以被视为网络k路点覆盖问题. 在分布式系统中, 如何设计个体自主决策的去中心化策略是实现网络覆盖优化的关键. 本文将k路点覆盖问题建模为网络空间博弈, 其中每 个节点被当作是仅与邻居进行通信的理性个体. 在非合作博弈框架下, 分析了强纳什均衡(SONE)与k路点覆盖之间的关系, 同时提出的基于博弈的同步期望驱动算法(GSAA)可以在有限时间内收敛到4人联盟SONE, 结合仿真结果验证了算法的有 效性. 本文围绕k路点覆盖问题, 从联盟视角建立覆盖解与博弈均衡之间的关系, 为博弈框架下解决具有网络局部耦合约束 的分布式优化问题提供了一种全新思路.
英文摘要
      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.