什么是纳什均衡包含两个或以上参与者的非合作博弈（Non-cooperative game）中，假设每个参与者都知道其他参与者的均衡策略的情况下，没有参与者可以透过改变自身策略使自身受益时的一个概念解。经济学概念？我不懂。社会学？也不懂OI 中的纳什均衡主要是用来解决一个这样的问题：假如博弈的各方都不知道对方的决策，仅仅依赖于当前自己的最优情况进行决策。且每一方都按照这样的方法进行决策后，每一方的期望收益都不会更多。这样的期望收益点就是纳什均衡点。其中决策不带概率的被称为：纯策略纳什均衡 (pure strategies)；决策有概率的称为：混合策略纳什均衡 (Mixed strategies)。可能会写一点英文表述，不是我想讲洋文，而是想方便大家看那篇论文的时候快速找到需要看的部分。形象一点就是这样：当然，纯策略的纳什均衡肯定是一条直线的。这样有马鞍面的收益期望函数的肯定是混合策略纳什均衡。注意，这里没有写双方或者多方。实际上，在 The Complexity of Nash Equilibria 这篇论文中详细介绍了几种纳什均衡的时间复杂度。总的来说，如果是非匿名的多玩家（ > 2） 策略为有限集的话，那么这是一个 NP-C 问题。如果是一个匿名的 n-Players ，策略集大小为 $|k|$ 的一个纳什均衡，则存在近似意义下的多项式时间求解纳什均衡点的算法。应该是 $O(n^k)$ 的算法。（例如 CF98E）具体这篇论文只需要看 Chapter 5 的内容即可，其实只看 Chapter 5.1 $\sim$ 5.5 的内容即可。不是很难懂，认真看是可以理解的。关于时间复杂度，稍后再讨论。主要讨论混合策略的纳什均衡，原因有两点：纯策略相当于混合策略的一个子集OI 中考察混合策略的题目更加有趣和挑战性此外，OI 中考察的纳什均衡应均为匿名博弈。纳什均衡在做什么事如果一个策略组合使任何一个参与人的策略都是相对于其他参与人的策略的最佳策略，这个策略就构成一个纳什均衡，不管这个策略是混合策略还是纯策略。这是纳什均衡的基础：每个人都选择相对于他人最利自己的策略，当每个人都这样选择并且无法更大任何一人的收益时即达到纳什均衡。形式化一点可能还好理解一些。以两个人举例。现在有一排蛋糕，Alice 有 $p$ 的概率吃第 $i$ 个，第 $i$ 个蛋糕的美味度是 $a_i$。那么 Alice 的总收益是：$\sum p_ia_i$。当然 Bob 不可能不吃（不吃则 Bob 没有达到相对于 Alice 自身利益最大）。若要达到纳什均衡，也就是 Bob 无论再怎么吃都不可能收获更多美味度。那么最大的肯定是 $\max\limits_{i=1}^{n} {p_ia_i}$ ，这样 Bob 这样吃是最佳的。其它怎么吃都不可能比这个优。因此，Alice 的期望收益（上面的乘了概率 $p_i$ 所有都应该是在期望意义下的）就是 $\sum p_ia_i - \max\limits_{i=1}^{n} {p_ia_i}$ 。Alice 也要自身最优，所以要求 $\max$ 这个式子。此时有一个结论（下文同样会再次引出），每个参与人的混合策略都使其余参与人的任何纯策略的期望收益相等。所以当 $\forall i, p_ia_i$ 尽可能相当时该式可以得到一个 $\max$ 。应该大概能看出来，纳什均衡都是在相互之前自利的情况下的最佳策略。并且一个重要结论就是每个参与人的混合策略都使其余参与人的任何纯策略的期望收益相等。这是 OI 中运用纳什均衡解决博弈问题的基础。接下来会继续探讨。石头剪刀布现在有两个玩家玩石头剪刀布，我们用 R P S 来分别代表石头、布、剪刀。如果平局收益为 $0$ ，胜一局收益为 $1$ ，负一局收益为 $-1$。下面通过一个表格来说明这个游戏：P1\P2RPSR(0,0)(-1,1)(1,-1)P(1,-1)(0,0)(-1,1)S(-1,1)(1,-1)(0,0)我们设两人都有 $p_1, p_2, p_3$ 的概率出 R,P,S. 那么若要达到纳什均衡，则应该两人的混合策略都使对方的纯策略期望收益相等，也就是：$-1 \cdot p_2 + p_3 = -1 \cdot p_3 + p_1 = -1 \cdot p_1 + p_2$为了强调 $1/-1$ 所以符号为负的项都写在了前面。可以解得上面的方程组的为：$p_1 = p_2 = p_3 = \frac{1}{3}$。也就是说，在纳什均衡的意义下，双方应等概率随机出 R,P,S从这个例子，也能看出来，解混合策略纳什均衡可以令参与人的各个纯策略收益相等，构成方程组求解。一个让人感叹书读少了的例子摸鱼一下，这个道理还是很深刻的。且不谈这个例子的严谨性（基本正确），但还是现实意义沉重。如果你喜欢一个女孩子。现在女孩子把你当很好很好的朋友。如果你表白，女孩子觉得这样当朋友太尴尬了，那以后可能一起玩的机会都没有了。如果女孩子把你拒绝了，她也就失去了一个很好的朋友，这一点对现在的她来说也不是好的结果。于是你们俩，谁都不愿主动做出改变，即纳什均衡。你们俩在信息不完全下达到了各自的最优。但对于外人来看却不是。作者：Ciel链接：https://www.zhihu.com/question/19804990/answer/154928632来源：知乎例题1：CF98E单独写了题解，直接丢链接：CF98E例题2：20211108 游戏 (game)单独写了题解，直接丢链接：20211108 游戏 (game)再探时间复杂度开头已经说过了,非匿名的纳什均衡点求解是 NP-C 的。下面均值讨论有限策略集的匿名纳什均衡点求解。首先什么样的博弈是匿名博弈。不可以顾名思义地认为是博弈方不带名字就是匿名，而是博弈方的收益仅取决于他的策略，而不取决于他的身份。例如，司机造成的延误取决于路线上的汽车数量，而不是司机的身份。另一个例子如在拍卖中，其中一个出价人的效用受其他出价人出价的分布影响，但不受其他出价人身份的影响。结论开头已经给出：匿名的 n-Players ，策略集大小为 $|k|$ 的一个纳什均衡，求解均衡点的复杂度是 $O(n^k)$。具体证明在原论文中：Chapter 5.2 介绍了匿名博弈，Chapter 5.3 定义了本章所有符号和定义。Chapter 5.4 主要证明了该结论。后面的章节可能意义就不大了。下面来简要介绍原论文的论述。首先给出了一个解决纳什均衡点的基本操作：我们并非要直接求这个点，而是求选择每一个策略的概率 $p_i$。设 $z$ 是一个足够大的自然数，那么每一个 $p_i$ 都是 $z$ 的整数倍。我们可以用动态规划来求解这个概率 $p_i$ 。事实上，每个玩家一共有不超过 $(z+1)^{k-1}$ 中策略集，所以 $n$ 个玩家划分这些方案的数量最多是 $n^{(z+1)^{k-1} - 1}$ 。然后比较最大的即可。原论文指引回了 Chapter 5.1 中的一些结论，可以了解一下。不多赘述。这样一来，你感觉 CF98E 就是一道跟着论文走的题。通解其实通过上面的描述，已经可以感受到在 OI 中纳什均衡的的求法了。再次强调，我们仅可以解决匿名博弈下的纳什均衡点。通过 dp / 记忆话搜索都可以做划分数 dp，dp 的状态就是划分。转移的时候做如下步骤：计算当前状态下的纳什均衡点 $p$根据 $p$ 点算出当前状态的最大期望收益这样大概就是纳什均衡在 OI 中的一般运用了。（主要纳什均衡的题目实在是太少了，几乎没有）如果是纯策略的话，直接求解线性方程组了。线性空间与纳什均衡纯策略的时候相当于最有期望可以被一条直线所表示，我们要做的是解方程组。那么混合策略的时候是不是也有类似的性质呢？当然是有的，在论文中证明复杂度的时候就是把策略看成一个 $k$ 维向量。当然，因为这跟解题没啥关系，不重要，了解即可。
《The Complexity of Nash Equilibria》by Constantinos Daskalakis这是这位神仙的博士毕业论文，学校很漂亮，2015 年的时候有幸参观过一次（加州大学伯克利分校），特别是它的“南瓜塔”拜读了他的这篇分析。传一下方便继续阅读。[button color="info" icon="" url="https://tony102.com/usr/uploads/2021/11/3711154289.pdf" type=""]《The Complexity of Nash Equilibria》[/button]
LinkSol入门纳什均衡。联考题里面别人介绍的一种方法，就是说假如两个人以上的一个非合作博弈中，每个人都知道对方的每一个策略的收益，并且每一个人都做出最符合自己利益的情况的决策，无一参与者可以“独自行动”（即单方面改变决定）而增加收获时的策略就是纳什均衡点。求出纳什均衡点是 NP-完全的，在参与者匿名的情况下，则仅需多项式时间即可逼近纳什均衡。回到本题。现在 A 有 $n$ 张牌，$B$ 有 $m$ 张牌，牌山里只有一张牌。假如先手根本就不问 B，上来直接猜，那么猜中的概率是 $\frac{1}{m+1}$ 。 很显然，然而只有青铜这么做，因为只要对方的牌还没有空，那么通过“指定”操作，仍然可以保持 $\frac{1}{m+1}$ 的胜率并且知道对方一张牌使得概率提升。设 $f(n,m)$ 表示先手有 $n$ 张牌，后手有 $m$ 张牌时，先手胜的概率。每次的收益就是获得的概率提升。注意，这里的先后手并非常规博弈意义下的先后手必胜的那种，仅仅用于描述当前操作的人是谁（相对关系），可能大家都懂，但是这里我卡了一下子才绕过来，只有青铜实锤了。假如 A 现在是先手， A 此时会问 B 一张自己手中没有的牌。假如 B 手中有这张牌，那么 B 会鸣出这张牌，先后手交换。那么 A 获得的收益即为：$\frac{m}{m+1} (1 - f(m - 1, n))$ （有 $\frac{m}{m+1}$ 的概率猜的牌在 B 手中，将牌鸣出且交换了以后的先手不胜的概率为 $1 - f(m-1,n)$）；若 B 手中没有这张牌，则 B 认为 A 问的牌就是牌山里唯一的牌，A 的收益为 $\frac{1}{m+1} \cdot 0$ 。如果以为这就完了，那可能连白银都打不过。A 现在不仅可以问 B 自己手中没有的牌，还可以诈 B 一手：问自己手中有的牌，让 B 迷雾。感觉这是这题比较有趣的一个地方。现在情况发生了改变，我们来梳理一下加上这种情况后会发生什么。原先的情况依然可能发生。我们称 A 不诈 B （即问自己手中有的牌）的情况叫做以和为贵，诈 B 的情况叫做不讲武德。同时 B 也可以选择相信 A 不诈和诈两种情况，分别称做相信和不信。下面通过一个表格 $w$ 来说明 A 的收益情况并解释：后手\先手以和为贵（不诈）不讲武德（诈他）相信$0 \cdot \frac{1}{m+1}$$1 \cdot \frac{1}{m+1}$不信$\frac{m}{m+1} (1-f(m-1,n))$$1 - f(m,n-1)$原先分析的不诈的情况就是第二列。现在分析第三列。假如 A 诈 B，可是 B 仍然相信 A 没有在诈，则 B 相信 A 没有这张牌即该牌在牌山里，错误，那么 A 再次操作的时候必胜。则猜中这张牌的概率为 $\frac{1}{m+1}$ 必胜概率为 $1$ ，乘在一起就是 $1 \cdot \frac{1}{m+1}$。如果 B 没有相信 A（认为 A 在诈），那么 B 会回答没有且不会鸣出任何牌。相当于此时 A、B 先后手转换，且 A 损失一张牌。即 $1 - f(m,n-1)$。同时注意边界情况，当 $m = 0$ 时先手必知牌山里的牌，胜率 $1$ ；当 $n=0$ 时，先手不猜则先后手转换后先手变成后手且必败，胜率为 $0$此时引入纳什均衡，设 A 有 $p$ 的概率以和为贵，$1-p$ 的概率不讲武德。纳什均衡就是要在该决策的情况下，无论怎么样获得的收益都均衡（不动点）。即：$$ p \cdot w_{1,1} + (1-p) \cdot w_{2,1} = p \cdot w_{1,2} + (1-p) \cdot w_{2,2} $$移项即可解得：$p = \frac{w_{2,2} - w_{2,1}}{w_{1,1}-w_{2,1}-w_{1,2}+w_{2,2}}$每次转移就是：$f_{n,m} = w_{1,1} \cdot p + (1 - p) \cdot w_{2,1}$Idea这种决策带概率的属于混合策略的纳什均衡。如果决策不依靠概率，则为纯策略型的纳什均衡。一般就是有一些决策的概率是需要确定的，且决策后的收益可以算。这个时候要求确定的一个值（纳什均衡点）使得每一个决策方获得收益都不会在变（即达到均衡）。很有意思的一个算法。Code#include <bits/stdc++.h> using namespace std; const int SIZE = 1e3 + 5; int m, n; double f[SIZE][SIZE]; double dp(int x, int y) { if (f[x][y]) return f[x][y]; if (!y) return f[x][y] = 1.000; if (!x) return f[x][y] = 1.000 / (y + 1); double w11 = 1.000 * y / (y + 1) * (1.000 - dp(y - 1, x)), w21 = 1.000, w12 = w11 + 1.000 / (y + 1), w22 = 1.000 - dp(y, x - 1); double p = (w21 - w22) / (w12 + w21 - w11 - w22); return f[x][y] = p * w11 + (1.000 - p) * w21; } int main() { scanf("%d %d", &m, &n); double p = dp(m, n); printf("%.10lf %.10lf\n", p, 1.000 - p); return 0; }