7.1.1 纳什均衡
在研究纳什均衡之前，我们必须首先给出博弈的数学定义，在此着重关注策略型博弈。
〈𝑁, (𝑆𝑖)𝑖∈𝑁, (𝑢𝑖)𝑖∈𝑁〉，其中：
∎ 𝑁 = {1, 2, … , 𝑛}为参与者的集合，包含参与者1, 2, … , 𝑛；
∎ 𝑆1, 𝑆2, … , 𝑆𝑛分别是参与者1, 2, … , 𝑛的策略集合；即𝑆1代表参与者1的策略集，…，𝑆𝑛代表参与者𝑛的策略集；
∎ 𝑢𝑖: 𝑆1 × 𝑆2 × … × 𝑆𝑛 → ℝ（其中，𝑖 = 1, 2, … , 𝑛）是一组映射，通常称为效用函数或收益函数。
在此，策略有时也被称为行动（action）或纯策略（pure strategies）。
我们使用笛卡尔积𝑆1 × 𝑆2 × … × 𝑆𝑛来表示策略，记为𝑆。如果参与者
𝑖根据某个给定的概率分布选择𝑆𝑖中的策略，则得到混合策略，又称随机策略。
定义 2（混合策略）鉴于参与者𝑖及其纯策略集𝑆𝑖的给定，其混合
策略（mixed strategy）或称随机策略（randomized strategy）𝜎𝑖可定义为𝑆𝑖上的概率分布。具体而言，𝜎𝑖: 𝑆𝑖 → [0,1]是一个映射，它为每个纯策略𝑠𝑖 ∈ 𝑆𝑖分配一个概率值，满足以下条件：
∑ 𝜎𝑖(𝑠𝑖) = 1.
𝑠𝑖∈𝑆𝑖
假设𝑆𝑖 = {𝑠𝑖1, 𝑠𝑖2, … , 𝑠𝑖𝑛}，则参与者𝑖的所有混合策略形成的集合，可以表示为集合𝑆𝑖上所有可能的概率分布的集合，即：
𝑚
Δ(𝑆𝑖) = {(𝜎𝑖1, … , 𝜎𝑖𝑚) ∈ ℝ𝑚: 𝜎𝑖𝑗 ≥ 0 对于𝑗 = 1, … , 𝑚且∑ 𝜎𝑖𝑗 = 1}.
𝑗=1
集合Δ(𝑆𝑖)被称为𝑆𝑖的混合扩展（mixed extension）。我们定义M =
Δ(𝑆1) × Δ(𝑆2) × … × Δ(𝑆𝑛)为混合策略集合。
现在我们已经为纳什均衡的定义做好了准备。
〈𝑁, (𝑆𝑖), (𝑢𝑖)〉及其策略组𝑠∗ = (𝑠∗, 𝑠∗, … , 𝑠∗)，如果满足以下条件：
1 2 𝑛
𝑢𝑖(𝑠∗, 𝑠∗ ) ≥ 𝑢𝑖(𝑠𝑖, 𝑠∗ ), ∀𝑠𝑖 ∈ 𝑆𝑖, 𝑖 = 1,2, … , 𝑛.
𝑖 −𝑖 −𝑖
则𝑠∗是Γ的一个纯策略纳什均衡（简记为 PSNE）。
我们现在提供纯策略纳什均衡（PSNE）的另外一种描述方法。定义 4 （ 最优反应对应） 对于给定的策略型博弈Γ =
〈𝑁, (𝑆𝑖), (𝑢𝑖)〉，参与者𝑖的最优反应对应（best response correspondence）
是映射𝑏𝑖: 𝑆−𝑖 → 2𝑆𝑖，其定义如下：
𝑏𝑖(𝑠−𝑖) = {𝑠𝑖 ∈ 𝑆𝑖: 𝑢𝑖(𝑠𝑖, 𝑠−𝑖) ≥ 𝑢𝑖(𝑠′, 𝑠−𝑖), ∀𝑠′ ∈ 𝑆𝑖}.
𝑖 𝑖
换句话说，给定所有其他参与者的策略组𝑠−𝑖，𝑏𝑖(𝑠−𝑖)给出了由参与者𝑖的所有最优反应策略组成的集合。
𝑠∗ ∈ 𝑏𝑖(𝑠∗ ), ∀𝑖 = 1,2, … , 𝑛.
𝑖 −𝑖
〈𝑁, (𝑆𝑖), (𝑢𝑖)〉以及其混合策略组(𝜎∗, 𝜎∗, … , 𝜎∗)，若满足对于所有𝑖 ∈ 𝑁：
1 2 𝑛
𝑢𝑖(𝜎∗, 𝜎∗ ) ≥ 𝑢𝑖(𝜎𝑖, 𝜎∗ ), ∀𝜎𝑖 ∈ Δ(𝑆𝑖).
𝑖 −𝑖 −𝑖
则 (𝜎∗, 𝜎∗, … , 𝜎∗)是一个混合策略纳什均衡（mixed strategy Nash
1 2 𝑛
equilibrium）。
定义最优反应函数（best response functions）𝑏𝑖(∙)如下：
𝑏𝑖(𝜎−𝑖) = {𝜎𝑖 ∈ Δ(𝑆𝑖): 𝑢𝑖(𝜎𝑖, 𝜎−𝑖) ≥ 𝑢𝑖(𝜎′, 𝜎−𝑖), ∀𝜎′ ∈ Δ(𝑆𝑖)}.
𝑖 𝑖
给定𝜎−𝑖，𝑏𝑖(𝜎−𝑖)是参与者𝑖的所有混合策略构成的集合，其中每
个混合策略都是他针对其他参与者选择𝜎−𝑖行为的最优反应。因此，显然，混合策略组(𝜎∗, 𝜎∗, … , 𝜎∗)是一个纳什均衡当且仅当：
1 2 𝑛
𝜎∗ ∈ 𝑏𝑖(𝜎∗ ), ∀𝑖 = 1,2, … , 𝑛.
𝑖 −𝑖
由定义可知，当博弈处于纳什均衡状态下，任意玩家无法通过单独改变自身的策略来获得更多的收益。
由于纳什均衡的计算是 PPAD-complete 的，因此，除了严格定义的纳什均衡外，还存在一种实际中经常被分析的近似纳什均衡。
定理 6 （𝜺-纳什均衡） 对于给定的策略型博弈〈𝑁, (𝑆𝑖), (𝑢𝑖)〉以及
一个策略组，给定实数𝜀 > 0，若对于所有𝑖 ∈ 𝑁：
𝑢𝑖(𝜎∗, 𝜎∗ ) ≥ 𝑢𝑖(𝜎𝑖, 𝜎∗ ) − 𝜀, ∀𝜎𝑖 ∈ Δ(𝑆𝑖).
𝑖 −𝑖 −𝑖
则(𝜎∗, … , 𝜎∗)称为该博弈的一个𝜺-纳什均衡（𝜀-Nash equilibrium）。
1 𝑛