零和博弈#

零和博弈是一种最经典也是最特殊的博弈，博弈玩家一般只有两名，且均只有有限个战略。而博弈双方的利得矩阵之和必为零矩阵。

例1 考虑一零和博弈，其中玩家A和B各有战略$S_A=\{\alpha_1,\alpha_2,\alpha_3\}$，$S_B=\{\beta_1,\beta_2,\beta_3,\beta_4\}$

利得矩阵为

$$\mathbf M_A=\begin{bmatrix} 12 & -6 & 30 & -22\\ 14 & 2 & 18& 10\\ -6 & 0 & -10& 16 \end{bmatrix}$$

为满足所有矩阵的加和$\sum \mathbf M$为零矩阵，该例中B矩阵很明显为$\mathbf M_B=-\mathbf M_A$。另外，利得矩阵也可以用有序数对组的表格表示，该类表格被称为利得表

该博弈中，对于玩家A，由于30的利得远超所有其他情况能获得的利得，因此单纯地，玩家A始终会选择战略$\alpha_1$，而对于玩家B，很明显22的利得是全场最大的，因此玩家B也会始终选择战略$\beta_4$，由于利得是由双方共同决定的，若玩家B寻得其最优战略，则会导致玩家A的利得由30变为-22。考虑到此时双方的选择都会使得对方的损失最大化，因此合适的策略应该是在最坏的结果中寻找最好的结果。

因此对于玩家A，$\alpha_1$的最劣利得为$\min\{12,-6,30,-22\}=-22$，$\alpha_2$的最劣利得为$\min\{14,2,18,10\}=2$，$\alpha_3$的最劣利得为$\min\{-6,0,-10,16\}=-10$。而所有的最劣利得中，相对损失小的则为$\max\{-22,2,-10\}=2$，在这种情况下，无论玩家B选择何种战略，玩家A的损失都不会超过2。

而对于玩家B，同理可以知道最劣的利得中最优利得为$\max\{-14,-2,-30,-16\}=-2$。因此玩家A和玩家B都倾向于选择$\alpha_2$和$\beta_2$作为他们各自的战略。注意到在利得矩阵中，2 既是所在行中的最小元素又是所在列中的最大元素。此时，只要对方不改变战略，任一局中人都不可能通过变换战略来增大利得或减少损失，称这样的局势为博弈的一个稳定解或均衡解。亦或称为零和博弈的纳什均衡（Nash Equilibrium）。

注意到这样的性质，在零和博弈中，寻找最优的战略路径实际上在寻找局部的极值。我们引入如下的定义来使得其严格化。

定义1：设$f(x,y)$为一个定义在$\mathbb R$上的实值函数，且$x\in A,y\in B$，如果存在$x^*\in A,y^*\in B$使得对一切$x\in A$和$y\in B$有

则$f(x^*,y^*)$称为函数 $f$ 的一个鞍点。

定义2：存在一个零和博弈的空间$G=\{I,S_A,S_B,\mathbf M_I\}$，其中$S_A=\{\alpha_1,\alpha_2,\alpha_3\,...,\alpha_m \}$，$S_B=\{\beta_1,\beta_2,\beta_3,...,\beta_n \}$，$\mathbf M_I=[U_{ij}]_{m \times n}$，若等式

成立，则$U_G=U_{i^*j^*}$为该零和博弈的均衡利得，而满足上式的战略组合$(\alpha_{i^*},\beta_{i^*})$ 则被称为鞍点或者稳定解

由于博弈的利得矩阵是离散的，当博弈问题有解时，其解可以不唯一，当解不唯一时，解之间的关系具有下面两条性质：

性质1：无差别性 若战略组合集$S=\{(\alpha_{i_1},\beta_{j_1}),(\alpha_{i_2},\beta_{j_2}),...,(\alpha_{i_n},\beta_{j_n})\}$为博弈$G$的$n$个解，则必然有$U_{i_1j_1}=U_{i_2j_2}=...=U_{i_nj_n}$。

性质2：可交换性 若若战略组合集$S=\{(\alpha_{i_1},\beta_{j_1}),(\alpha_{i_2},\beta_{j_2}),...,(\alpha_{i_n},\beta_{j_n})\}$为博弈$G$的$n$个解，则任意两两战略角标的线性交换$(\alpha_{i_1},\beta_{j_2}),(\alpha_{i_1},\beta_{j_2})$等也是其中的解。