纳什存在性定理_(Nash's_Existence_Theorem)

纳什存在性定理 (Nash's Existence Theorem)

纳什存在性定理 (Nash's Existence Theorem) 是博弈论 (Game Theory) 中最基本也是最重要的基石性定理之一。该定理指出，在任何具有有限数量参与者且每位参与者都只有有限个纯粹策略 (Pure Strategy) 的非合作博弈 (Non-cooperative Game) 中，只要我们允许参与者使用混合策略 (Mixed Strategy)，那么至少存在一个纳什均衡 (Nash Equilibrium)。

该定理由数学家约翰·纳什 (John Forbes Nash Jr.) 在其1950年的博士论文中提出并证明，这一成果极大地扩展了博弈论的应用范围，并成为现代经济学、政治科学、计算机科学和演化生物学等领域分析策略互动的基础。纳什也因此获得了1994年的诺贝尔经济学奖。

定理的正式陈述

纳什存在性定理可以被更精确地描述如下：

对于一个拥有 $n$ 个参与者的博弈 $G = \{S_1, \dots, S_n; u_1, \dots, u_n\}$：

1. 参与者集合：参与者数量 $n$ 是一个有限的整数。
2. 策略空间：每个参与者 $i$ 的纯粹策略集合 $S_i$ 是一个有限集合。
3. 支付函数：每个参与者 $i$ 的支付函数 (Payoff Function) $u_i(s_1, \dots, s_n)$ 为每一个可能的纯策略组合（即策略组合 $s \in S_1 \times S_2 \times \dots \times S_n$）都分配一个实数值的效用 (Utility) 或支付。

如果这个博弈允许参与者采用混合策略，即每个参与者 $i$ 可以在其纯策略集合 $S_i$ 上选择一个概率分布 $\sigma_i$，那么该博弈至少存在一个纳什均衡。

一个混合策略纳什均衡是一个混合策略组合 $(\sigma_1^*, \sigma_2^*, \dots, \sigma_n^*)$，使得对于任何一个参与者 $i$，在其他参与者都选择其均衡策略 $\sigma_{-i}^*$ 的情况下，该参与者 $i$ 无法通过单方面改变自己的策略（从 $\sigma_i^*$ 变为任何其他策略 $\sigma_i$）来获得更高的期望支付。数学上表示为：

其中 $\Sigma_i$ 是参与者 $i$ 的所有可能混合策略的集合。

理解定理的核心概念

为了深入理解纳什存在性定理，必须先掌握以下几个关键概念：

• 纯粹策略 (Pure Strategy)：指参与者在博弈中选择的一个确定的行动方案。例如，在“石头、剪刀、布”游戏中，出“石头”就是一个纯粹策略。
• 混合策略 (Mixed Strategy)：指参与者并非确定地选择某一个纯粹策略，而是以一定的概率分布来选择不同的纯粹策略。例如，以 $1/3$ 的概率出石头，$1/3$ 的概率出剪刀，$1/3$ 的概率出布，这就是一个混合策略。纳什存在性定理的关键就在于将策略空间从有限的纯粹策略点扩展到了连续的混合策略空间。
• 纳什均衡 (Nash Equilibrium)：这是一个策略组合，在该组合中，没有任何一个参与者可以通过单方面改变自己的策略而获得更好的收益。它是一个“稳定”的状态，因为一旦达到纳什均衡，所有参与者都没有动机偏离这个状态。著名的囚徒困境 (Prisoner's Dilemma) 的均衡就是一个典型的例子。

定理的证明思路（基于不动点定理）

纳什存在性定理的证明是一个非构造性的证明，它证明了均衡的存在性，但没有提供一个通用的方法来找到这个均衡。其证明巧妙地运用了高等数学中的不动点定理，通常是角谷不动点定理 (Kakutani's Fixed-Point Theorem)（或者在更简单情况下的Brouwer不动点定理 (Brouwer's Fixed-Point Theorem)）。

其证明逻辑可以概括为以下步骤：

1. 构建策略空间：首先，我们构建一个所有参与者混合策略的联合空间，记为 $\Sigma = \Sigma_1 \times \Sigma_2 \times \dots \times \Sigma_n$。这个空间中的每一个点都代表一个完整的混合策略组合。这个联合策略空间是一个紧集 (Compact) 和凸集 (Convex)。 \begin{itemize}
2. 凸性 (Convexity)：意味着如果两个策略组合是有效的，那么它们的任意线性组合（加权平均）也是一个有效的策略组合。
3. 紧性 (Compactness)：在欧几里得空间中，它意味着这个空间是有界且闭合的。 \end{itemize}
4. 定义最佳应对函数 (Best-Response Correspondence)：对于任意给定的其他参与者的策略组合 $\sigma_{-i}$，我们可以为参与者 $i$ 找到一个或多个使他自己期望支付最大化的策略。所有这些策略的集合被称为参与者 $i$ 对 $\sigma_{-i}$ 的“最佳应对”，记为 $BR_i(\sigma_{-i})$。
5. 构建联合最佳应对函数：我们将所有参与者的最佳应对函数组合成一个联合的最佳应对函数（一个集值函数或“对应”），$BR: \Sigma \to 2^{\Sigma}$，它将空间中的任意一个策略组合 $\sigma$ 映射到所有参与者对其进行最佳应对后形成的新策略组合的集合 $BR(\sigma) = BR_1(\sigma_{-1}) \times \dots \times BR_n(\sigma_{-n})$。
6. 应用角谷不动点定理：我们可以证明，这个联合最佳应对函数 $BR$ 满足角谷不动点定理的所有条件： \begin{itemize}
7. 定义域 $\Sigma$ 是非空的、紧的、凸的欧几里得空间子集。
8. 对于任意 $\sigma \in \Sigma$，其像 $BR(\sigma)$ 是非空且凸的。
9. $BR$ 的图像是闭合的（这是一种连续性条件，称为“上半连续性”）。 \end{itemize}
10. 解释不动点：角谷不动点定理保证了，必然存在一个策略组合 $\sigma^*$，使得 $\sigma^* \in BR(\sigma^*)$。这个点就是“不动点”。一个不动点 $\sigma^*$ 意味着，它本身就是对它自己的最佳应对。换言之，在策略组合 $\sigma^*$ 中，每一位参与者 $i$ 的策略 $\sigma_i^*$ 都是对其他参与者策略 $\sigma_{-i}^*$ 的最佳应对。
11. 不动点即纳什均衡：根据纳什均衡的定义，一个所有参与者都在采取相互最佳应对策略的策略组合，正是一个纳什均衡。因此，不动点的存在证明了纳什均衡的存在。

意义与局限

意义

• 奠定理论基础：纳什存在性定理是现代非合作博弈理论的出发点。它保证了对于一大类重要的、具有现实意义的博弈，纳什均衡这个解概念不是空洞的，总能找到至少一个解。这使得经济学家和其他社会科学家可以充满信心地构建基于纳什均衡的理论模型来分析复杂的策略互动。
• 广泛的应用：该定理支持了对寡头垄断市场（如古诺模型和伯特兰模型）、拍卖理论、公共选择、国际关系等众多领域的分析。

局限

• 非构造性：定理只告诉我们均衡存在，但没告诉我们如何找到它。在复杂博弈中，计算纳什均衡是一个非常困难的问题，属于计算复杂性理论中的 PPAD 完全问题。
• 多重均衡：一个博弈可能存在多个纳什均衡。定理不提供选择哪一个均衡的标准，这导致了“均衡选择”问题。
• 效率问题：纳什均衡不一定是帕累托最优的。囚徒困境就是最经典的例子，其纳什均衡对所有参与者来说都是一个次优的结果。
• 混合策略的解释：混合策略的现实解释存在争议。它究竟是代表参与者主动的随机化选择，还是代表群体中不同个体采取纯策略的比例分布，或者是其他参与者对某人行为的不确定性信念，这些至今仍在讨论中。