Tony102's Blog - 纳什均衡
type: channel
link: https://tony102.com/index.php/tag/%E7%BA%B3%E4%BB%80%E5%9D%87%E8%A1%A1/
items: 浅谈纳什均衡
items: 纳什均衡复杂度分析
items: CF98E Help Shrek and Donkey

浅谈纳什均衡
type: item
date: 2021-11-09T14:02:00+08:00
description: 什么是纳什均衡包含两个或以上参与者的非合作博弈（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从这个例子，也能看出来，解混合策略纳什均衡可以令参与人的各个纯策略收益相等，构成方程组求解。一个让人感叹书读少了的例子摸鱼一下，这个道理还是很深刻的。且不谈这个例子的严谨性（基本正确），但还是现实意…

纳什均衡复杂度分析
type: item
date: 2021-11-08T23:46:00+08:00
description: 《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]

CF98E Help Shrek and Donkey
type: item
date: 2021-11-08T20:25:00+08:00
description: 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…