> For the complete documentation index, see [llms.txt](https://dizzzzy.gitbook.io/notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dizzzzy.gitbook.io/notebook/nash.md).

# Nash

## 数学证明环节：冯・诺依曼零和博弈均衡的存在性

### 一、前置定义：双人有限零和博弈的数学形式

先把 “零和博弈” 转化为严格的数学语言（为证明铺路）：设双人有限零和博弈为 $$G=(S1​,S2​,u)$$，其中：

* $$S1​={s11​,s12​,...,s1m​}$$：参与者 1 的**纯策略集**（m 个可选纯策略）；
* $$S2​={s21​,s22​,...,s2n​}$$：参与者 2 的**纯策略集**（n 个可选纯策略）；
* $$u:S1​×S2​→R$$：参与者 1 的**收益函数**（因零和博弈，参与者 2 的收益为 $$−u(s1​,s2​)$$，故只需定义 u）。

#### 关键扩展：混合策略

纯策略是 “确定选某一策略”，而**混合策略**是 “以概率选不同纯策略”，对应：

* 参与者 1 的混合策略空间：$$Δ1​={p∈R≥0m​∣∑i=1m​pi​=1}$$（$$pi​$$是选$$s1i​$$的概率）；
* 参与者 2 的混合策略空间：$$Δ2​={q∈R≥0n​∣∑j=1n​qj​=1}$$；
* 混合策略下的**期望收益**：$$U(p,q)=∑i=1m​∑j=1n​pi​qj​u(s1i​,s2j​)$$（参与者 1 的期望收益，参与者 2 为$$−U(p,q)$$）。

### 二、核心定理：极小极大定理

**定理表述**：对任意双人有限零和博弈 $$G=(S1​,S2​,u)$$，存在混合策略 $$p∗∈Δ1​,q∗∈Δ2​$$，使得：$$maxp∈Δ1​​minq∈Δ2​​U(p,q)=minq∈Δ2​​maxp∈Δ1​​U(p,q)=U(p∗,q∗)$$其中：

* $$maxp​minq​U(p,q)$$：参与者 1 的 “极大极小值”（在最坏情况下最大化自己的最小收益）；
* $$minq​maxp​U(p,q)$$：参与者 2 的 “极小极大值”（在最坏情况下最小化自己的最大损失）；
* 等式成立时，$$(p∗,q∗)$$ 就是该零和博弈的**纳什均衡**（双方都无法通过单独改变策略提升收益）。

### 三、证明核心：布劳威尔不动点定理的应用

冯・诺依曼的证明是 “拓扑学工具 + 博弈论建模” 的首次结合，分 4 步完成：

####  1：验证策略空间的 “紧致凸集” 性质

布劳威尔不动点定理的**前提条件**是：映射的定义域是**紧致（闭且有界）凸集**，且映射是**连续**的。先验证混合策略空间 $$Δ1​×Δ2​$$（即 “所有混合策略组合的集合”）满足紧致凸集：

* **凸集**：对任意两个策略组合 $$(p1​,q1​),(p2​,q2​)∈Δ1​×Δ2​$$，以及任意 $$λ∈\[0,1]$$，线性组合 $$λ(p1​,q1​)+(1−λ)(p2​,q2​)$$ 仍属于 $$Δ1​×Δ2​$$（概率和仍为 1，且非负）；
* **紧致**：$$Δ1​×Δ2​$$ 是 $$Rm+n$$ 中的闭子集（包含所有边界点，如 “只选某一纯策略” 的点），且有界（所有概率分量都在 \[0,1] 内）。

####  2：构造 “最优反应映射”

定义映射 $$f:Δ1​×Δ2​→Δ1​×Δ2​$$，其中：

* 对参与者 1：给定参与者 2 的策略 $$q$$，其**最优反应**是最大化自身期望收益的混合策略，即 $$f1​(q)=argmaxp∈Δ1​​U(p,q)$$；
* 对参与者 2：给定参与者 1 的策略 $$p$$，其**最优反应**是最小化自身损失（即最小化参与者 1 的收益），即 $$f2​(p)=argminq∈Δ2​​U(p,q)$$；
* 完整映射：$$f(p,q)=(f1​(q),f2​(p))$$。

####  3：验证映射的 “连续性”

布劳威尔不动点定理要求映射连续 —— 即 “对手策略的微小变化，不会导致自身最优策略的突变”。证明连续性：

* 期望收益 $$U(p,q)$$ 是关于 $$p,q$$ 的线性函数（因此连续）；
* 最优反应 $$f1​(q)$$ 是连续函数的 “最大值点集合”，对凸紧集上的连续函数，其最大值点集合是 “非空凸集” 且随 $$q$$ 连续变化（根据最大值定理）。

#### 4：应用布劳威尔不动点定理得均衡

根据布劳威尔不动点定理：

> 对紧致凸集 $$X$$ 上的连续映射 $$f:X→X$$，存在不动点 $$x∗∈X$$，使得 $$f(x∗)=x∗$$。

将其应用到我们的映射 $$f:Δ1​×Δ2​→Δ1​×Δ2​$$，存在不动点 $$(p∗,q∗)$$，满足：$$f(p∗,q∗)=(p∗,q∗)⟹p∗=f1​(q∗), q∗=f2​(p∗)$$这意味着：

* $$p∗$$ 是对 $$q∗$$ 的最优反应（$$U(p∗,q∗)=maxp​U(p,q∗)$$）；
* $$q∗$$ 是对 $$p∗$$ 的最优反应（$$U(p∗,q∗)=minq​U(p∗,q)$$）；

因此：$$maxp​U(p,q∗)=minq​U(p∗,q)=U(p∗,q∗)$$结合极大极小值的定义，可进一步推出 $$maxp​minq​U(p,q)=minq​maxp​U(p,q)=U(p∗,q∗)$$，极小极大定理得证 ——**零和博弈的纳什均衡存在**。

### 四、从 “存在性证明” 到 “实际计算”：线性规划的桥梁

证明解决了 “均衡是否存在”，但网安攻防中需要**找到具体的均衡策略**（如 “防御者该以多大概率部署防火墙”），这需要将零和博弈转化为线性规划问题。

#### 零和博弈与线性规划的对偶等价性

极小极大定理的结论，恰好对应**一对线性规划的对偶问题**：

**原问题（参与者 1 的极大极小值）**

目标：最大化自己的最小收益 $$v$$$$⎩⎨⎧​maxs.t.​v∑i=1m​pi​u(s1i​,s2j​)≥v, ∀j=1,...,n∑i=1m​pi​=1pi​≥0, ∀i=1,...,m​$$

**对偶问题（参与者 2 的极小极大值）**

目标：最小化自己的最大损失 $$u$$$$⎩⎨⎧​mins.t.​u∑j=1n​qj​u(s1i​,s2j​)≤u, ∀i=1,...,m∑j=1n​qj​=1qj​≥0, ∀j=1,...,n​$$

#### 线性规划算法：从理论到实践

根据线性规划**对偶定理**，原问题与对偶问题的最优值相等（$$v∗=u∗$$），这恰好对应极小极大定理的结论。而求解这对线性规划，需要用到两种核心算法：

1. **丹齐格（Danzig）单纯形法**
   * 核心逻辑：在线性规划的可行域（凸多面体）顶点间迭代，每次移动到 “目标函数更优” 的相邻顶点；
   * 复杂度：**最坏情况指数级**（如 Klee-Minty 立方体问题），但**实践中极高效**（网安攻防的策略空间通常是 “中等规模”，迭代次数与策略数线性相关）；
   * 网安应用：DDoS 攻防、漏洞修复资源分配的均衡策略求解。
2. **卡哈基扬（Khachiyan）椭球法**
   * 核心逻辑：用椭球逐步收缩覆盖可行域，逼近最优解；
   * 复杂度：**理论多项式级**（$$O(n6L)$$，n 为变量数，L 为精度），但**实践中效率极低**（常数因子过大，收缩速度慢）；
   * 网安应用：仅用于超大规模策略空间的理论研究，极少落地。

两位玩家分别从整数集合 $${0,1,\dots,100}$$\选数，设两数为 $$a,b$$。规则如下：

* 计算“所有数的平均值的一半” —— 对于两人这就是 $$T=\frac{a+b}{4}$$​。
* 离T更近者获胜（获 1），若距离相同则各得 $$\frac{1}{2}$$。
* 额外规则：如果有人选 0，则选 100的玩家获胜。

目标：在该游戏下（只选整数，人数为 2），推导纳什均衡。

#### 1)  在没有特殊规则时的直观均衡

给定两数 $$a,b$$，比较谁离 $$T=\frac{a+b}{4}$$更近：

$$|a-T| < |b-T| \iff |a-\tfrac{a+b}{4}| < |b-\tfrac{a+b}{4}| \iff |3a-b| < |3b-a|$$

两边平方展开并约去项后得到（注意 $$a,b\ge0$$）： $$(3a-b)^2 < (3b-a)^2 \iff 8a^2 < 8b^2 \iff a^2 < b^2 \iff a < b$$

结论：**在不考虑额外 0↔100 例外规则时，两人中选更小的那个必胜（若相等则平局）**。

双方同时选 0（即策略剖面 $$(0,0)$$）是一个纯策略纳什均衡

***

#### 2) 把例外规则加入后的分析（0 、1与 100 形成循环）

把“有人选 0，则选 100 的获胜”加入后，会出现一个循环式的偏好：

* 若对手选 $$b\in{1,\dots,99}$$，则你通过选更小的数（最优为 0）取胜 —— 因此对于任何 $$1\le b\le99$$，你最优是选 0。
* 若对手选 100，选 0 会被额外规则惩罚（对手 100 获胜），因此对手选 100 时你 **不能** 选 0；此时你应选一个 1（或任意 $$1\le k\le99$$），任意这些数都会比 100 更小从而获胜；最优是尽可能小的正整数（即 1）。
* 若对手选 0，你可以改为 100 并直接赢（按例外规则）；所以对手选 0 时你最优是 100。

总结成 BR（最好回应）映射（简化写出代表性的最好回应）：

* $$\mathrm{BR}(b)=0$$ 对于 $$b\in{1,\dots,99}$$；
* $$\mathrm{BR}(100)=1$$（或任何正整数，但 1 是最优）；
* $$\mathrm{BR}(0)=100$$.

这产生了一个三角循环： $$0 \to 100 \to 1 \to 0$$。因此不存在稳定的纯策略剖面——任意纯剖面都存在单点偏离使偏离者获利。所以**没有纯策略纳什均衡**。

***

#### 3) 寻找混合策略纳什均衡 —— 支持集只需 {0,1,100}

由上面的循环结构，我们可以猜测并验证一个最简的支持集（support）是 $${0,1,100}$$。理由：其它中间数 $$k\in{2,\dots,99}$$ 在对手随机化于$${0,1,100}$$时不会比 1 有更高的期望回报，因此混合均衡的支持只需包含这三个策略。

设在对称混合均衡中，三策略的概率分别为 $$p\_0=\Pr(0),\quad p\_1=\Pr(1),\quad p\_{100}=\Pr(100)$$

且 $$p\_0+p\_1+p\_{100}=1$$。在对称均衡中，三种被支持的纯策略对对手分布应当使期望收益相等（不在支持内的任意策略期望收益不超过该共同值）。

计算这三种纯策略面对对方以 $$(p\_0,p\_1,p\_{100})$$随机化时的期望收益（按“胜得 1，平局得 1/2，输得 0”）：

* 选 0 的期望收益：

  &#x20;$$U(0)=p\_1\cdot 1 + p\_0\cdot\frac12 + p\_{100}\cdot 0$$

  （对手出 1 时你赢；对手出 0 平局；对手出 100 时按例外你输。）
* 选 1 的期望收益：

  $$U(1)=p\_{100}\cdot 1 + p\_1\cdot\frac12 + p\_0\cdot 0$$

  （对手出 100 时你比 100 小而赢；对手出 1 平局；对手出 0 时你输。）
* 选 100 的期望收益：

  $$U(100)=p\_0\cdot 1 + p\_1\cdot 0 + p\_{100}\cdot\frac12$$

  （对手出 0 时按例外你赢；对手出 1 时你输；对手出 100 平局。）

令三者相等 $$U(0)=U(1)=U(100)$$。联立等式 $$p\_0+p\_1+p\_{100}=1$$解这个线性方程组，可以解得：

&#x20;$$p\_0=\tfrac13,\quad p\_1=\tfrac13,\quad p\_{100}=\tfrac13$$&#x20;

代回任一 $$U$$ 可得共同期望收益 $$U=\tfrac12$$​。

此外检验任一其它策略 $$k\in{2,\dots,99}$$在对手以 $$(\frac13, \frac13, \frac13)$$ 随机时的期望收益为 $$\Pr(\text{对手}=100)\cdot 1 = \frac13 < \frac12$$，因此没 U有动机偏离进入支持外的策略。

因此这是一个对称混合策略纳什均衡：**两位玩家各自以等概率** $$(\frac13, \frac13, \frac13)$$**选择** $${0,1,100}$$。