Pure Strategy Games
策略博弈说的是有限个玩家，每个玩家都有有限个决策，并且每个玩家的决策必须同时作出（即不能知悉其他人的决策），每个玩家都知道每一种决策组合的结果给每个玩家带来的收益。
形式化地，有
\(N\) 个玩家构成有限的玩家集
每个玩家 \(i\) 都有一个有限的决策集 \(A_i\)，表示其所有可以选择的决策
一个局面 \(a\in A=\prod\limits_{i=1}^N A_i\)，包含了场上所有玩家所作出的决策
每个玩家 \(i\) 都有一个收益函数 \(u_i\colon A\mapsto \mathbb K\)，其中 \(\mathbb K\) 是一个全序集
之所以定义为全序集是因为并非所有收益都是可以计算出来的数值，但是我们希望任意两个收益是可以比较好坏的
为了简化，规定
\(a_{i-1}\in A_{-i}=\prod\limits_{i\neq j} A_j\) 表示玩家 \(i\) 的所有对手的某种决策局面
由1，某个局面 \(a\) 就可以写成是 \((a_i,a_{-i})\)，注意到我们并不关心局面的枚举顺序，因此这里实际上是集合而不是笛卡尔积....
记 \(B_i(a_{-i})=\underset{a_i}{\arg\max}\; u_i(a_i,a_{-i})\) 为玩家 \(i\) 的所有对手选择了 \(a_{-i}\) 决策时，所有能最大化玩家 \(i\) 的收益的决策集，称为 \(i\) 的 Best Response
Dominant Strategy
对于玩家\(i\)而言，某些决策严格劣于其余决策，因此是绝对不会选的，可以直接删掉。
上述过程可以持续进行直至不存在被严格支配的决策，这样可以化简求解时的难度
Nash Equilibrium
若一个局面 \(a=(a_i,a_{-i})\) 满足对于一切的玩家 \(i\) 都有命题 \(\forall c\in A_i\) ，\(U_i(a_i,a_{-i})\succeq U_i(c,a_{-i})\) 成立，那么称局面 \(a\) 为一个（单一策略的）纳什均衡点
可以这么考虑：在纳什均衡的局面下，每个玩家单方面地作出决策变动都将让ta的收益下降。
一个简单的求解套路是对每个玩家 \(i\) 求出 \(U_i(\cdot)\)，然后求 \(\dfrac{\partial}{\partial a_i} U_i(a_i,a_{-i})\) 来得到一个 \(a_i^{*}\in B_i(a_{-i})\)。显然在均衡点时，每个玩家都要最大化，那么联立求解就得到了一组解 \(a^*=(a_i^*,a_{-i}^*)\)。
注意这里的纯策略纳什均衡不一定存在，反例非常好找。并且若存在也不一定唯一，例如"剪刀石头布"的博弈模型就有三个均衡点。
求解PNE
可以枚举所有的outcome来逐一判断每个人是否都达到了最优，可以看成寻找一个超立方体上的“鞍点”。
Mixed Strategy Game
纯策略意味着每个人的决策是唯一确定的，这个前提太强。一个放松是给出选择每个决策的概率，即一个 \(A_i\) 上的概率分布 \(p_i\)
记 \(\Delta(A_i)\) 为玩家 \(i\) 的决策集 $A_i $ 上所有可能的概率分布的集合，那么每个玩家的决策就会是一个决策集上的分布 \(p_i\in \Delta(A_i)\)
同样记 \(p=(p_i,p_{-i})\)
给出 \(U_i(p)=\sum\limits_{a\in A}Pr[X=a]u_i(X)\)，其中 \(X\sim p\) 为一个随机变量
注意到每个玩家互不交流，因此它们的决策相互独立，拆开就得到 \(U_i(p)=\sum\limits_{a\in A}u_i(a)\prod\limits_{i=1}^N p_j(a_j)\)，这其实就是一个收益的期望，随机性来源于 \(N\) 个独立分布的叠加。
定理1
若 \(p=(p_i,p_{-i})\) 是一个纳什均衡，那么所有使得 \(p_i(a)>0\) 的决策 \(a\) 都将会是局面 \((a,p_{-i})\) 的 Best Response。
意思是对于一个纳什均衡的局面 \(p=(p_i,p_{-i})\)，在固定了对手的所有决策分布之后，玩家 \(i\) 可能选择的单一决策（概率不为 \(0\) 的那些决策）的每一个都将是应对 \(p_{-i}\) 的最佳选择。
证明只需要反证一下，假设某个 \(p_i(a)>0\) 但 \(a\not\in B_i(p_{-i})\)，那么构造一个新的分布 \(p_i'\) 满足 \(p_i'(a)=0\) 且其余非零位置都乘上 \(\frac1{1-p_i(a)}\)，可以证明新的分布下将达到更大的 \(U_i(p_i')\)，这与 \((p_i,p_{-i})\) 是纳什均衡矛盾；但是反过来不一定成立，例如可以存在多个单独最优解，但是我们不随机，只选择其中一个策略。
这个引理还是比较强的，说明即使引入了随机性，每个玩家的选择仍然是固定的，只不过现在变成了固定的集合。
Mixed Nash Equilibrium
每个finite strategy game都有至少一个混合策略的纳什均衡，称为Mixed Nash Equilibrium(MNE)
这个定理也是Nash证明的，算是比较漂亮的定理了。
求解MNE
profile enumeration
对于一个非退化的2人游戏，可以 \(2^n\) 枚举概率非 \(0\) 的决策解一个不等式组。不妨设枚举出的行抽取出的矩阵为 \(A\)，那么对于玩家1而言必然有 \(Aq\) 的每一元素都相等（根据定理1）且严格大于剩余行的期望收益。
vertex enumeration
可以发现上面等价于给定原收益矩阵 \(M\)，要求对于玩家1而言满足
\[\begin{aligned} \forall \text{distribution } q \\ Mq\ge v\textbf1 \\ \text{maximize } v \end{aligned}\]这样的解构成了一个闭凸多边形，边界上的解代表某些约束取到了等号。