欢迎访问《控制理论与应用》期刊网站！

网络分布式k路点覆盖的空间博弈方法

doi: 10.7641/CTA.2024.30734

齐龙¹ ，李翔²

1. 复旦大学信息科学与工程学院自适应网络与控制研究室, 上海 200433

2. 同济大学上海自主智能无人系统科学中心复杂网络与智能系统研究所, 上海 201210

基金项目: 国家自然科学基金区域创新发展联合基金项目(U23A20331)资助.

详细信息

作者简介

齐龙博士研究生,目前研究方向为多智能体博弈、分布式优化,E-mail: 21110720115@m.fudan.edu.cn;

李翔教授,博士生导师,研究领域为复杂网络科学与集群智能系统,E-mail: lix@fudan.edu.cn.

通信作者

李翔,E-mail: lix@fudan.edu.cn

Spatial game approach for the distributed k-path vertex cover of networks

QI Long¹ ， LI Xiang²

1. Adaptive Networks and Control Lab, School of Information Science and Technology, Fudan University, Shanghai 200433 , China

2. Institute of Complex Networks and Intelligent Systems, Shanghai Research Institute for Intelligent Autonomous Systems, Tongji University, Shanghai 201210 , China

Funds: Supported by the Joint Fund for Regional Innovation and Development of the National Natural Science Foundation of China (U23A20331).

摘要

作为网络覆盖问题的重要分支, 许多真实世界复杂系统的难题可以被视为网络k路点覆盖问题. 在分布式系统中, 如何设计个体自主决策的去中心化策略是实现网络覆盖优化的关键. 本文将k路点覆盖问题建模为网络空间博弈, 其中每个节点被当作是仅与邻居进行通信的理性个体. 在非合作博弈框架下, 分析了强纳什均衡(SONE)与k路点覆盖之间的关系, 同时提出的基于博弈的同步期望驱动算法(GSAA)可以在有限时间内收敛到4人联盟SONE, 结合仿真结果验证了算法的有效性. 本文围绕k路点覆盖问题, 从联盟视角建立覆盖解与博弈均衡之间的关系, 为博弈框架下解决具有网络局部耦合约束的分布式优化问题提供了一种全新思路.

关键词

复杂网络 / k路点覆盖 / 空间博弈 / 分布式优化 / 强纳什均衡

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 networks / k-path vertex cover / spatial game / distributed optimization / strong Nash equilibrium

1 引言 2 预备知识 2.1 k路点覆盖 2.2 分布式设定 3 博弈模型 4 博弈均衡与覆盖状态关系分析 5 分布式优化算法 6 仿真结果与分析 7 结束语

1 引言

通过将个体和彼此间的相互关系分别用节点和边表示，复杂网络可以用于抽象表示客观世界中复杂系统的结构特征 ^[1-2] . 在各种复杂系统中，存在许多具有挑战性的任务，它们可以被归纳为网络上的组合优化问题（combinatorial optimization problems，COP），例如人员调度、飞机座位分配、组合拍卖、生物网络分析和社交网络广告投放等 ^[3-5] . 当任务可以抽象为从网络中选取最优的一组元素覆盖整个网络（网络中的所有覆盖对象），那么这类 COP可以看作是网络覆盖问题. k路点覆盖问题（k-path vertex cover，VCP_k）将网络中所有k路径（包含k ≥ 2节点之路径）作为被覆盖对象，最优性问题旨在选择最少的一组节点覆盖所有 k路.

作为网络覆盖的关键问题，VCP_k具有较强的广泛性，应用领域包括网络安全与隐私协议 ^[6]、无线传感器网络的安全监测和部署问题 ^[7]、社交网络恶意消息监控 ^[8]、无线自组织网络的广播方案设计 ^[9] 和多处理器的同步 ^[10] 等.

为了更快地找到最小覆盖集合，一些学者提出多种分支和归约规则，以降低分支算法的时间复杂度 ^[11-14] . 然而，对于任意整数 k ≥ 2，VCP_k 都是 NPhard的，除非 P = NP，否则无法在多项式时间内被解决 ^[15]，面对大型网络时分支算法难以应用. 考虑到精确算法的局限性，启发式算法被当作替代方案 ^[16-20] . Papadimitriou等 ^[21]提出了著名的vercov近似算法，后续一些学者致力于降低近似比 ^[22-26] . 以上算法为集中式算法，需要一个中心处理器与其他节点进行通信，面对大量节点数据的传输和融合处理会有较高时延，且对计算性能有较高要求 ^[27] .

博弈论作为一个用于研究博弈群体策略决策的数学理论和方法 ^[28]，近年来被许多学者引入到VCP₂的分布式方法中. Yang等 ^[29]首次研究了在空间雪堆博弈下严格纳什均衡（strict Nash equilibrium，SNE）与覆盖状态间的关系. Wu等 ^[30]将空间雪堆博弈用于算法的局部搜索. Tang等 ^[31]针对加权网络建立了非对称博弈模型. Chen等 ^[32]设计了更一般的非对称博弈模型. Sun等 ^[33-34]将问题的目标函数作为势函数，建立了加权VCP₂的严格势博弈模型，其中个体效用函数变化量等于势函数的变化量，保证最优势函数策略组合与最优覆盖状态的对应关系 ^[35]. Chen等 ^[36]提出了时变二元对数线性学习算法（time-variant binary loglinear learning algorithm，TVBLLA）用于处理未加权的情况，将异步策略更新过程建模为马尔可夫链，分析随机稳定性. 另外，还有学者将前景理论应用于分布式方法中寻找SNE解^[37] . 上述工作围绕VCP₂提出了不同的基于博弈的分布式解决方案. 然而，目前仍未有针对k≥ 3研究提出的分布式解决方案.

本文将节点覆盖交互关系建模为网络空间博弈，提供VCP_k（k ≥ 3）的分布式解决方案. 个体考虑来自于联盟的收益，旨在描述联盟联合策略没有偏离动机的稳定状态，即强纳什均衡（strong Nash equilibrium，SONE）. 在此博弈下证明了f人联盟SONE介于最小k 路点覆盖和极小k路点覆盖状态之间. 另外，本文提出了基于博弈的同步期望驱动算法（game-based synchronous aspiration-driven algorithm，GSAA）用于解决 VCP_k. 一般地，在基于期望驱动的规则下，个体不再追求当下效用最大化，而是评估当前效用是否满足期望水平，若不满足则会转向其他策略 ^[38]. GSAA允许个体在与邻居交互过程中设定合适的期望，利用自评估机制更新自身策略.

本文主要贡献: 1）针对VCP_k，设计了适用于k ≥ 3 的分布式解决方案，提出了GSAA 用于更新个体策略; 2）探究了严格纳什均衡（SNE）和f人联盟强纳什均衡（SONE）与覆盖状态的关系; 3）证明了GSAA能够突破SNE，在有限时间内收敛到4人联盟SONE，结合仿真验证了算法的优越性.

2 预备知识

2.1 k路点覆盖

