\newcommand\norm[1]{\left\lVert#1\right\rVert} \newcommand\abs[1]{\left\lvert#1\right\rvert}

Pure Strategy Games

策略博弈说的是有限个玩家，每个玩家都有有限个决策，并且每个玩家的决策必须同时作出（即不能知悉其他人的决策），每个玩家都知道每一种决策组合的结果给每个玩家带来的收益。

形式化地，有

1. $N$ 个玩家构成有限的玩家集

2. 每个玩家 $i$ 都有一个有限的决策集 $A_i$，表示其所有可以选择的决策

3. 一个局面 $a\in A=\prod\limits_{i=1}^N A_i$，包含了场上所有玩家所作出的决策

4. 每个玩家 $i$ 都有一个收益函数 $u_i\colon A\mapsto \mathbb K$，其中 $\mathbb K$ 是一个全序集

之所以定义为全序集是因为并非所有收益都是可以计算出来的数值，但是我们希望任意两个收益是可以比较好坏的

为了简化，规定

1. $a_{i-1}\in A_{-i}=\prod\limits_{i\neq j} A_j$ 表示玩家 $i$ 的所有对手的某种决策局面

2. 由1，某个局面 $a$ 就可以写成是 $(a_i,a_{-i})$，注意到我们并不关心局面的枚举顺序，因此这里实际上是集合而不是笛卡尔积….

3. 记 $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}

这样的解构成了一个闭凸多边形，边界上的解代表某些约束取到了等号。