⚛ 纳什均衡

Nash equilibrium theory!

由于春节档电影太贵了，囊中羞涩的小U只好蜷缩在被窝里与影视娱乐软件作伴.

翻来翻去觉得最近没有啥有意思的影视剧，便默默地调整了索引年份.秉持着随机观影的原则，小U闭眼控制鼠标点击了一部影视，wow~ ⊙o⊙，一睁眼看片名<<美丽心灵>>，不明觉厉,但也没有想到这部电影剧情竟是如此跌宕起伏，并且科气十足≡(▔﹏▔)≡，主人公John·Nash(The 1994 Academic Nobel Prize winner)引起了小U的兴趣，啊等等，小U的意思是，他的学术成果引起了小U的兴趣~

小U决定，今天浅尝辄止地了解一下他的丰功伟业.

What is Nash Equilibrium

纳什均衡是博弈论中的一个概念.

纳什均衡可以这样阐述：一次博弈中的最优结果就是在没有激励因素的条件下偏离初始策略，即在考虑了他们的对手的策略后，没有玩家有偏离他们已选择策略的激励因素.

这么官方的话术显然不太算”人话”，总的来说可以这么理解————在你的对手都不改变其博弈策略的情况下，你做出策略改变，不会对你最终的收益产生任何增益.一场博弈可能有很多纳什均衡，也可能没有.

文字语言看不懂，不妨看数学语言.

我们用$(S,F)$表征M位决策者参与博弈的游戏，$S_{i}$是第i位决策者的所有可能策略集合，$S=\prod_{i=1}^{M}S_{i}$表示该博弈游戏的全部策略集合，$F(x)=(F_{1}(x),…F_{M}(x))$是$x\in S$时的收益函数.

当每位玩家都选择了自己的策略后，第i位玩家的收益可以表征为：
$F_{i}(x)=F_{i}(x=(x_{1}…x_{j},…x_{M})),x_{j}\in S_{j},j=1,2…M$

显然每个玩家的最终收益与每位玩家所采取的策略有关.

如果没有任何一个玩家可通过单方面改变策略获取更多收益，则这个策略集x∈S 就是纳什均衡，即：
∀i,xᵢ ∈ Sᵢ :Fᵢ(xᵢ, x₋ᵢ) ≥ Fᵢ(xᵢ,x₋ᵢ),x*₋ᵢ=$(x_{1},x_{2},…x_{j},…),j\neq i$

How to form an understanding

1. 纳什均衡是博弈论中的一个决策定理，它表明决策者在不偏离初始策略的情况下可以达到预期的结果
2. 在纳什均衡中，在考虑到其余对手的策略后，每一位决策者的策略都是最优的，每一位决策者都是赢家，因为他们都实现了自己的预期
3. 纳什均衡常与优势策略结合讨论.优势策略是说，不管对手选择怎样的策略，决策者所选区的策略将在所有可行的策略中带来更好的结果
4. 纳什均衡并不总是意味着选择最优策略

Comparison with Dominant

纳什均衡常与优势策略相比较，两者都是博弈论中的策略.

纳什均衡表明决策者的最优策略是：在知道对手策略的情况下，只要其他参与人不改变策略，只需要保持初始策略不变即可

而如前所述，最优策略是说，不论对手采取什么样的策略，决策者所选择的策略在所有可行的策略中会带来更大的收益

最优策略可以包含在纳什均衡中，而纳什均衡可能不是博弈中的最佳策略

博弈论的所有模型都是在假定参与者是“理性行动者”的情况下才有效，这意味着他们渴望特定的结果，试图选择最优的结果，在决策中包含不确定性，他们的选择具有现实意义.

Have fun with games

Game

Prisoner's dilemma

玩一个囚徒困境的游戏.

游戏规则可能大家都很熟悉，但不妨在此重述一遍：执法机关怀疑A,B涉及一桩刑事案件，于是将其分别独立监禁，并且二人没有任何沟通的手段.但检察官也没有证据证明两人有罪，因此，检方给每个嫌犯提供机会————要么背叛对方，要么保持沉默.

判刑规则如下：双方都背叛对方，每人喜提5年监禁；但一方背叛，背叛者无罪释放，另一方喜提10年监禁；双方保持沉默，各方喜提1年监禁.

容易分析，假定A知道B会背叛他，显然这时A也选择背叛的收益最大，而改变自己的策略不会带来任何增益；假定A知道B不会背叛他，显然A仍然选择背叛的收益还是最大，改变策略显然也不会产生任何增益.因此，在这个问题中，纳什平衡是指双方都背叛对方，尽管我们也可以看到对A来说，这显然不是最优解.

Some FAQ

Is Nash Equilibrium reasonable

1. 并行
   通常情况下一个问题可能会有很多纳什均衡(NE).
2. 选择
   假设参与者上演的是纳什均衡，但作为旁观者，我们很难确定他们选择的是什么样的纳什均衡，有些纳什均衡相比更加合理.
3. 弱化
   有时纳什均衡很强烈，但对短期收益来说，人们通常不上演纳什均衡，需要提出一个弱化的观点来适应实际博弈问题

Is NE always exist

是不是所有的博弈都存在纳什平衡？看看下面的例子

E.X First Price Auction (FPA)

在拍卖中都是价高者得，假设意见拍品有n位竞标者，他们的最高出价能力满足$v_{1}>v_{2}>…>v_{n}>0$, 每轮竞价举牌时的竞标价分别为$b_{i}$,用$b=(b_{1},b_{2},…,b_{n})$表征弈论的竞价集，第i位竞价者竞拍成功时，他的实际收益是$v_{i}-b_{i}$如果出现平价，最终竞得者将被随机指派，并且竞拍者都希望收益最大化，那么在这个问题中是否存在纳什均衡呢？

