Chapter08_对策论

1. 试述组成对策模型的三个基本要素及各要素的含义
   1. 局中人 在一个对策行为中，有权决定自己行动方案的对策参加者，称为局中人。常用 $I$ 表示局中人集合。若有 $n$ 个局中人，则有 $I=\{1,2,\cdots,n\}$。一般要求一个对策中至少有两个局中人。
   2. 策略集 一局对策中，可供局中人选择的一个实际可行的完整行动方案，称为一个策略；参加对策的每一局中人 $i,i\in I$，都有自己的策略集 $\mathbb{S}_i$。一般地，每个局中人的策略集至少包含两个策略。
   3. 赢得函数 每一句对策中，各组人选定的策略形成的策略组称为一个局势，即若 $s_i\in \mathbb{S}_i$ 是第 $i$ 个人的一个策略，则 $n$ 个人的策略组 $$s=(s_1,s_2,\cdots,s_n)$$称为一个局势；全体局势 $\mathbb{S}$ 的集合可用各局中人的策略集的笛卡尔积表示$$\mathbb{S} = \mathbb{S}_1 \times \mathbb{S}_2\times\cdots\times\mathbb{S}_n$$当一个局势出现后，对策的结果也就确定了。也就是对于任一局势 $s\in\mathbb{S}$，局中人 $i$ 可得到一个赢得值 $H_i(s)$。显然，$H_i(s)$ 是局势 $s$ 的函数，称为第 $i$ 个人的赢得函数。
2. 对策的常见分类方式
   1. 局中人个数：二人对策，多人对策；
   2. 各局中人的赢得函数的代数和是否为 $0$：零和对策，非零和对策；
   3. 各局中人是否允许合作：合作对策，非合作对策
   4. 局中人策略集中的策略个数：有限对策，无限对策；
3. 试述二人零和有限对策在研究对策模型中的地位、意义。为什么它又被称为矩阵对策？
   1. 矩阵对策是目前为止在理论研究和求解方法方面都比较完善的一种对策；尽管其是一类最简单的对策模型，但其研究思想和方法十分具有代表性，可体现对策论的一般思想和分析方法，且其基本结果也是研究其他对策模型的基础。
   2. 因为常用赢得矩阵来表示二人零和有限对策的赢得函数；故将二人零和有限对策称为矩阵对策。
