7.1.2 纳什均衡的存在性
纳什均衡的存在性是博弈论中被广泛探讨的重要议题。它被定义
为合适映射的不动点。事实上,博弈均衡的存在性与不动点(fixed points)定理密切相关,其中包括布劳威尔(Brouwer)不动点定理[1] 、角谷(Kakutani)不动点定理[2] 等。
子集𝑋 ⊂ ℝ𝑛,如果映射𝑓: 𝑋 → 𝑋连续,则𝑓存在一个不动点。
(a)𝑓是上半连续的;
(b)对于每个𝑥 ∈ 𝑋,𝑓(𝑥)是非空且凸的,并且𝑓(𝑥) ⊂ 𝑋;则𝑓在𝑋中存在一个不动点。
约翰·纳什在他的重要著作[3] [4] 中将均衡概念推广到三人或三人以上博弈,并证明了每个有限策略型博弈都至少存在一个混合策略纳什均衡。
定理 9(纳什定理)对于每个有限策略型博弈Γ = 〈𝑁, (𝑆𝑖), (𝑢𝑖)〉,
都至少存在一个混合策略纳什均衡。
证明: 考虑有限策略型博弈Γ = 〈𝑁, (𝑆𝑖), (𝑢𝑖)〉 ,其中𝑁 =
{1,2, … , 𝑛}。我们使用下列符号
𝑆𝑖 = {𝑠𝑖𝑗: 𝑗 = 1,2, … , 𝑚𝑖}
表示参与者𝑖的策略集,其中𝑚𝑖 = |𝑆𝑖|;𝑖 = 1,2, … , 𝑛。
我们现在利用布劳威尔不动点定理来证明上述有限策略型博弈存在至少一个混合策略均衡(纳什定理)。定义Δ(𝑆𝑖)为由𝑆𝑖 上的所有概率分布组成的集合,令𝑀 = Δ(𝑆1) × Δ(𝑆2) × … × Δ(𝑆𝑛)。每个𝜎 ∈ 𝑀都是一个向量,含有∑𝑖∈𝑁|𝑆𝑖|个个分量。假设𝑠𝑖𝑘是参与者𝑖的某个特定纯策略,令𝜎𝑖𝑘是𝜎中对应于𝑠𝑖𝑘的分量。我们将𝜎记为𝜎 = (𝜎𝑖, 𝜎−𝑖)。定义映射𝑓: 𝑀 → 𝑀,它将𝑀中的向量映射到自身。给定𝜎 ∈ M,𝑓(𝜎)的分量个数与𝜎的分量个数相同;令𝑓𝑖𝑘(𝜎)表示𝑓(𝜎)中对应于纯策略𝑠𝑖𝑘的分量。可以表示为:
𝑓 (𝜎) = 𝜎𝑖𝑘 + max (0, 𝑢𝑖(𝑠𝑖𝑘, 𝜎−𝑖) − 𝑢𝑖(𝜎𝑖, 𝜎−𝑖)) .
𝑖𝑘
∑ [𝜎
+ max (0, 𝑢 (𝑠
, 𝜎
) − 𝑢 (𝜎 , 𝜎
))]
𝑠𝑖𝑗∈𝑆𝑖 𝑖𝑗
𝑖 𝑖𝑗
−𝑖
𝑖 𝑖 −𝑖
需要注意的是,上式中的分母必定大于或等于 1,因为
∑ 𝜎𝑖𝑗 = 1.
𝑠𝑖𝑗∈𝑆𝑖
此外,我们有
|𝑆𝑖|
∑ 𝑓𝑖𝑗(𝜎) = 1, 𝑖 = 1,2, … , 𝑛.
𝑗=1
显然,𝑓: 𝑀 → 𝑀是一个明确定义的映射,并且可以证明𝑓是连续的。因此,根据布劳威尔不动点定理,𝑓有一个不动点。也就是说,存在𝜎∗ ∈ M使得𝑓(𝜎∗) = 𝜎∗。这意味着,对于所有𝑖 ∈ 𝑁,所有𝑠𝑖𝑘 ∈ 𝑆𝑖,
我们有
∗ ∗ 𝑖𝑘 −𝑖 𝑖 −𝑖
𝜎∗ + max (0, 𝑢𝑖(𝑠𝑖𝑘, 𝜎∗ ) − 𝑢𝑖(𝜎∗, 𝜎∗ ))
𝜎 = 𝑓(𝜎 ) = .
𝑖𝑘
𝑖𝑘
∑ [𝜎∗ + max (0, 𝑢 (𝑠
, 𝜎∗ ) − 𝑢 (𝜎∗, 𝜎∗ ))]
𝑠𝑖𝑗∈𝑆𝑖
𝑖𝑗
𝑖 𝑖𝑗
−𝑖
𝑖 𝑖
−𝑖
我们现在考虑两种情形。在第一种情况下,
∑ [𝜎∗ + max (0, 𝑢𝑖(𝑠𝑖𝑗, 𝜎∗ ) − 𝑢𝑖(𝜎∗, 𝜎∗ ))] = 0, ∀𝑖 ∈ 𝑁.
𝑠𝑖𝑗∈𝑆𝑖
𝑖𝑗
−𝑖
𝑖 −𝑖
在第二种情况下,至少对于某个𝑖 ∈ 𝑁,上式大于零。在第一种情况下,我们有
𝑢𝑖(𝑠𝑖𝑘, 𝜎∗ ) − 𝑢𝑖(𝜎∗, 𝜎∗ ) ≤ 0, ∀𝑠𝑖𝑗 ∈ 𝑆𝑖, ∀𝑖 ∈ 𝑁.
−𝑖 𝑖 −𝑖
显然,(𝜎∗, 𝜎∗ )是一个纳什均衡。
𝑖 −𝑖
在第二种情况下,至少存在一个参与者𝑖和策略𝑠𝑖𝑘 ∈ 𝑆𝑖,使得 max(0, 𝑢𝑖(𝑠𝑖𝑘, 𝜎∗ ) − 𝑢𝑖(𝜎∗, 𝜎∗ )) > 0.
这意味着
−𝑖
𝑖 −𝑖
∗ −𝑖 𝑖 −𝑖
max (0, 𝑢𝑖(𝑠𝑖𝑘, 𝜎∗ ) − 𝑢𝑖(𝜎∗, 𝜎∗ ))
𝜎 = .
𝑖𝑘
∑ [max (0, 𝑢 (𝑠
, 𝜎∗ ) − 𝑢 (𝜎∗, 𝜎∗ ))]
𝑠𝑖𝑗∈𝑆𝑖
𝑖 𝑖𝑗
−𝑖
𝑖 𝑖
−𝑖
这又意味着𝜎∗ ≠ 0,由此可知𝜎∗ > 0。进一步,我们可以证明,
𝑖𝑘 𝑖𝑘
𝑖𝑘
∀𝑠𝑖𝑘 ∈ 𝑆𝑖,当且仅当𝜎∗ > 0时有:
𝑢𝑖(𝑠𝑖𝑘, 𝜎∗ ) > 𝑢𝑖(𝜎∗, 𝜎∗ ).
−𝑖 𝑖 −𝑖
这样,我们就得到了一个矛盾,这是因为𝑢𝑖(𝜎∗, 𝜎∗ )是𝑢𝑖(𝑠𝑖𝑘, 𝜎∗ )
𝑖
𝑖𝑘
的一个凸组合,其中𝑠𝑖𝑘 ∈ 𝑆𝑖,𝜎∗ > 0。注意:
−𝑖
−𝑖
𝑢𝑖(𝜎∗, 𝜎∗ ) = ∑ 𝑢𝑖(𝑠𝑖𝑘, 𝜎∗ ) > ∑ 𝑢𝑖(𝜎∗, 𝜎∗ ) = 𝑢𝑖(𝜎∗, 𝜎∗ ).
𝑖
𝑖
𝑖 −𝑖
𝑠𝑖𝑘∈𝛿(𝜎∗)
−𝑖
𝑠𝑖𝑘∈𝛿(𝜎∗)
𝑖 −𝑖
𝑖 −𝑖
因此,只有第一种情形能够发生。因此,(𝜎∗, 𝜎∗ )是一个纳什均
𝑖 −𝑖
衡。∎