博弈论：纳什均衡
著名的纳什均衡(Nash equilibrium)由美国数学家John Forbes Nash Jr.于1950年发表。在一个博弈过程中，无论对方的策略选择如何，当事人一方都会选择某个确定的策略，则该策略被称作支配性策略。
如果两个博弈的当事人的策略组合分别构成各自的支配性策略，那么这个组合就被定义为纳什均衡。一个策略组合被称为纳什均衡，当每个博弈者的均衡策略都是为了达到自己期望收益的最大值，与此同时，其他所有博弈者也遵循这样的策略。
用一个大白话来说，就是在一场博弈中，每个玩家都不愿意主动更改自己的策略。
纳什均衡实验：猜数字游戏
斯坦福的公开课上举了一个例子来说明纳什均衡。猜数字游戏要求每个人从1-100中选择一个整数，最后从最接近平均值三分之二的人中随机选一个获得奖励，假设参加这项游戏的人数足够多。
在这种情况下，纳什均衡会是多少呢？由于获胜者要求是接近平均值的三分之二，如果我们假设大家的选择都是均匀分布，那均值应该是$50$，最终最可能获胜的数字应该是$50\times \frac{2}{3} =33$
而如果获胜数字最有可能是$33$，那最有可能获胜的数字应该是$30\times \frac{2}{3} =22$
再往下，最有可能获胜的数字应该是$22\times \frac{2}{3} =11$
……
到了最后，假设大家都是理智的，纳什均衡的解将是0。这时候最终获奖者将随机从0中选出。
这是一个美国的真实实验，最终结果中，2%的实验者选择了$66$、5 %选择了$50$、10 %选择了$33$、6 %选择了$22$、12 %选择了$0$或者$1$。但最后的获胜数字为$19$。这也说明了实际博弈中，不是所有玩家都是理性的。
纳什均衡
在之前提到的囚徒困境中，纳什均衡点将是双方都招供，因为在未知对方选择的情况下，招供是己方的支配性策略(Strongly dominates)。所谓支配型策略，就是指一个策略在任何时刻的效用都最大。
相对的，如果一个策略在任何状态下的效用都不小于另一个策略，则被称为弱支配策略(Weakly dominates)。
如果一个决策支配其他所有决策，那么称之为占优策略。如果该决策严格压制每一个其他决策，那么称之为严格占优策略，并且该策略唯一。由占优策略组成的策略组合一定是纳什均衡点，全部由严格占优策略组成的策略组合一定是唯一的纳什均衡点。
硬币正反游戏
百度百科的纳什均衡条目下给出了一个游戏：
两个人玩一个硬币正反的游戏，规则是：双方各自亮出硬币的一面，或正或反。如果我们都是正面，则玩家A给玩家B$3$元，如果都是反面，玩家A给玩家B$1$元，剩下的情况玩家B给玩家A$2$元。现在问题是，这个游戏对A公平吗？
每一种游戏依具其规则的不同会存在两种纳什均衡，一种是纯策略纳什均衡，也就是说玩家都能够采取固定的策略(比如一直出正面或者一直出反面)，使得每人都赚得最多或亏得最少；或者是混合策略纳什均衡，而在这个游戏中，便应该采用混合策略纳什均衡。
可以构建一个收益矩阵：
| 玩家B/玩家A | 正面 | 反面 |
|---|---|---|
| 正面 | (3, -3) | (-2, 2) |
| 反面 | (2, -2) | (1, -1) |
假如A出正面的概率是X，反面概率是1-X，B出正面的概率是Y，反面是1-Y。为了利益最大化，应该使得B无论什么决策时的收益都相等（因为对手一旦改变决策的策略就会使得A的收益下降）。
A的期望收益可以列出方程如下：
$3y+(-2)\times (1-y)=(-2)\times y+1\times (1-y)$
$y=\frac{3}{8}$
B的期望收益则为：
$-3x+(-2)\times (1-x)=(-2)\times x+(-1)\times (1-x)$
$x=\frac{3}{8}$
对于B，每次博弈的期望收益是$2(1-x)-3x=\frac{1}{8}$元。这意味着，双方每次都采取最优策略时，平均每次B的收益都是$\frac{1}{8}$元。那么，只要B采取$\frac{3}{8}$，$\frac{5}{8}$的混合策略，就会立于不败之地。
如果A全出正面，那么每次的期望收益是$\frac{3+3+3-2-2-2-2-2}{8}=-\frac{1}{8}$元。
如果A全出反面，每次的期望收益也是$\frac{-2-2-2+1+1+1+1+1}{8}=-\frac{1}{8}$元。
如果A用完全随机$(\frac{1}{2}，\frac{1}{2})$策略，收益是$\frac{1}{2}(\frac{3}{8} * 3 + \frac{5}{8} * (-20)) + \frac{1}{2}(\frac{3}{8}* (-2) + \frac{5}{8} * 1) = -\frac{1}{8}$元。
这个问题还有另一种思考方式：只要A的期望不为$0$，这个游戏就对他不公平。而他的期望收益可以列为：
$E(A)=3p-2p-2(1-p)=p+2p-2=3p-2$
如果$E(A)=0$，那么这是公平的。此时求得$p$为$\frac{2}{3}$，即如果A按照$\frac{2}{3}$的概率选择正面，那么游戏就对他公平。
而这个游戏的纳什均衡是A选择正面，B选择正面，或A选择反面，B也选择反面。
如何挑选纳什均衡点？
从定义上来看，纳什均衡就是给定其他决策者的决策，每个决策者都没有单独改变决策的动机。（也就是当前决策是最优决策）
假设一共有A、B、C三个决策者，知A、B决策下C做出最优决策C*，已知A、C决策下B做出最优决策B*，已知B、C决策下A做出最优决策C*，则(A*,B*,C*)是一个纳什均衡点。
如何从决策矩阵中挑选纳什均衡点？
看该单元格，是否左侧的值是该列左侧值的最大值，右侧的值是否是该行右侧值的最大值。
| 1/2 | C | D |
|---|---|---|
| C | -1,-1 | -4,0 |
| D | 0,-4 | -3,-3 <–NE点 |
| 1/2 | C | D |
|---|---|---|
| C | 1，1 <–NE点 | 0,0 |
| D | 0,0 | 1，1 <–NE点 |
| 1/2 | C | D |
|---|---|---|
| C | 2，1 <–NE点 | 0，0 |
| D | 0，0 | 2，1 <–NE点 |
也存在无纯策略纳什均衡的情况，例如：
| 1/2 | C | D |
|---|---|---|
| C | 1,-1 | -1,1 |
| D | -1,1 | 1,-1 |
注意：
- 纳什均衡不一定是全局最优。比如囚徒困境。
- 纳什均衡也不是自发实现的，需要有一定的沟通协商规定，总之就是直接间接获取他人的决策信息。
帕累托最优
前面提到的纳什均衡是个体寻找自身的最佳策略，而在整个博弈中，要找到一个对大家都最优的策略，这就是帕累托最优(Pareto Optimality)。
帕累托最优的核心思想是，给定一组多目标或多标准的评价指标，如果没有办法在不损害任何一个目标的前提下改善其他目标，那么我们就说该解决方案是帕累托最优的。它要解决的问题就是多目标优化问题。
简单来说，如果一个解决方案或策略在满足所有给定标准或目标的同时，无法进一步改进或优化，那么它就被认为是帕累托最优的。
也就是说，我们从全局出发，只要有一个全局的策略组合对于所有玩家的效用都高，那么它就是帕累托最优，同时它对于其他策略组合产生了帕累托支配的关系。例如，如果有 $( \mathrm{\large O}(7,8) ) $和$ ( \mathrm{\large O}^{\prime}(4,5) )$，则 $(\mathrm{O}) Pareto-dominates (\mathrm{O}^{\prime}).$
注意：
- 一场游戏中可能有多个帕累托最优决策组合。
- 一场游戏中最少含有一个帕累托最优决策组合。
2023/12/31 于苏州家中