4. 解释下列概念，并说明同组概念之间的联系和区别
   1. 策略，纯策略，混合策略；
      1. 策略：对策中局中人的一个可实施的完整行动方案；
      2. 纯策略：在对策中，局中人选择策略集中的某一单一策略作为应对方案。
      3. 混合策略：分别以一定概率选取纯策略得到的一种策略，称为混合策略。
   2. 鞍点，平衡局势，纯局势，纳什均衡纯策略意义下的解；
      1. 鞍点：设 $f(x,y)$ 是的定义在 $x\in \mathbb{A},y\in\mathbb{B}$ 的函数，若存在 $x^*\in\mathbb{A},y^*\in\mathbb{B}$，对一切 $x\in\mathbb{A},y\in\mathbb{B}$ 有 $$f(x,y^*)\le f(x^*,y^*)\le f(x^*,y)$$称 $(x^*,y^*)$ 为函数 $f$ 的一个鞍点
      2. 平衡局势：设 $G=\{\mathbb{S}_1,\mathbb{S}_2；\boldsymbol{A}\}$ 为一矩阵对策，其中 $\mathbb{S}_1=\{\alpha_1,\alpha_2,\cdots,\alpha_m\};\ \mathbb{S}_2=\{\beta_1,\beta_2,\cdots,\beta_n\},\boldsymbol{A} = (a_{ij})_{m\times n}$。若$$\max_i\min_j a_{ij} = \min_{j}\max_i a_{ij}$$成立，记其值为 $V_G = a_{i^*j^*}$，则称 $V_G$ 为对策 $G$ 的值，则称使得上式成立的纯局势 $(\alpha_{i^*},\beta_{j^*})$ 为 $G$ 在纯策略下的解（或平衡局势），$\alpha_{i^*}$ 与 $\beta_{j^*}$ 分别称为局中人 I，II 的最优纯策略。
      3. 纯局势：由各局中人的一个策略组成的策略组，$(s_1,\cdots,s_n)$ 称为一个纯局势
      4. 矩阵对策 $G$ 在纯策略意义下有解，且 $V_G=a_{i^*j^*}$ 的充要条件是 $a_{i^*j^*}$ 为矩阵 $\boldsymbol{A}$ 的一个鞍点。
   3. 混合扩充，混合局势，纳什均衡混合策略意义下的解；
      1. 混合扩充：设有矩阵对策 $G=\{S_1,S_2;\boldsymbol{A}\}$，其中 $\mathbb{S}_1=\{\alpha_1,\cdots,\alpha_m\},\mathbb{S}_2=\{\beta_1,\cdots,\beta_n\},\boldsymbol{A}=(a_{ij})_{m\times n}$ 记$$\begin{split}&S_1^*=\{\boldsymbol{x}\in \mathbb{E}^m\vert x_i\ge0,\quad i=1,\cdots,m,\quad\sum_{i=1}^{m}x_i=1\}\\&S_2^*=\{\boldsymbol{y}\in \mathbb{E}^n\vert y_j\ge0,\quad j=1,\cdots,n,\quad\sum_{j=1}^{n}y_j=1\}\end{split}$$则 $S_1^*,S_2^*$ 分别称为局中人 I 和局中人 II 的混合策略集；$\boldsymbol{x}\in S^*_{1}$ 和 $\boldsymbol{y}\in S_{2}^*$ 分别称为局中人 I 和局中人 II 的混合策略；对 $\boldsymbol{x}\in S_{1}^*,\boldsymbol{y}\in S^*_2$，则称 $(\boldsymbol{x},\boldsymbol{y})$ 是一个混合局势 局中人 I 的赢得函数 $$E(\boldsymbol{x},\boldsymbol{y}) = \boldsymbol{x}^\intercal \boldsymbol{Ay} = \sum_{i=1}^m\sum_{j=1}^n a_{ij}x_{i}y_j$$这样得到一个新的对策记为 $G^*=\{S_1^*,S_2^*;E\}$，称 $G^*$ 为对策 $G$ 的混合扩充
      2. 设 $G^*=\{S_1^*,S_2^*;E\}$ 是矩阵对策 $G=\{S_1,S_2;\boldsymbol{A}\}$ 的混合扩充，若 $$\max_{\boldsymbol{x}\in S_{1}^*}\min_{\boldsymbol{y}\in S_{2}^*} E(\boldsymbol{x},\boldsymbol{y}) = \min_{\boldsymbol{y}\in S_2^*}\max_{\boldsymbol{x}\in S_{1}^*} E(\boldsymbol{x},\boldsymbol{y})$$记其值为 $V_G$。则称 $V_G$ 为对策 $G^*$ 的值，使得上式成立的混合局势 $(\boldsymbol{x},\boldsymbol{y})$ 为 $G$ 在混合策略意义下的解，$\boldsymbol{x}^*,\boldsymbol{y}^*$ 分别称为局中人 I 和局中人 II 的最优混合策略
   4. 优超，某纯策略被另一纯策略优超，某纯策略为其他纯策略的凸线性组合所优超。
      1. 设有矩阵对策 $G=\{S_1,S_2;\boldsymbol{A}\}$，其中 $S_1=\{\alpha_1,\cdots,\alpha_m\},S_2=\{\beta_1,\cdots,\beta_n\},\boldsymbol{A}=(a_{ij})_{m\times n}$，若对一切 $j=1,\cdots,n$ 都有 $a_{i^0j}\ge a_{k^0j}$，即矩阵 $\boldsymbol{A}$ 的第 $i^0$ 行元素均不小于 $k^0$ 行元素，则称局中人 I 的纯策略 $\alpha_{i^0}$ 优超于 $\alpha_{k^0}$；若对一切 $i=1,\cdots,m$ 都有 $a_{ij^0}\le a_{il^0}$，即矩阵 $\boldsymbol{A}$ 的，则称局中人 II 的纯策略 $\beta_{j^0}$ 优超于 $\beta_{l^0}$
      2. 设有矩阵对策 $G=\{S_1,S_2;\boldsymbol{A}\}$，其中 $S_1=\{\alpha_1,\cdots,\alpha_m\},S_2=\{\beta_1,\cdots,\beta_n\},\boldsymbol{A}=(a_{ij})_{m\times n}$，若存在 $t_{i}\ge 0,\ i=0,2,\cdots,N$ 且 $\sum_{i=0}^Nt_{i}=1$ 使得对一切 $j=1,\cdots,n$ 都有 $$\sum_{i=0}^{N}t_ia_{i^0j}\ge a_{k^0j}$$则称对于当局者 I 的策略 $\alpha_{i^0},\alpha_{i^1},\cdots,\alpha_{i^t}$ 的凸组合优超于 $\alpha_{k^0}$
