5.3 Network Defending Games

网络防御博弈 Network Defending Games

网络防御博弈（network defending game）研究防御者如何在带权网络中分配有限资源，以降低攻击者单点攻击造成的最坏损失。资源既保护所在节点，也通过邻接关系产生共享防御效果。

模型与优化目标

设网络为带权无向图 \(G=(V,E)\)，\(N(u)\) 表示节点 \(u\) 的邻居集合。资源分配（resource allocation）为 \(r=(r_u)_{u\in V}\)，满足

\[ r_u\ge 0,\qquad \sum_{u\in V}r_u\le R, \]

其中 \(R\) 是总资源预算。每个节点有最低防御阈值 \(\mathrm{LB}_u\)、完全防御阈值 \(\mathrm{UB}_u\)，以及完整损失 \(g_u\) 和部分损失 \(g'_u\)，且 \(\mathrm{LB}_u\le\mathrm{UB}_u\)、\(0\le g'_u<g_u\)。

共享资源与防御水平

边权 \(w_{uv}\ge0\) 表示相邻节点资源共享的强度。节点的防御水平（defending power）为

\[ p_u(r)=r_u+\sum_{v\in N(u)}w_{uv}r_v. \]

资源共享并非从邻居扣除资源后转移给本节点，而是同一份部署对相邻节点产生保护效果。例如，当边权均为 \(0.5\) 时，邻居的每单位资源为本节点贡献 \(0.5\) 单位防御水平。

三种防御状态