给定一个无向图（V，E），由节点集合V ={1，2，· · ·，n}和连边集合

E = \{e_{i ， j}\} （ i ， j \in V ， i \neq j ）

组成，无向图中的任意一条k路可以表示为包含k个不同节点和 k − 1条不同边的集合

p_{k} = \{i ， e_{i ， i + 1} ， i + 1 ， \dots ， i + k - - 1} （ k ⩽ n ） .

定义

P_{k} = \{p_{k}^{1} ， p_{k}^{2} \dots ， p_{k}^{n p_{k}}\}

为所有k路集合，当覆盖节点集合V ′ ⊆V 满足任意一条k路都被覆盖时，即

p_{k}^{i} \cap V^{'} \neq \emptyset ， \forall p_{k}^{i} \in P_{k} ，

则称其符合k路点覆盖状态VCP_k，状态集合用VVCP_k表示. 具有最小覆盖集合的VCP_k 被称为最小k 路点覆盖状态MVCP_k，状态集合可以表示为

V_{{M V C P}_{k}} : = \{V^{*} \in V_{{V C P}_{k}} : |V^{*}| ⩽ |V^{'}| ， \forall V^{'} \in V_{{V C P}_{k}}\} .

定义 1 针对无向图（V， E），假设覆盖节点集 V ′ ⊆ V 满足VCP_k，若其中任意一个覆盖节点变为未覆盖后不再满足VCP_k，则称V ′符合极小k路点覆盖状态 mVCP_k，状态集合表示为

V_{{m V C P}_{k}} : = \{V^{'} \in V_{{V C P}_{k}} : V^{'} ∖ {i} \notin V_{{V C P}_{k}} ， \forall i \in V^{'}\} .

针对k = 3，4的不同网络的3种覆盖状态如图1所示. 根据覆盖状态定义辅以图1示例，对于任意固定参数k，可知

V_{{M V C P}_{k}} \subseteq V_{{m V C P}_{k}} \subseteq V_{{V C P}_{k}} .

图1 k路点覆盖不同覆盖状态图

Fig.1Various cover states of k-path vertex cover

2.2 分布式设定

在分布式系统中，通常将连边的存在视为对应个体间能够通信. 考虑到没有连边的个体间可能存在耦合约束的情况，往往需要保证它们是连通的，信息得以传递 ^[39-40] . 对于VCP_k具有耦合约束的任意两个个体间一定是连通的.

假设 1 针对一个无向图（V， E），其中任意个体

i \in V

可以与其任意邻居

j \in N_{i}

交换信息，邻居集合定义为

N_{i} = {j \in V : d i s （ i ， j ） < k}

3 博弈模型

节点作为博弈者组成具有网络结构的博弈群体，即结构群体，个体策略选择受到局部邻居的直接影响 ^[41-42] . 本文将节点自主覆盖过程映射为博弈个体之间的博弈过程.

定义 2 对于无向图（V， E），可将 VCP_k 映射为空间博弈

G : = {(A_{i} ， U_{i}^{χ} ， P_{k} （ i ）)}_{i \in V} ，

其中:

1）V = {1，2，· · ·，n}为博弈个体集合，对应无向图的节点集合;

2） A_i = {C， D}为博弈个体 i ∈ V 的可行策略集合，a_i = C 表示个体 i 覆盖，a_i = D为不覆盖， ap ∈ AP为所有个体的策略组合，

A P = \prod_{i \in V} A_{i}

表示所有个体的策略组合空间;

3）

U_{i}^{χ}

为个体i的效用函数，其中

χ \in C_{f}

表示联盟，用

C_{f} = {χ \subseteq V : | χ | \in [1 ， f]}

表示最多

f ⩾ 1

个个体的联盟集合;

4）

P_{k} （ i ） = \{p_{k}^{x} \in P_{k} : p_{k}^{x} \cap {i} \neq \emptyset\}

表示个体i的所有k路集合.

在博弈G中，个体交互存在于k路和联盟中. 对于任意个体i ∈ V，若存在一条k路

p_{k ， i} \in P_{k} （ i ）

），没有覆盖个体，则其中包括i在内的所有个体的最优选择为覆盖; 反之，若个体i所处的所有k路都被其他个体覆盖了，则其最优选择为不覆盖. 若存在一种具有更少覆盖个体的联盟联合策略，且对于每个成员都是当前最优，则此联合策略从整体看是更优选择. 设计效用函数时，同时考虑了每条k路的累积收益和联盟收益

U_{i}^{χ} = \sum_{z = 1}^{n p_{k} (i)} u_{X} (p_{k, i}^{z}) + U_{X}^{c o} (χ, i),

(1)

其中: np_k（i）表示个体i所处的k路数; u_X（·）为选择策略X ∈ {C，D}时的k人博弈收益 ^[43]，

\{\begin{matrix} u_{C} (p_{k}^{x}) = b - \frac{c}{s_{p_{k}^{x}}}, \\ u_{D} (p_{k}^{x}) = b \times 1 (s_{p_{k}^{x}} > 0), \end{matrix}

(2)

其中: b，c为常参数;

S_{p_{k}^{x}}

为

p_{k}^{x}

中策略C个体数量; 1（·）表示指示函数.

U_{X}^{c o} （ χ ， i ）

为个体

i \in χ

的联盟收益，即

(3)

其中

n D （ χ ）

表示联盟

χ

中选择策略D的博弈者数量.若

χ = {i} ，

则来自联盟的影响为0. 用U_i表示个体i忽略联盟收益的效用，即

U_{i} = U_{i}^{{i}} = \sum_{z = 1}^{n p_{k} （ i ）} u_{X} (p_{k ， i}^{z}) .

博弈G中的联盟并不等同于合作博弈中联盟的概念. 在非合作博弈中，博弈者通常被设定为理性个体，追求自身收益最大化 ^[44] . 纳什均衡（Nash equilibrium，NE）作为非合作博弈基本的解概念，用于描述一种所有博弈个体的策略都是最佳响应（best response，BR）的状态^[45] . NE常被用于帮助预测和分析多人博弈中的个体行为和相互作用，例如拍卖行为和群体竞争.

定义 3 对于博弈G 中的任意个体

i \in V ，

若给定所有其他个体策略组合

a p_{- i} = {(a_{j})}_{j \in V ∖ {i}} ，

无法通过单方面改变策略提高自身效用，则对应的策略组合

a p^{*} \in A P

被看作是一个NE，即

U_{i} (a_{i}^{*}, a p_{- i}^{*}) ⩾ U_{i} (a_{i}^{'}, a p_{- i}^{*}) .

(4)

若式（4）为严格不等式，则称该博弈均衡是严格纳什均衡（strict NE，SNE）. SNE是一种个体策略改变对效用函数影响的表征，仅对于单个个体的策略偏离稳定，没有考虑联盟的概念. 然而在一些多人非合作博弈场景中，无法忽略联盟联合策略变化对成员的影响. 强纳什均衡（SONE）是一种考虑了联盟联合策略的博弈均衡，在此均衡下，个体不仅无法单方面提高自身效用，而且也无法在联盟中与其他成员共同提高效用 ^[46-47] .

定义 4 对于博弈G，若对于

\forall χ \in C_{f} ，

不存在任何联盟策略组合

a p_{χ}^{'} \in A P_{χ} = \prod_{j \in χ} A_{j}

能够满足

U_{i}^{χ} (a p_{χ}^{'}, a p_{- χ}^{*}) > U_{i}^{χ} (a p^{*}), \forall i \in χ,

(5)

则

a p^{*}

满足 f 人联盟 SONE，其中

a p_{- χ} = {(a_{j})}_{j \in V ∖ χ}

表示除联盟

χ

外其他个体联合策略.

定理 1 给定无向图（V，E），同时考虑两个 k 路点覆盖博弈: G 以及

G^{'} = {(A_{i} ， U_{i}^{'} ， P_{k} （ i ）)}_{i \in V} ，

其中

U_{i}^{'} = \sum_{z = 1}^{n p_{k} （ i ）} u_{X} (p_{k ， i}^{z}) .

若

b > \underset{i \in V}{m a x} \{n p_{k} （ i ）\} c > 0 ，

则博弈G′的f人联盟SONE 集合和SNE 集合相等，并且等于博弈G的SNE集合.

证 G′的f人联盟SONE集合和SNE集合分别用符号

V_{S O N E}^{'}

和

V_{S N E}^{'}

表示. G的SNE 集合表示为 V_SNE. 要证V_SNE =

V_{S N E}^{'}

，首先证明V_SNE ⊆

V_{S N E}^{'}

. 假设V^∗ ∈V_SNE，

V^{*} \notin V_{S N E}^{'} ， a p^{*}

为对应策略组合，则∃i ∈ V 有

U_{i}^{'} (a_{i}^{*} ， a p_{- i}^{*}) < U_{i}^{'} (a_{i}^{'} ， a p_{- i}^{*}) .

此时有

U_{X}^{c o} （ χ ， i ） = 0 ，

则

U_{i} (a_{i}^{*} ， a p_{- i}^{*}) < U_{i} (a_{i}^{'} ， a p_{- i}^{*}) ，

与SNE定义相悖，假设不成立，所以

V_{S N E} \subseteq V_{S N E}^{'} .

然后证

V_{S N E}^{'} \subseteq V_{S N E} .

类似地，由

U_{X}^{c o} （ χ ， i ） = 0

可得

V_{S N E}^{'} \subseteq V_{S N E} .

综上所述，

V_{S N E} = V_{S N E}^{'} .

由于f = 1时，

V_{S N E}^{'} = V_{S O N E}^{'}

一定成立. 不失一般性，设

f \in [2 ， n] .

要证明

V_{S N E}^{'} = V_{S O N E}^{'} ，

首先证明

V_{S N E}^{'} \subseteq V_{S O N E}^{'} .

假设

V^{*} \in V_{S N E}^{'} ，

且

V^{*} \notin V_{S O N E}^{'} ， a p^{*}

为对应策略组合. 对于

\forall χ \in C_{f} ， \exists i \in χ ， a_{i}^{*} = D

满足

\begin{matrix} U_{i}^{χ^{'}} (C, a p_{χ ∖ {i}}^{'}, a p_{- χ}^{*}) - U_{i}^{χ^{'}} (a p_{χ}^{*}, a p_{- χ}^{*}) = \\ (\sum_{l = 1}^{k} d_{l}^{'} - \sum_{l = 1}^{k - 1} d_{l}) b - \sum_{l = 1}^{k} \frac{d_{l}^{'} c}{k - l + 1} > 0, \end{matrix}

d_l和

d_{l}^{'}

分别表示当联合策略为ap^∗和ap′时，集合P_k（i）中具有（k − l）个选择策略C的其他个体的k路数量，其中

a p^{'} = (C, a p_{χ ∖ {i}}^{'}, a p_{- χ}^{*}),

则有

\sum_{l = 1}^{k} d_{l}^{'} - \sum_{l = 1}^{k - 1} d_{l} = n p_{k} (i) - \sum_{l = 1}^{k - 1} d_{l} ⩾ 1,

这与

V^{*} \in V_{S N E}^{'}

相悖，假设不成立. 假设

V^{*} \in V_{S O N E}^{'} ，

且

V^{*} \notin V_{S N E}^{'} ，

这与定义相悖. 综上，

V_{S N E}^{'} = V_{S O N E}^{'} .

证毕.

4 博弈均衡与覆盖状态关系分析

本节讨论博弈均衡与覆盖状态关系. 对于博弈G，用

V_{S O N E}^{f}

和VSNE分别表示f人联盟SONE和SNE对应的状态集合，其中f ∈ [1，n].

引理 1 对于 k 路点覆盖博弈 G，当满足 b >

\underset{i \in V}{m a x} \{n p_{k} （ i ）\} c > 0

时，SNE的充要条件为

1）若a_i = C，∀i∈V，则∃pk ∈ P_k（i），使得s_pk = 1;

2）若a_i= D，∀i∈V ，则∀p_k∈ P_k（i），都有s_pk>0.

f人联盟SONE的充要条件除了条件1）和2），还包括

3）对于

\forall χ \in C_{f} ，

若所有成员都策略取反，∀j ∈ V 依旧满足条件1）和2），则覆盖节点数量不会降低.

证首先证明SNE的充要条件.

充分性证明: 假设 ap′ ∈ AP 满足条件1）和2）. 对于∀i ∈ V ，设P_k（i）中具有（k − l）个选择策略C的其他个体的k路存在d_l条

1）当

a_{i}^{'} = C

时，其至少存在一条k路有s = 1，则

\begin{matrix} U_{i} (C, a p_{- i}^{'}) - U_{i} (D, a p_{- i}^{'}) > \\ d_{k} \underset{i \in V}{m a x} \{n p_{k} (i)\} c - \sum_{l = 1}^{k} d_{l} c ⩾ 0; \end{matrix}

2）当

a_{i}^{'} = D

时，对于其任意k路都满足s >0，则有

综上，

U_{i} (a_{i}^{'} ， a p_{- i}^{'}) > U_{i} (a_{i}^{''} ， a p_{- i}^{'}) ，

则ap′是SNE.

必要性证明: 假设 ∃ ap′ ∈ AP是SNE，设P_k（i）中具有（k − l）个选择策略C的其他个体的k路存在d_l条

1）当

a_{i}^{'} = C

时，有

\begin{matrix} U_{i} (C, a p_{- i}^{'}) - U_{i} (D, a p_{- i}^{'}) > \\ d_{k} \underset{i \in V}{m a x} \{n p_{k} (i)\} c - \sum_{l = 1}^{k} \frac{d_{l} c}{k - l + 1} > 0, \end{matrix}

可得

d_{k} ⩾ 1 .

因此，

\exists p_{k}^{x} \in P_{k} （ i ） ，

使得

s_{p_{k}^{x}} = 1;

2）当

a_{i}^{'} = D

时，有

\begin{matrix} U_{i} (D, a p_{- i}^{'}) - U_{i} (C, a p_{- i}^{'}) > \\ \sum_{l = 1}^{k} \frac{d_{l} c}{k - l + 1} - d_{k} \underset{i \in V}{m a x} \{n p_{k} (i)\} c > 0, \end{matrix}

可得d_k= 0. 因此，

\forall p_{k}^{x} \in P_{k} （ i ）

都有

s_{p_{k}^{x}} > 0 .

接下来，证明f人联盟SONE的充要条件.

充分性证明: 假设 ∃ ap′ ∈ AP，满足条件1）–3）. 对于联盟

χ ，

设存在fc个合作者，f d个非合作者，

f c + f d ⩽ f ，

用

a p_{χ}^{''} = - a p_{χ}^{'}

表示

χ

所有成员取反策略组合. 设

i n v （ χ ）

为联盟取反个体数量:

1）当inv

（ χ ） = | χ | ⩽ f

时，所有成员都取反策略，一定有

\exists i \in χ ， a_{i}^{'} = C

是最佳响应，假设联盟策略都取反后，

a_{i}^{''} = D

依旧是最佳响应，设取反前后P_k（i）中具有（k − l）个选择策略C的其他个体的k路分别存在d_l和

d_{l}^{'}

条，有

U_{i}^{χ} (a p_{χ}^{''} ， a p_{- χ}^{'}) - U_{i}^{χ} (a p_{χ}^{'} ， a p_{- χ}^{'}) = \sum_{l = 1}^{k} d_{l} (\frac{c}{k - l + 1}) + （ f c - f d - 1 ） n p_{k} （ i ） c ⩽ 0 ，

此时联盟联合策略都取反后，无法满足

U_{i}^{χ} (a p_{χ}^{''}, a p_{- χ}^{'}) > U_{i}^{χ} (a p^{'}), \forall i \in χ;

(6)

2）当 inv

（ χ ） = y < | χ |

时，存在 y 个取反的个体，组成的子联盟

χ^{'} \subset χ^{'}

无法满足式（6）.

因此，对于

\forall χ \in C_{f} ，

不存在ap_χ满足式（6）. 综上，ap′是f人联盟SONE.

必要性证明: 假设 ∃ ap′ ∈ AP是f人联盟SONE，

\forall χ \in C_{f} ，

若所有成员策略取反ap′为SNE，则

\exists i \in χ ， a_{i}^{'} = C ，

一定有

U_{i}^{χ} (a p_{χ}^{''} ， a p_{- χ}^{'}) - U_{i}^{χ} (a p_{χ}^{'} ， a p_{- χ}^{'}) = \sum_{l = 1}^{k} d_{l} (\frac{c}{k - l + 1}) + （ f c - f d - 1 ） n p_{k} （ i ） c ⩽ 0 ，

则

f c - f d ⩽ 0 .

因此，当联盟成员策略全部取反后，策略D个体数量降低或不变，即覆盖节点数量不会降低.

证毕.

定理 2 对于k路点覆盖博弈G，若参数满足b >

\underset{i \in V}{m a x} \{n p_{k} （ i ）\} c > 0 ，

则有

V_{M V C P k} \subseteq V_{S O N E}^{f} \subseteq V_{S N E} = V_{m V C P k} \subseteq V_{V C P k}

证先证

V_{M V C P k} \subseteq V_{S O N E}^{f} .

假设

V^{*} \in V_{M V C P k} ，

且

V^{*} \notin V_{S O N E}^{f} ， a p^{*}

为对应策略组合，对于

\forall χ \in C_{f} ， f \in [1 ， n] ，

一定

\exists i \in χ ， a_{i}^{*} = C ，

使得

\exists a p_{χ}^{'} \in A P_{χ} ，

有

\begin{matrix} U_{i}^{χ} (D, a p_{χ ∖ {i}}^{'}, a p_{- χ}^{*}) - U_{i}^{χ} (a p_{χ}^{*}, a p_{- χ}^{*}) = \\ (\sum_{l = 1}^{k - 1} d_{l}^{'} - \sum_{l = 1}^{k} d_{l}) b + \sum_{l = 1}^{k} \frac{d_{l} c}{k - l + 1} + \\ (n D^{'} (χ) - 1) n p_{k} (i) c \times 1 (\forall p_{k}^{x} \in P_{k} (i) : \\ s_{p_{k}^{x}} > 0) - n D (χ) n p_{k} (i) c \times 1 (\exists p_{k}^{x} \in \\ P_{k} (i) : s_{p_{k}^{x}} = 1) > 0, \end{matrix}

(7)

d_l和

d_{l}^{'}

分别表示当联合策略为ap^∗和ap′时，P_k（i）中具有（k − l）个选择策略C的其他个体的k路数量，其中

a p^{'} = (D ， a p_{χ ∖ {i}}^{'} ， a p_{- χ}^{*}) ， n D^{'} （ χ ）

为对应新联合策略下联盟中选择策略D的个体数量. 若

χ = {i} ，

式（7）不成立. 因此，给定

a p_{- i}^{*} ， i

的最佳响应为C.

若

i \in χ

且

| χ | > 1 ，

给定

a p_{- i} = (a p_{χ ∖ {i}}^{'} ， a p_{- χ}^{*}) ，

a_i= C是最佳响应，则式（7）不成立; 若a_i= D是最佳响应，有

n D^{'} （ χ ） > n D （ χ ） ，

这与

V^{*} \in V_{M V C P k}

相悖.因此

V_{M V C P k} \subseteq V_{S O N E}^{f} .

然后证明

V_{S O N E}^{f} \subseteq V_{S N E} .

假设

V^{*} \in V_{S O N E}^{f} ，

且

V^{*} \notin V_{S N E} ，

则对应策略组合ap^∗不满足引理1的条件 1）和2），这与

V^{*} \in V_{S O N E}^{f}

相悖，则有

V^{*} \in V_{S N E} .

根据定义 3和引理 1可知，SNE 的充要条件等价于mVCP_k状态，且mVCP_k满足VCP_k状态，所以有 V_SNE=

V_{m V C P k} \subseteq V_{V C P k}

. 证毕.

注 1 目前针对VCP₂存在多种基于博弈的分布式方案，模型包括空间雪堆博弈 ^[29] 和势博弈 ^[33-34，36] . 根据引理1，现存模型SNE的充要条件与本文模型G的SNE等价.

5 分布式优化算法

本节提出了一种全新的基于博弈的同步期望驱动算法（GSAA），算法允许个体间同步更新策略，并且能够在有限时间内收敛到4人联盟SONE.

在期望驱动机制下，若个体效用达到期望水平则重复当前策略，否则将会试图转向另一策略 ^[38] . 用

N_{i}^{+}

表示个体i及其邻居集合. 对于个体i，k距离以内的联盟

χ \subseteq N_{i}^{+}

所有成员策略转移产生的代价为

{S C}_{i} (χ) = U_{i}^{χ} (a p_{χ}, a p_{- χ}) - U_{i}^{χ} (- a p_{χ}, a p_{- χ}),

(8)

其中−ap_χ表示χ中所有成员转移为另一个策略（策略取反）. 若χ = i，则上式表示为 i 自身策略转移代价，用符号SISC（i）= SC_i（i）表示; 若SISC（i）>0，则此时a_i为最佳响应，即

a_{i} = a r g \underset{\tilde{a_{i}} \in A_{i}}{m a x} (U_{i} (\tilde{a_{i}} ， a p_{- i})) ，

反之，则有SISC（i）<0. SISC = 0的情况不做讨论.

用

ϕ_{i} = \{j \in N_{i} : {S C}_{j} （ i ） > S I S C （ i ） > 0\}

表示i转向非最佳响应时，拥有比其自身转移代价更大代价的个体集合. 转向非最佳响应时对i造成比其自身更大转移代价的个体集合为

ψ_{i} = \{j \in N_{i} : {S C}_{i} （ j ） > S I S C （ j ） > 0} .

对个体

i \in ψ_{j} ，

用

ω_{i} （ j ） = \{y \in N_{i} : {S C}_{i} （ i ， j ， y ） > 0 ， j \in ϕ_{i} \cap ϕ_{y}\}

表示与 j 有相同转移代价关系的邻居集合，并且三者同时策略转移后i的效用降低. 对于任意个体i ∈ V，期望AU_i定义为

(9)

其中:

X_{i} = n p_{k} （ i ） c \times 1 (m_{i} ⩾ M) ， M

是常参数，m_i在每个时步都进行更新，即

(10)

个体通过自评估当前效用与期望的关系更新策略

(11)

其中:

U_{i} = U_{i} (a_{i}^{t} ， a p_{- i}^{t})

表示个体i在t时刻的效用水平，p ∈（0，1）为概率. 具体算法流程如表1所示.

表1基于博弈的同步期望驱动算法GSAA

Table1Game-based synchronous aspiration-driven algorithm (GSAA)

引理 2 给定博弈

G = {(A_{i} ， U_{i}^{χ} ， P_{k} （ i ）)}_{i \in V} ，

满足

b > \underset{i \in V}{m a x} \{n p_{k} （ i ）\} c > 0 .

假设ap满足SNE状态，∀i∈V，若

ϕ_{i} \neq \emptyset ，

使得

|ψ_{j}| = |ω_{i} （ j ）| + 1 ， \forall j \in ϕ_{i} ，

则ap是4 人联盟SONE.

证若

ϕ_{i} \neq \emptyset ，

假设a_i =D，则

\forall j \in ϕ_{i} ， {S C}_{j} （ i ） ⩽

0，假设不成立，因此a_i = C. 设P_k（i）中具有（k − l）个选择策略C的其他个体的k路存在d_l条，对于∀j ∈ ϕ_i，假设与i的共同k路中具有（k − q）个包括i在内的选择策略C的其他个体的k路存在dd_q条.

1）当a_j=D且

j \notin ϕ_{i}

时，有

S I S C （ i ） ⩾ {S C}_{j} （ i ） ，

可得

d_{k} > d d_{k - 1} . i ， j

策略转移后，P_k（i）中未满足覆盖的 k路大于P_k（j）中除j外没有策略C个体的k路，则还至少需要一个其他策略D个体转向C才能满足SNE;

2）当a_j=D且j ∈ ϕ_i时，若ω_i（j）=∅，有SC_j（i）>SISC（i），

d d_{k - 1} b > d_{k} b - \sum_{q = 1}^{k} \frac{d_{l} c}{k - l + 1} ，

可得dd_k₋₁ = d_k，则 i， j 转移策略后有SISC（i），SISC（j）>0，其他策略C个体策略转移后，不再满足SNE. 若

ω_{i} （ j ） \neq \emptyset ，

对于

\forall y \in ω_{i} （ j ）

有SC_i（i，j，y）>0，有

\begin{matrix} U_{i}^{{i, j, y}} (a p_{{i, j, y}}, a p_{- {i, j, y}}) > \\ U_{i}^{{i, j, y}} (- a p_{{i, j, y}}, a p_{- {i, j, y}}), \end{matrix}

(12)

其中ap_{_i_，_j_，_y_} =（C，D，C）. 此时

\forall y \in ψ_{j} ∖ {i}

都满足式（12）. 此时至少需要一个其他策略D个体策略转移才能满足SNE. 假设

y \notin ω_{i} （ j ）

且a_y = C，若

y \in N_{j} ∖ ψ_{j} ，

等同于情况1）; 若

y \notin N_{j} ，

则i，j，y策略转移后一定不满足SNE;

3）当a_j = C时，若

ϕ_{j} = \emptyset ，

根据情况1）和2）可知，至少需要3个策略D个体与i，j同时策略转移才能满足SNE. 若

ϕ_{j} \neq \emptyset ，

根据情况2）可知，至少需要两个策略D个体与i，j同时策略转移才能满足SNE.

若

ϕ_{i} = \emptyset ，

上述情况1）的讨论过程一致，情况2）不存在. 情况3）当a_j= C，至少需要3个策略D个体与i，j同时策略转移才能满足SNE.

对于SNE状态ap，若∃x ⊆ V 使得所有成员策略都取反，依然满足SNE，那么对于其中任意成员，x中一定有其邻居，即∀i ∈ x，∃j ∈ N_i，j ∈ x. 综上，ap满足 4 人联盟SONE的充要条件. 证毕.

定理 3 给定博弈

G = {(A_{i} ， U_{i}^{χ} ， P_{k} （ i ）)}_{i \in V} ，

满足

b > \underset{i \in V}{m a x} \{n p_{k} （ i ）\} c > 0 ， M ⩾ 1 ，

算法 GSAA可以在有限时间内收敛到4人联盟强纳什均衡.

证首先证明当

X_{i} = n p_{k} （ i ） c

时，对于∀i ∈ V ，若 a_i为最佳响应，则

U_{i} ⩾ A U_{i} ，

若−a_i为最佳响应，则U_i<AU_i . 分以下几种情况讨论，∀i ∈ V 有

1）当

ϕ_{i} = \emptyset ， {S C}_{j} （ i ） > S I S C （ i ） ， \forall j \in N_{i} ，

期望为

A U_{i} = n p_{k} （ i ） b

则SISC（i）<0，有−a_i为最佳响应，假设U_i =AU_i，则a_i =D 并且 SISC（i）>0，这与ϕ_i =∅ 相悖，此种情况不存在，那么有U_i<AU_i;

2）当

ϕ_{i} \neq \emptyset ， A U_{i} = n p_{k} （ i ） （ b - c ） ，

则SISC（i）>0，此时a_i为最佳响应，假设U_i <AU_i，一定有SISC（i）<0，这与条件相悖，那么有

U_{i} ⩾ A U_{i};

3）当

ϕ_{i} = \emptyset ， {S C}_{j} （ i ） ⩽ S I S C （ i ） ， \exists j \in N_{i} ，

期望为

A U_{i} = n p_{k} （ i ） （ b - c ） .

当a_i为最佳响应时，则有

U_{i} ⩾

AU_i . 当−a_i为最佳响应时，假设 a_i= C，则有

{S C}_{j} （ i ） ⩾ 0 ， \forall j \in N_{i} ，

则SISC（i）>0，这与条件相悖，此情况不存在，假设a_i = D，一定有U_i <AU_i .

若个体未达到最佳响应，上述情况2）不存在，则以p >0的概率转向最佳响应. 若个体当前策略为最佳响应，只有满足情况2）条件并且所有邻居策略都为最佳响应的个体在X = 0时才会转移策略，而其他个体一定不会转移策略.

定义

{\{a p^{t}\}}_{t ⩾ 1}

为算法1的动作组合时间序列，考虑到p >0，对于∀i ∈ V 给定任意ap₋_i∈ AP，一定存在

\tilde{T} \in N_{+} ，

使得若ap重复博弈

T + 1 ⩾ \tilde{T} + M

次，即

a p^{τ} = a p ， τ \in [t ， t + T] ，

有

U_{i} ⩾ A U_{i}^{t + T} ，

且有

a_{i}^{t + T} = a r g \underset{{\tilde{a}}_{i} \in A_{i}}{m a x} (U_{i} ({\tilde{a}}_{i} ， a p_{- i})) ，

此时为“锁定状态”. 若

ϕ_{i} \neq \emptyset ， \forall i \in V ，

有

m_{i}^{τ} ⩾ M ， τ ⩾ t + M - 1 ，

根据引理 2，

a p^{τ} = a p^{*} ， \forall τ \in [t + M - 1 ， + \infty ） ，

锁定为4人联盟 SONE.

假设任意状态策略组合ap₀ ∈ AP重复T₁<T+ 1次后，i在T₁时刻选择最佳响应，此事件发生的概率至少是ρ₁ =p（1 − p）²ⁿ^（^T^+1） >0，最多重复|AP|次后得到的策略组合

a p^{t_{0}}

一定是SNE. 然后假设

a p^{t_{0}}

重复 T₂<T + 1次后，对于个体j，满足

\exists i \in ψ_{j} ， m_{i}^{t_{0} + T_{2}}

< M，则i ∈ ψ_j在t₀ + T₂时刻转移策略，此事件发生的概率至少为ρ₂ = p（1 − p）ⁿ^（^T^+1）>0，得到

a p^{t_{1}} .

假设

a p^{t_{1}} .

重复T₃ <T + 1次后，个体j在t₁ + T₃时刻转向最佳响应，事件概率至少是

ρ_{3} = p （ 1 - p ）^{2 n （ T + 1 ）} > 0 ，

得到

a p^{t_{2}} .

然后假设

a p^{t_{2}} .

重复T₄ <T + 1次后，∃y ∈

ψ_{j} ∖ ⋃_{z \in Z} ω_{z} （ j ）

在t₂ + T₄时刻转向最佳响应，事件概率至少是

ρ_{4} = p （ 1 - p ）^{2 n （ T + 1 ）} > 0 ，

此顺序事件最多重复

|ψ_{j}| - 1

次，得到

a p^{t_{3}}

为SNE，其中

Z = {i ， \dots} \subseteq

ψ_j按照事件顺序形成个体集合. 随后，假设

a p^{t_{3}}

保持 T + 1次不变，使得若

ϕ_{j} \neq \emptyset ，

则

m_{i}^{τ} ⩾ M ， τ ⩾ t_{3} + T

此事件发生的概率至少为

ρ_{5} = （ 1 - p ）^{n （ T + 1 ）}

，得到

a p^{t_{4}}

为SNE.

上述从t₀到t₄的过程最多重复n次，得到策略组合ap^∗是4人联盟SONE. ap⁰ → ap^∗ 的概率下界ρ =

ρ_{1}^{| \vec{A P} |} \prod_{j \in V} (ρ_{2} ρ_{3} ρ_{5} ρ_{4}^{|ψ_{j}| - 1})

一定大于0. 证毕.

6 仿真结果与分析

本节验证GSAA的性能. 针对VCP_k分别进行多次独立实验，根据统计结果分析. 实验目标函数设为

F (Y) = \sum_{i = 1}^{n} [y_{i} + n \sum_{p_{k}^{z} \in P_{k} (i)} 1 (s_{p_{k}^{z}} = 0)],

(13)

其中: Y 为覆盖解; y_i= 1表示节点i属于覆盖集合，反之y_i = 0. F（Y）越小表示解Y 越优. 当满足条件b >

\underset{i \in V}{m a x} \{n p_{k} （ i ）\} c > 0 ， b ， c

的取值对算法性能没有影响，参数设为

b = 2 c \underset{i \in V}{m a x} \{n p_{k} （ i ）\} + 1 ， c = 0.1

针对 VCP₃ 验证算法有效性，在网格（Grid）网络、Barabási-Albert（BA）无标度网络 ^[48]、Erdős-Rényi（ER）随机网络 ^[49]和Watts-Strogatz（WS）小世界网络 ^[50]进行仿真实验. Grid网络为两条k路的笛卡尔积，BA无标度网络的度分布遵从幂律分布，WS小世界网络的构造从环状最近邻耦合网络开始，以p_ws的概率断边重连，具有较小平均距离Ad和较高聚类系数Cc. 仿真所用的 WS小世界网络满足 Ad（p_ws）/Ad（0）∈（0.1，0.21）和Cc（p_ws）/Cc（0）∈（0.7，0.91）. 将算法参数设为M =[20 30 60 100]，p=[0.2 0.4 0.6 0.8]，在 500节点Grid网络，1000节点平均度为4的BA无标度，ER随机和WS小世界网络上独立运行50次. 用Ac和At 分别表示平均覆盖节点数和平均运行时间（s）. 结果如图2所示，对于Grid网络， M保持不变，p 越大平均覆盖数越少. 对于BA无标度网络，p = 0.6和0.8对于覆盖结果差距并不明显. 对于ER随机和WS小世界网络，当p = 0.6时平均覆盖数最少.

图2不同参数M和p值VCP₃的实验结果

Fig.2Experimental results of VCP₃ with different values of parameters M and p

根据不同参数实验结果设置合适的GSAA参数，对于Grid和WS小世界网络（M，p）=（60，0.6），对于 BA无标度和ER随机网络（M，p）=（30，0.6）. 每个算法在不同图上独立运行50次得到F（Y）统计数据和平均运行时间（s）. 对比结果如表2所示，与MSIG相比，GSAA在仅获取局部信息的情况下，在BA，ER和WS 网络上具有明显的优势，能够用更少的耗时获得更优的覆盖解. 与MBR相比，GSAA 在所有仿真网络上都更具有优势，这得益于算法允许个体考虑联盟收益，能够收敛到4人联盟SONE，而MBR仅能保证收敛到 SNE.

表2各算法在不同图上的实验结果（VCP₃）: 最小/ 平均/最大F（Y）、标准差/平均运行时间

Table2Experimental results of various algorithms on different graphs for VCP₃: minimum/average/ maximum F (Y) , standard deviation/average runtime

为进一步验证GSAA的性能，针对特例k = 2的情况，将GSAA与其他算法进行对比. 对比算法及参数如下:（分布式）MBR ^[29]（参数: 记忆长度l = 200，针对 WS网络 l = 25）;（分布式）基于记忆的启发式加权算法（heuristic weighted memory-based algorithm，HWMA）^[34]（参数: 惩罚系数λ = 1，记忆长度l = 200，对于BA1000<4>，BA1000<8>， l=100，60）;（分布式）时变二元对数线性学习算法（time-variant binary loglinear learning algorithm，TVBLLA）^[36]（参数: 不同网络的参数向量c = [2e−2 4e−3 2e−3 7e−5 7e−5 6e−4 3.6e−4 1e−3 4.8e−4]，迭代时步ts= 8e+ 7）;（集中式）基于博弈的模因算法（game-based memetic algorithm，GMA）^[30]（参数: 总群体大小m_size = 100，最大代数g_max = 100，突变概率m_r= 1/n，成本效益比r = 0.001，局部进化次数le= 10）.

GSAA参数设置: Grid网络（M，p）=（100，0.6），BA 无标度网络（M，p）=（60，0.4），ER随机网络（M，p）=（60，0.6），WS小世界网络（M，p）=（30，0.6）. 实验结果如表3所示，与其他分布式算法相比，GSAA在所有网络上均能够获得更优的结果，并且平均运算时间是最少的. 与集中式算法GMA相比，对于除了Grid网络外的其它网络，GSAA仅用其20%以内的运行时间就能获得更优的覆盖集.

针对k = 2，3，将GSAA与其他算法在不同网络上进行对比. GSAA在仅采用局部信息的前提下，相较于集中式算法具有更强实用性的同时，在多数网络中以更快速度得到更优解. 另外，GSAA能够突破SNE，较其他分布式算法性能更卓越.

表3各算法在不同图上的实验结果（VCP₂）: 最小/平均/最大F（Y）、标准差/平均运行时间

Table3Experimental results of various algorithms on different graphs for VCP₂: minimum/average/ maximum F (Y) , standard deviation/average runtime

7 结束语

本文针对VCP_k设计了一种基于空间博弈的分布式方案，将个体之间的覆盖交互建模为空间博弈，个体组成的结构群体作为博弈群体，个体仅与邻居相互交互以完成覆盖任务. 博弈模型为分析覆盖状态和博弈均衡之间的关系提供了一种全新视角. 另外，提出的算法GSAA允许个体同步更新策略，并能够在有限时间内收敛到4人联盟SONE，较SNE具有更严格的充要条件. 通过仿真验证了GSAA的有效性和优越性. 在实际应用中，信息需要多跳传递，随着k的增加，节点间的通信成本也随之增加，并且还会面临时延变大的风险，这是未来亟需解决的问题.

图2不同参数M和p值VCP₃的实验结果

Fig.2Experimental results of VCP₃ with different values of parameters M and p

下载: 全尺寸图片

表1基于博弈的同步期望驱动算法GSAA

Table1Game-based synchronous aspiration-driven algorithm (GSAA)

下载: 全尺寸图片

表2各算法在不同图上的实验结果（VCP₃）: 最小/ 平均/最大F（Y）、标准差/平均运行时间

Table2Experimental results of various algorithms on different graphs for VCP₃: minimum/average/ maximum F (Y) , standard deviation/average runtime

下载: 全尺寸图片

表3各算法在不同图上的实验结果（VCP₂）: 最小/平均/最大F（Y）、标准差/平均运行时间

Table3Experimental results of various algorithms on different graphs for VCP₂: minimum/average/ maximum F (Y) , standard deviation/average runtime

下载: 全尺寸图片

图2不同参数M和p值VCP₃的实验结果

Fig.2Experimental results of VCP₃ with different values of parameters M and p

表1基于博弈的同步期望驱动算法GSAA

Table1Game-based synchronous aspiration-driven algorithm (GSAA)

表2各算法在不同图上的实验结果（VCP₃）: 最小/ 平均/最大F（Y）、标准差/平均运行时间

Table2Experimental results of various algorithms on different graphs for VCP₃: minimum/average/ maximum F (Y) , standard deviation/average runtime

表3各算法在不同图上的实验结果（VCP₂）: 最小/平均/最大F（Y）、标准差/平均运行时间

Table3Experimental results of various algorithms on different graphs for VCP₂: minimum/average/ maximum F (Y) , standard deviation/average runtime

图(1) / 表(3)

引用本文

齐龙, 李翔. 网络分布式k路点覆盖的空间博弈方法. 控制理论与应用, 2026, 43(2): 239 – 248

复制

QI Long, LI Xiang. Spatial game approach for the distributed k-path vertex cover of networks. Control Theory & Applications, 2026, 43(2): 239 – 248

Copy

计量

图2不同参数M和p值VCP₃的实验结果

Fig.2Experimental results of VCP₃ with different values of parameters M and p

表1基于博弈的同步期望驱动算法GSAA

Table1Game-based synchronous aspiration-driven algorithm (GSAA)

表2各算法在不同图上的实验结果（VCP₃）: 最小/ 平均/最大F（Y）、标准差/平均运行时间

Table2Experimental results of various algorithms on different graphs for VCP₃: minimum/average/ maximum F (Y) , standard deviation/average runtime

表3各算法在不同图上的实验结果（VCP₂）: 最小/平均/最大F（Y）、标准差/平均运行时间

Table3Experimental results of various algorithms on different graphs for VCP₂: minimum/average/ maximum F (Y) , standard deviation/average runtime

MAKSE H A, HAVLIN S, STANLEY H E. Modelling urban growth patterns. Nature,1995,377(6550):608-612.

MILO R, ITZKOVITZ S, KASHTAN N,et al. Superfamilies ofevolved and designed networks. Science,2004,303(5663):1538-1542.

GOTTLOB G, GRECO G. Decomposing combinatorial auctions and set packing problems. Journal of the ACM(JACM),2013,60(4):1-39.

WANG X, CHOI T M, LIU H,et al. Novel ant colony optimization methods for simplifying solution construction in vehicle routing problems. IEEE Transactions on Intelligent Transportation Systems,2016,17(11):3132-3141.

MORSTYN T. Annealing-based quantum computing for combinatorial optimal power flow. IEEE Transactions on Smart Grid,2022,14(2):1093-1102.

NOVOTNÝ M. Design and analysis of a generalized canvas protocol. The 4th IFIP WG 11.2 International Workshop, WISTP 2010. Passau, Germany: Springer,2010:106-121.

WEIGT M, HARTMANN A K. Number of guards needed by a museum: A phase transition in vertex covering of random graphs. Physical Review Letters,2000,84(26):6118-6121.

ZHOU J, CAO Z, DONG X,et al.4S: A secure and privacypreserving key management scheme for cloud-assisted wireless body area network in m-healthcare social networks. Information Sciences,2015,314:255-276.

AGATHOS S, PAPAPETROU E. On the set cover problem for broadcasting in wireless ad hoc networks. IEEE Communications Letters,2013,17(11):2192-2195.

BHATTACHARYYA S S, SRIRAM S, LEE E A. Resynchronization for multiprocessor DSP systems. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications,2000,47(11):1597-1609.

XIAO M, NAGAMOCHI H. Exact algorithms for maximum independent set. Information and Computation,2017,255:126-146.

CHANG M S, CHEN L H, HUNG L J. Moderately exponential time algorithms for the maximum induced matching problem. Optimization Letters,2015,9:981-998.

FOMIN F V, GASPERS S, KRATSCH D,et al. Iterative compression and exact algorithms. Theoretical Computer Science,2010,411(7/9):1045-1053.

FERNAU H. Parameterized algorithmics for d-hitting set. International Journal of Computer Mathematics,2010,87(14):3157-3174.

TU J, ZHOU W. A primal-dual approximation algorithm for the vertex cover P3 problem. Theoretical Computer Science,2011,412(50):7044-7048.

DORIGO M, MANIEZZO V, COLORNI A. Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man,and Cybernetics, Part B(Cybernetics),1996,26(1):29-41.

CHANG W L, REN T T, FENG M. Quantum algorithms and mathematical formulations of biomolecular solutions of the vertex cover problem in the finite-dimensional hilbert space. IEEE Transactions on Nanobioscience,2014,14(1):121-128.

QUAN C, GUO P. A local search method based on edge age strategy for minimum vertex cover problem in massive graphs. Expert Systems with Applications,2021,182:115185.

WANG Y, PAN S, AL-SHIHABI S,et al. An improved configuration checking-based algorithm for the unicost set covering problem. European Journal of Operational Research,2021,294(2):476-491.

ZHANG W, TU J, WU L. A multi-start iterated greedy algorithm for the minimum weight vertex cover P3 problem. Applied Mathematics and Computation,2019,349:359-366.

PAPADIMITRIOU C H, STEIGLITZ K. Combinatorial Optimization: Algorithms and Complexity. Chelmsford, MA, USA: Courier Corporation,1998.

KARAKOSTAS G. A better approximation ratio for the vertex cover problem. International Colloquium on Automata, Languages,and Programming. Berlin, Heidelberg: Springer,2005:1043-1050.

KARDOŠ F, KATRENIČ J, SCHIERMEYER I. On computing the minimum 3-path vertex cover and dissociation number of graphs. Theoretical Computer Science,2011,412(50):7009-7017.

BREŠAR B, KARDOŠ F, KATRENIČ J,et al. Minimum k-path vertex cover. Discrete Applied Mathematics,2011,159(12):1189-1195.

HALPERIN E. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM Journal on Computing,2002,31(5):1608-1623.

TU J, ZHOU W. A primal-dual approximation algorithm for the vertex cover P3 problem. Theoretical Computer Science,2011,412(50):7044-7048.

CAMISA A, NOTARNICOLA I, NOTARSTEFANO G. Distributed primal decomposition for large-scale MILPs. IEEE Transactions on Automatic Control,2021,67(1):413-420.

VON NEUMANN J, MORGENSTERN O. Theory of Games and Economic Behavior. Princeton, USA: Princeton University Press,1944.

YANG Y, LI X. Towards a snowdrift game optimization to vertex cover of networks. IEEE Transactions on Cybernetics,2013,43(3):948-956.

WU J, SHEN X, JIAO K. Game-based memetic algorithm to the vertex cover of networks. IEEE Transactions on Cybernetics,2018,49(3):974-988.

TANG C, LI A, LI X. Asymmetric game: A silver bullet to weighted vertex cover of networks. IEEE Transactions on Cybernetics,2017,48(10):2994-3005.

CHEN J, LUO K, TANG C,et al. Optimizing polynomial-time solutions to a network weighted vertex cover game. IEEE/CAA Journal of Automatica Sinica,2022,10(2):512-523.

SUN C, SUN W, WANG X,et al. Potential game theoretic learning for the minimal weighted vertex cover in distributed networking systems. IEEE Transactions on Cybernetics,2018,49(5):1968-1978.

SUN C, QIU H, SUN W,et al. Better approximation for distributed weighted vertex cover via game-theoretic learning. IEEE Transactions on Systems, Man,and Cybernetics: Systems,2021,52(8):5308-5319.

JALEEL H, SHAMMA J S. Path to stochastic stability: Comparative analysis of stochastic learning dynamics in games. IEEE Transactions on Automatic Control,2020,66(11):5253-5268.

CHEN J, LI X. Toward the minimum vertex cover of complex networks using distributed potential games. Science China Information Sciences,2023,66(1):112205.

LI X, CHEN J, YUAN Q. Adaptive vertex cover of dynamical networks with prospect theoretic perspective. IEEE Transactions on Network Science and Engineering,2022,9(6):4159-4170.

ZHOU L, WU B, DU J,et al. Aspiration dynamics generate robust predictions in heterogeneous populations. Nature Communications,2021,12(1):3250.

TATARENKO T, TOURI B. Non-convex distributed optimization. IEEE Transactions on Automatic Control,2017,62(8):3744-3757.

TESTA A, NOTARSTEFANO G. Generalized assignment for multirobot systems via distributed branch-and-price. IEEE Transactions on Robotics,2021,38(3):1990-2001.

NOWAK M A, BONHOEFFER S, MAY R M. Spatial games and the maintenance of cooperation. Proceedings of the National Academy of Sciences,1994,91(11):4877-4881.

WANG Long, HUANG Feng. An interdisciplinary survey of multiagent games,learning,and control. Acta Automatica Sinica,2023,49(11):580-613.(王龙, 黄锋. 多智能体博弈、学习与控制. 自动化学报,2023,49(11):580-613.)

SOUZA M O, PACHECO J M, SANTOS F C. Evolution of cooperation under N-person snowdrift games. Journal of Theoretical Biology,2009,260(4):581-588.

NASH J. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences of the United States of America,1950,36(1):48-49.

FUDENBERG D, TIROLE J. Game Theory. Cambridge, USA: MIT Press,1991.

CLEMPNER J B, POZNYAK A S. Computing the strong Nash equilibrium for Markov chains games. Applied Mathematics and Computation,2015,265:911-927.

GOTTLOB G, GRECO G, SCARCELLO F. Pure Nash equilibria: Hard and easy games. Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge. Indiana, USA: ACM,2003:215-230.

BARABASIÁ L, ALBERT R. Emergence of scaling in random net-works. Science,1999,286(5439):509-512.

ERDŐS P, R ÉNYI A. On the evolution of random graphs. Publication of the Mathematical Institute of the Hungarian Academy of Sciences,1960,5(1):17-60.

WATTS D J, STROGATZ S H. Collective dynamics of’small-world’networks. Nature,1998,393(6684):440-442.