CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
===== 有限二人零和博弈 =====

设 $A\in\mathbb{R}^{n\times m}$，$X=\{1,2,\cdots,n\}$，$Y=\{1,2,\cdots,m\}$（即 $X$，$Y$ 均为有限集），$X$ 表示玩家 I 的（纯）策略集合，$Y$ 表示玩家 II 的（纯）策略集合。若玩家 I 选择纯策略 $i\in X$，玩家 II 选择纯策略 $j\in Y$，那么玩家 I 将获得 $A_{ij}$ 的收益，玩家 II 将获得 $-A_{ij}$ 的收益（零和）。注意在该游戏的原始定义中，两人应当同时提出策略，即不知道对方的策略。此外，不妨将玩家 II 的收益也称为 $A$，但是他的目标是最小化之。

此外，考虑混和策略 $X^{*}$ 和 $Y^{*}$：

$$
X^{*}=\{\boldsymbol{p}=(p_{1},p_{2},\cdots,p_{n})^{T}:p_{i}\ge0\land\sum_{i=1}^{n}p_{i}=1\}\\
Y^{*}=\{\boldsymbol{q}=(q_{1},q_{2},\cdots,q_{m})^{T}:q_{i}\ge0\land\sum_{i=1}^{m}q_{i}=1\}
$$

含义为玩家 I 以 $p_{i}$ 的概率选择纯策略 $i$。下文中，不加说明的策略均指混合策略。

现在改变一下游戏规则，不妨假设玩家 II 需要先声明自己的策略，玩家 I 随后选择自己的策略。那么玩家 I 选择策略 $\boldsymbol{p}$ 的收益是 $\boldsymbol{p}^{T}A\boldsymbol{q}$。显然玩家 I 将选择对于特定的 $\boldsymbol{q}$ 收益最大的 $\boldsymbol{p}$，玩家 II 则在玩家 I 选择的基础上选择收益最小的 $\boldsymbol{q}$。那么玩家 I 的收益将是

$$
\overline{V}=\min_{\boldsymbol{q}\in Y^{*}}\max_{\boldsymbol{p}\in X^{*}}\boldsymbol{p}^{T}A\boldsymbol{q}
$$

可以发现，这意味着玩家 II 可以在原游戏中保证自己的收益不超过 $\overline{V}$，他只要选择同样的操作即可。

将两人的操作顺序反过来，同理有

$$
\underline{V}=\max_{\boldsymbol{p}\in X^{*}}\min_{\boldsymbol{q}\in Y^{*}}\boldsymbol{p}^{T}A\boldsymbol{q}
$$

这意味着玩家 I 可以在原游戏中保证自己的收益不低于 $\underline{V}$，他只要选择同样的操作即可。

首先证明 $\underline{V}\le\overline{V}$，这对于任意集合 $X^{*}$ 和 $Y^{*}$ 和定义在 $X^{*}\times Y^{*}$ 上的实值函数 $f$ 都成立，即证明

$$
\max_{x\in X^{*}}\min_{y\in Y^{*}}f(x,y)\le\min_{y\in Y^{*}}\max_{x\in X^{*}}f(x,y)$$

注意到

$$
\min_{y'\in Y^{*}}f(x,y')\le f(x,y)\le \max_{x'\in X^{*}}f(x',y)
$$

对任意 $x,y$ 都成立。因此对左侧加上 $\max_{x\in X^{*}}$，右侧加上 $\min_{y\in Y^{*}}$ 不影响不等式。

事实上，可以证明在这一问题中，$\underline{V}=\overline{V}$。注意到在上述两种简化问题中，后手必然有最优的纯策略。事实上最优的策略是所有最优的纯策略的线性组合。考虑线性规划问题

$$
\text{maximize}\;\;\;\;\;\;\min_{j\in Y}\sum_{i=1}^{n}p_{i}a_{ij}
$$

s.t.

$$
\sum_{i=1}^{n}p_{i}=1\\
p_{i}\ge0
$$

但是这不是个线性规划，因为优化目标中有个 $\min$。添加一个辅助变量 $v$：

$$
\text{maximize}\;\;\;\;\;\;v
$$

s.t.

$$
v\le\sum_{i=1}^{n}p_{i}a_{ij}\text{ for all } j\\
\sum_{i=1}^{n}p_{i}=1\\
p_{i}\ge0
$$

它的解即为 $\underline{V}$。

考虑另一个线性规划：

$$
\text{minimize}\;\;\;\;\;\;v
$$

s.t.

$$
v\le\sum_{j=1}^{m}a_{ij}q_{j}\text{ for all } i\\
\sum_{j=1}^{m}q_{j}=1\\
q_{j}\ge0
$$

它的解即为 $\overline{V}$。

注意到这两个线性规划互为对偶，因而有 $\underline{V}=\overline{V}$。记该值为 $V$，称为该游戏的值。这一定理称为最小最大值定理。

这样一来，玩家 I 可以保证自己至少获得 $V$ 的收益，玩家 II 可以保证对方至多获得 $V$ 的收益。那么显然两人都会按照这样的策略行动。这也预示着该问题可用线性规划求解。
CVBB ACM Team

用户工具

站点工具

页面工具