我们不禁想知道什么情况下才会存在纳什均衡

Nash Existence Theorem
假设$A_{i}$是$R^{k}$上的一个非空的、紧凑的、凸的子集，在博弈游戏$(N,A_{i},u_{i})$中，对于任意给定的$a_{-i}\in A_{-i},i\in N$,$u_{i}$在A中是连续的，并且在$A_{i}$中是拟凹的，那么就存在纳什均衡

说实话，小U也还没看懂这个定理的定义是什么意思，定义中有些拓扑学的概念，为了解决这个麻烦，我们先讲一会儿拓扑学！

被迫引入的拓扑学

Topology

为了快速解决这个麻烦，下面我们尽量用人话简要的学习一下与拓扑有关的内容

Metric Space

度量空间简单来说就是一个集合.

度量空间是一种具有度量函数，或者叫做距离函数的集合.这个函数定义了集合内所有元素的距离.

度量空间中最容易直观理解的就是三维欧氏空间，概念metric可以认为是欧氏距离性质的推广

度量空间是一个有序对，记作(X,d)，其中X是一个集合，d是X上的度量函数，$X\times X\rightarrow [0,\infty)$，它把X中的每一对点(x,y)映射到一个非负实数，并且满足如下四条性质：

1. 非负性：$d(x,y)\ge 0$
2. 唯一性：$d(x,y)=0\Leftrightarrow x=y$
3. 对称性：$d(x,y)=d(y,x)$
4. 三角不等式：$x,y,z\in X,d(x,z)\le d(x,y)+d(y,z)$

常见的度量空间有n维欧氏空间、赋范向量空间(比如曼哈顿范数)等

Open & Closed set

开集就是一个不包含边界的集合

比如我们熟悉的开区间就是一个二维开集

开集的严格定义如下：对于$\forall a\in A,\exists r>0,s.t. B(r,a))\subseteq A$，其中$B(r,a)$是一个让所有两点距离$d(a,b)<r$的集合，那么A就是一个开集

开集有如下性质：

1. 若干个开集的连集仍然是开集
2. 有限个开集的交集，仍然是开集
3. 全集R和空集也属于开集
4. 开集里所有的点都是极限点，也都是内点

闭集就是一个补集为开集的集合，闭集是一个包含所有其极限点的集合

Points

极限点、边界点、孤立点、内点、外点…..你是什么点？

极限点的定义是：对于$\forall P,if B(r,P)\bigcap A\neq \phi or P$，那么P为A的极限点. 更像人话的表述是，极限点的邻域必须与集合A相交，且包含一个不是自己的点.

边界点的定义是：对于$\forall P,if B(r,P)\bigcap A\neq\phi$并且$B(r,P)\forall A^c\neq\phi$，那么P为A的边界点，更像人话的表述就是边界点的邻域必须同时与集合A和A的补集相交

在度量空间为欧氏空间时，所有的孤立点都是边界点

边界点与极限点没有必然联系

孤立点的定义是：对于$\forall P\in A, if B(r,P)\bigcap A=P$，那么P为A的孤立点，人话翻译过来就是，孤立点的邻域与集合A的交集就是他自己

内点就是邻域完整包含在集合A内的点，而外电显然就是邻域完全在集合A以外的点

Compact set

紧集的定义是：若A的任意开覆盖，都存在有限子覆盖，那么A为紧集

开覆盖就是一堆开集的连集(即并集)，有限子覆盖的意思就是有限个开集的连集

紧集的性质是：紧集是闭集且有界

Connected set

连通集的定义是：若A不可被分割成两个不相交的开集，那么A为连通集

连通空间的定义是：若度量空间X不能被分解成两个非空的、不相交的闭集的并，那么X为连通空间

至此，我们结束了拓扑学导引

角谷静夫不动点定理：设A为$R^n$中的一个紧致凸集，对于$\forall x\in A$，如果$f(x)$是A的一个非空凸集且在A上半连续，则必定存在x使$x\in f(x)$

John·Nash利用不动点定理证明了纳什均衡，但小U数学水平不高，还看不懂他的论文，就不能往下展开了

Further explanation

纳什在他的论文中提出了两种关于均衡的想法：一种基于理性，一种基于统计人群.

在理性解释下，玩家们被认定为理性的，而且知晓游戏的全部信息，包含其他玩家的选择偏好，而且这些消息都是众所周知的。由于所有的玩家都了解彼此的选择策略和偏好，所以也能为所有的策略计算其收益，得到最佳策略。如果游戏只玩一次且所有的玩家都期望相同的纳什均衡（高收益），那么没有人会想要改变自己的策略.

基于统计人群的假设中，纳什指出：不必假设玩家完全了解游戏的信息，或者有能力和意愿进行复杂的推理过程。这是由于“假设在游戏的每个位置都有一群玩家，随着时间变化，会有随机玩家参与游戏。如果有玩家用一个稳定的平均频率来选用纯策略，那么这个稳定的平均频率就是混合策略纳什均衡。”.

混合策略纳什均衡是一种策略集，其特征是至少有一个参与者在玩随机策略，并且没有一个参与者可以通过单方面改变和轮换策略来获得更高的期望收益.

纳什的结果表明，在所有有限对策中至少存在一个纳什均衡点.

[1]incentive:激励
[2]assert:断言
[3]compact:紧凑的
[4]:convex:凸的

[1]Nash Equilibrium,JAMES CHEN,Investopedia
[2]Nash Equilibrium - University of California, Los Angeles
[3]Nash Equilibrium - Animation assistance