5. 纯策略意义下解的之间的性质：
   1. 性质1 无差别性：若$(\alpha_{i_1},\beta_{j_1})$ 和 $(\alpha_{i_2},\beta_{j_2})$ 是对策 $G$ 的两个解，则 $a_{i_1 j_1}=a_{i_2j_2}$
   2. 性质2 可交换性：若$(\alpha_{i_1},\beta_{j_1})$ 和 $(\alpha_{i_2},\beta_{j_2})$ 是对策 $G$ 的两个解，则 $(\alpha_{i_1},\beta_{j_2})$ 和 $(\alpha_{i_2},\beta_{j_1})$ 也是解。
6. 矩阵策略的基本定理
   1. 定理1 设 $x^*\in S_1^*, y^*\in S_2^*$，则 $(x^*,y^*)$ 是 $G$ 的解的充分必要条件是，对于任意 $i=1,\cdots,m;j=1,\cdots,n$，有 $$E(i,y^*)\le E(x^*,y^*)\le E(x^*,j)$$
   2. 定理2 设 $x^*\in S_1^*, y^*\in S_2^*$，则 $(x^*,y^*)$ 是 $G$ 的解的充分必要条件是：存在数 $v$，使得 $x^*,y^*$ 分别是不等式组 $(\mathrm{I})$ 和 $(\mathrm{II})$ 的解，且 $v=V_G$ $$\begin{split}&(\mathrm{I})\begin{cases}\displaystyle\sum_{i} a_{ij}x_{i}\ge v &(j=1,\cdots,n)\\ \displaystyle\sum_ix_i = 1\\ x_{i}\ge 0 &(i=1,\cdots,m)\end{cases}\\\\&(\mathrm{II})\begin{cases}\displaystyle\sum_{j} a_{ij}y_{j}\le v &(i=1,\cdots,m)\\ \displaystyle\sum_j y_j = 1\\ y_{j}\ge 0 &(j=1,\cdots,n)\end{cases}\end{split}$$
   3. 定理3 对于任意矩阵对策 $G=\{S_1,S_2;\boldsymbol{A}\}$，一定存在混合策略意义下的解。
   4. 定理4 设 $(\boldsymbol{x}^*,\boldsymbol{y}^*)$ 是矩阵对策 $G$ 的解，$v=V_G$，则
      1. 若 $x_i^* >0$，则 $\underset{j}{\sum}a_{ij}y_{j}^* = v$
      2. 若 $y^*_j>0$，则 $\underset{i}{\sum}a_{ij}x_{i}^* = v$
      3. 若 $\underset{j}{\sum}a_{ij}y_{j}^* < v$，则 $x_i^* =0$
      4. 若 $\underset{i}{\sum}a_{ij}x_{i}^* < v$，则 $y_j^* =0$
   5. 定理5 设有两个对策矩阵 $$\begin{split}&G_1=\{S_1,S_2;\boldsymbol{A}_1\}\\&G_2=\{S_1,S_2;\boldsymbol{A}_2\}\end{split}$$其中 $\boldsymbol{A}_1=(a_{ij}); \boldsymbol{A}_2=(a_{ij} + L)$，$L$ 为任一常数，则
      1. $V_{G_{1}} + L = V_{G_{2}}$
      2. $T(G_1)=T(G_2)$
   6. 定理6 设有两个对策矩阵 $$\begin{split}&G_1=\{S_1,S_2;\boldsymbol{A}\}\\&G_2=\{S_1,S_2;a\boldsymbol{A}\}\end{split}$$其中 $a>0$ 为任一常数，则
      1. $aV_{G_1}=V_{G_2}$
      2. $T(G_1)= T(G_2)$
   7. 定理7 设 $G=\{S_1,S_2;\boldsymbol{A}\}$ 为一矩阵对策，且 $\boldsymbol{A}=-\boldsymbol{A}^\intercal$ 为斜对称矩阵（此种对策称为对称对策），则
      1. $V_G=0$
      2. $T_1(G)=T_2(G)$，其中 $T_1(G)$ 和 $T_2(G)$ 分别为局中人 I 和 II 的最优策略集。