状态	条件	攻击节点 \(u\) 的损失
防御不足	\(p_u<\mathrm{LB}_u\)	\(g_u\)
部分防御	\(\mathrm{LB}_u\le p_u<\mathrm{UB}_u\)	有防御不足的邻居时为 \(g'_u\)，否则为 \(0\)
完全防御	\(p_u\ge\mathrm{UB}_u\)	\(0\)

因此，部分防御节点的损失不仅取决于自身防御水平，也取决于邻居是否脆弱。写成损失函数（loss function）：

\[ L_u(r)= \begin{cases} g_u,&p_u<\mathrm{LB}_u,\\ g'_u,&\mathrm{LB}_u\le p_u<\mathrm{UB}_u\ \text{且存在 }v\in N(u):p_v<\mathrm{LB}_v,\\ 0,&\text{其他情况}. \end{cases} \]

攻击者选择损失最大的节点，防御结果（defending result）与最优值分别为

\[ D(r)=\max_{u\in V}L_u(r),\qquad \operatorname{OPT}(R)=\min_{r\ge0,\,\sum r_u\le R}D(r). \]

目标是最小化最坏单点攻击损失，而不是所有节点损失之和。

课件算例

六个节点的资源量为 \((2,1,2,1,4,1)\)，总预算为 \(11\)。共享边权为 \(0.5\) 时，课件图中防御水平为 \((5,5,5,4,7,2)\)。取 \(\mathrm{LB}=4\)、\(\mathrm{UB}=6\)、\(g=2\)、\(g'=1\)，则防御水平为 \(7\) 的节点完全防御，为 \(2\) 的节点防御不足，其余节点处于部分防御状态；后者是否发生损失还须检查邻居。

固定损失目标的可行性判定

先固定目标值 \(\alpha\)，判断是否能使 \(D(r)\le\alpha\)。定义

\[ A_\alpha=\{u:g_u>\alpha\},\qquad B_\alpha=\{u\in A_\alpha:g'_u>\alpha\}. \]

\(A_\alpha\) 是必须至少达到最低防御阈值的节点集合；\(B_\alpha\) 是连部分损失也不能容忍的关键节点集合。为满足目标：

• 对 \(u\in A_\alpha\)，必须有 \(p_u\ge\mathrm{LB}_u\)。
• 对 \(u\in B_\alpha\)，必须完全防御，或确保所有邻居至少达到各自最低防御阈值。
• 对 \(u\notin A_\alpha\)，自身完整损失不超过目标，但仍可能需要保护它以消除关键邻居的部分损失。

随着 \(\alpha\) 增大，要求不会变得更严格，可在候选损失值 \(\{0\}\cup\{g_u,g'_u:u\in V\}\) 上进行二分搜索（binary search）。

单阈值模型：线性规划精确求解

单阈值模型（single-threshold model）要求 \(\mathrm{LB}_u=\mathrm{UB}_u\)，因此没有部分防御区间。对固定 \(\alpha\)，只需保证 \(A_\alpha\) 中所有节点达到门槛。

线性规划（Linear Programming，LP）可写成：

\[ \begin{aligned} \text{寻找 }&r_u\ge0,\\ \text{满足 }&r_u+\sum_{v\in N(u)}w_{uv}r_v\ge\mathrm{LB}_u &&\forall u\in A_\alpha,\\ &\sum_{u\in V}r_u\le R. \end{aligned} \]

该 LP 可行，当且仅当存在损失不超过 \(\alpha\) 的分配。结合候选值搜索，可得到多项式时间精确算法。共享资源仍然存在，但损失判定已经成为线性约束。

无共享模型：最小割精确求解

无共享模型（isolated model）要求所有 \(w_{uv}=0\)，因此 \(p_u=r_u\)。原图邻接关系仍决定部分防御节点是否受脆弱邻居影响；“无共享”不等于删除所有邻接关系。

选择哪些关键节点完全防御

令 \(S\subseteq B_\alpha\) 表示选择完全防御的关键节点。其他关键节点只达到最低门槛，但它们的所有邻居都必须达到最低门槛。达到目标所需资源为

\[ \begin{aligned} C(S)={}&\sum_{u\in A_\alpha}\mathrm{LB}_u +\sum_{u\in S}(\mathrm{UB}_u-\mathrm{LB}_u)\\ &+\sum_{\substack{v\notin A_\alpha:\\N(v)\cap(B_\alpha\setminus S)\ne\varnothing}}\mathrm{LB}_v. \end{aligned} \]

第一项是固定基础成本，第二项是把关键节点升级为完全防御的额外成本，第三项是为未升级关键节点保护外部邻居的成本。一个邻居即使关联多个关键节点，也只需计一次。

加权覆盖与割网络

只考虑 \(B_\alpha\) 与 \(V\setminus A_\alpha\) 之间的边。每条边 \((u,v)\) 都必须由以下至少一个选择覆盖：升级 \(u\)，或保护 \(v\)。这形成二分图上的最小权顶点覆盖（minimum-weight vertex cover），可用最小割（minimum cut）求解。

构造源点 \(s\)、汇点 \(t\)，并加入：

• \(s\to u\)，\(u\in B_\alpha\)，容量 \(\mathrm{UB}_u-\mathrm{LB}_u\)；
• \(v\to t\)，\(v\notin A_\alpha\)，容量 \(\mathrm{LB}_v\)；
• \(u\to v\)，对应上述两集合间的原图边，容量取大于任何有限可行成本的值。

有限割要求每条 \(u\to v\) 至少切掉对应的一个端点成本。若 \(u\) 位于汇侧，则升级 \(u\)；若 \(v\) 位于源侧，则保护 \(v\)。最小割值是最小额外成本，加上基础成本即为达到 \(\alpha\) 所需的最少资源。利用最大流—最小割定理（max-flow/min-cut theorem）及候选值搜索，可精确求解该模型。

一般模型的计算困难性

非确定性多项式时间困难（non-deterministic polynomial-time hard，NP-hard）意味着该问题至少与 NP 中最困难的判定问题一样难。一般网络防御模型通过最大析取范式满足问题（maximum disjunctive normal form satisfiability，MAX-DNF）归约证明困难性。

MAX-DNF 给定布尔变量和若干由文字合取构成的子句，目标是最大化被满足的子句数。归约构造互补文字节点、子句节点以及文字—子句关系节点，以资源部署编码变量赋值。若至少 \(t\) 个子句可被满足，则对应网络可在预算

\[ R=n+\frac{m-t}{m} \]

下获得零损失；反向也成立，其中 \(n\) 为变量数，\(m\) 为子句数。

因此，区分 \(\operatorname{OPT}=0\) 与 \(\operatorname{OPT}>0\) 已经 NP-hard。任何有限乘法比率的损失近似都必须在零最优值时返回零，否则无法满足比率保证，所以在标准复杂度假设 \(\mathrm P\ne\mathrm{NP}\) 下，一般模型没有有限乘法近似算法。

资源增强与 LP 舍入

资源增强（resource augmentation）改变比较方式：允许算法使用 \(\gamma R\) 资源，但要求其损失不超过预算 \(R\) 下的最优损失。课件给出 \(\gamma=2\) 的保证：

\[ D(r^{\mathrm{alg}})\le\operatorname{OPT}(R),\qquad \sum_u r_u^{\mathrm{alg}}\le2R. \]

用指示变量表达两种保护选择

固定 \(\alpha\)，对 \(u\in B_\alpha\) 设置 \(y_u\in\{0,1\}\) 表示是否完全防御；对 \(v\notin A_\alpha\) 设置 \(y_v\in\{0,1\}\) 表示是否保护到最低阈值。约束为

\[ \begin{aligned} y_u+y_v&\ge1 &&\forall (u,v)\in E,\ u\in B_\alpha,\ v\notin A_\alpha,\\ p_u&\ge\mathrm{LB}_u+y_u(\mathrm{UB}_u-\mathrm{LB}_u) &&\forall u\in B_\alpha,\\ p_u&\ge\mathrm{LB}_u &&\forall u\in A_\alpha\setminus B_\alpha,\\ p_v&\ge y_v\mathrm{LB}_v &&\forall v\notin A_\alpha. \end{aligned} \]

再加入防御水平定义、非负资源和预算约束。关键节点的邻居若在 \(A_\alpha\) 内，本来就已达到最低门槛，因此不需要额外的覆盖约束。

松弛与舍入规则

线性规划松弛（LP relaxation）把指示变量放宽到 \([0,1]\)。对预算 \(R\) 求得分数可行解后，采用舍入（rounding）：

\[ r'_u=2r_u,\qquad y'_u=\begin{cases}1,&y_u\ge1/2,\\0,&y_u<1/2.\end{cases} \]

由于防御水平对资源线性，\(p'_u=2p_u\)。每条覆盖边满足 \(y_u+y_v\ge1\)，至少一端的分数值不小于 \(1/2\)，所以舍入后仍被覆盖。

若关键节点 \(y_u\ge1/2\)，则

\[ p'_u\ge2\mathrm{LB}_u+2y_u(\mathrm{UB}_u-\mathrm{LB}_u) \ge\mathrm{UB}_u. \]

若外部邻居 \(y_v\ge1/2\)，则 \(p'_v\ge2y_v\mathrm{LB}_v\ge\mathrm{LB}_v\)。其他必须保护的节点也保持满足最低门槛。因此舍入不会破坏目标损失约束，资源使用最多翻倍。

课件公式采用另一种等价记法：松弛阶段预算为 \(R/2\)，舍入阶段预算为 \(R\)。两种写法都表示“使用双倍资源，匹配原预算下的最优防御质量”。

结论与模型边界

模型	可用方法	主要结论
单阈值，共享资源	LP 与目标值搜索	多项式时间精确求解
双阈值，无共享资源	最小割与目标值搜索	多项式时间精确求解
双阈值，共享资源	整数规划、LP 松弛与舍入	NP-hard；有 2 倍资源增强保证

攻击伤害传播、资源只能沿邻边移动等扩展会改变约束与困难性。课件的资源增强结论针对静态资源部署和单点攻击，使用时应先核对模型假设。