7. 矩阵对策的解法
   1. 公式法 $2\times 2$ 对策 $$\begin{split}&(\rm I) \begin{cases}a_{11}x_1 + a_{12} x_{2} = v\\a_{21}x_1 + a_{22} x_{2} = v\\x_1 + x_{2} = 1\\x_1,x_2\ge0\end{cases}\\\\&(\rm II) \begin{cases}a_{11}y_1 + a_{21} y_{2} = v\\a_{12}y_1 + a_{22} y_{2} = v\\y_1 + y_{2} = 1\\y_1,y_2\ge0\end{cases}\end{split}$$联立即可解得。
   2. 图解法 $2\times n$ 或 $m\times 2$
   3. 线性方程组法$$\begin{split}&(\mathrm{I})\begin{cases}\displaystyle\sum_{i} a_{ij}x_{i}= v &(j=1,\cdots,n)\\ \displaystyle\sum_ix_i = 1\\ x_{i}\ge 0 &(i=1,\cdots,m)\end{cases}\\\\&(\mathrm{II})\begin{cases}\displaystyle\sum_{j} a_{ij}y_{j} = v &(i=1,\cdots,m)\\ \displaystyle\sum_j y_j = 1\\ y_{j}\ge 0 &(j=1,\cdots,n)\end{cases}\end{split}$$
   4. 线性规划法 令 $\boldsymbol{x}'= \boldsymbol{x}/v；\boldsymbol{y}'= \boldsymbol{y}/v$ 通过线性规划问题 $$\begin{split}&(\mathrm{I})\begin{cases}\displaystyle\min z=\sum_i x_i' \\\displaystyle\sum_{i} a_{ij}x'_{i}\ge 1 &(j=1,\cdots,n)\\ x_{i}\ge 0 &(i=1,\cdots,m)\end{cases}\\\\&(\mathrm{II})\begin{cases}\displaystyle \max w=\sum_jy_j\\\displaystyle\sum_{j} a_{ij}y'_{j}\le 1 &(i=1,\cdots,m)\\ y_{j}\ge 0 &(j=1,\cdots,n)\end{cases}\end{split}$$显然，$(\rm I),(\rm II)$ 互为对偶问题；而 $V_{G} = 1/\sum x_i = 1/\sum y_j$
8. 怎样理解参与对策的各局中人都是“理性”的假设？
9. 在一场羽毛球团体赛中，对阵双方各出三名单打和两对双打，若 A 队有四名单打预选和三对双打预选，试述该队教练对出场布局有多少策略。