§15 对策论基础

C1 对策

1）基本要素：

• 局中人 $I$I：决策行动的参与者
• 策略集 $S_i,i\in I$Si​,i∈I：每一位参与者的决策行为集合
• 局势集：笛卡尔积 $S = S_1 \times S_2\times \dots\times S_n$S=S1​×S2​×⋯×Sn​
• 获利/支付函数：评价某一局势下参与者的获利$H_i(s),s = (s_1,s_2,\dots ,s_n)$Hi​(s),s=(s1​,s2​,…,sn​)

2）决策问题的分类：

• 局中人个数：二人对策、多人对策
• 获利函数代数和：零和对策、非零和对策
• 局中人策略集是否有限：有限对策、无限对策
• 是否合作：合作对策、非合作对策

C2 矩阵对策

1）矩阵对策：二人 有限 零和 对策

• 记法约定：局中人Ⅰ Ⅱ，策略集$S_1 = \{\alpha_1,\alpha_2,\dots,\alpha_m\},S_2 = \{\beta_1 ,\beta_2 ,\dots \beta_n\}$S1​={α1​,α2​,…,αm​},S2​={β1​,β2​,…βn​}，获利矩阵$A = (a_{ij})_{m\times n},a_{ij} = H(s_i,s_j),B= - A^T$A=(aij​)m×n​,aij​=H(si​,sj​),B=−AT。对策：$G = \{Ⅰ,Ⅱ;S_1,S_2,A\}$G={Ⅰ,Ⅱ;S1​,S2​,A}

2）平衡局势：$\exist a_{i^*j^*} :\max \limits_{i} \min \limits_{j} {a_{ij}} = a_{i^*j^*} = \min\limits_{j}\max\limits_{i} {a_{ij}}$∃ai∗j∗​:imax​jmin​aij​=ai∗j∗​=jmin​imax​aij​

• 称$V_G = a_{i^*j^*}$VG​=ai∗j∗​为矩阵对策G的值，对应的$\alpha_{i^*},\beta_{j^*}$αi∗​,βj∗​为最优纯策略

• 平衡局势存在的充要条件：$\exist a_{i^*j^*}:\forall i,j,a_{ij^*}\le a_{i^*j^*}\le a_{i^*j}$∃ai∗j∗​:∀i,j,aij∗​≤ai∗j∗​≤ai∗j​(行中最小列中最大)，即存在鞍点

• 鞍点性质：

  • 无差别性：两鞍点的获利取值相同
  • 可交换性：若$a_{i_1j_1},a_{i_2j_2}$ai1​j1​​,ai2​j2​​是鞍点，则$a_{i_1j_2},a_{i_2j_1}$ai1​j2​​,ai2​j1​​也是鞍点

3）混合策略：允许策略为策略集集上一个概率分布。

• 策略集：$S^* = \{x\in E^m |x_i\ge0,i=1,2,\dots,m,\sum_{i=1}^m = 1\}$S∗={x∈Em∣xi​≥0,i=1,2,…,m,∑i=1m​=1}
• 获利函数：$E(x,y) = x^TA \ y = \sum\limits_{i}\sum\limits_j a_{ij}x_iy_j$E(x,y)=xTA y=i∑​j∑​aij​xi​yj​
• 显然，纯策略是$x_i \in\{0,1\}$xi​∈{0,1}的特例
• 平衡局势：$\max\limits_{x\in S_1^*}\min\limits_{y\in S_2^*} {E(x,y)} = \min\limits_{y\in S_2^*}\max\limits_{x\in S_1^*}{E(x,y)} \iff \exist x^*,y^*:\forall x,y,E(x,y^*)\le E(x^*,y^*) \le E(x^*,y)$x∈S1∗​max​y∈S2∗​min​E(x,y)=y∈S2∗​min​x∈S1∗​max​E(x,y)⟺∃x∗,y∗:∀x,y,E(x,y∗)≤E(x∗,y∗)≤E(x∗,y)
• 注意到$\max\limits_{x\in S_1^*}\min\limits_{y\in S_2^*} {E(x,y)} \le \min\limits_{y\in S_2^*}\max\limits_{x\in S_1^*}{E(x,y)}$x∈S1∗​max​y∈S2∗​min​E(x,y)≤y∈S2∗​min​x∈S1∗​max​E(x,y)，即Ⅰ的有把握最大获利不会大于Ⅱ的有把握最低损失

4）矩阵对策基本定理：矩阵对策总是存在最优混合策略

• 记Ⅰ采取纯策略$\alpha_i$αi​时，相应的赢得函数为$E(i,y) = \sum\limits_ja_{ij}y_j$E(i,y)=j∑​aij​yj​

  记Ⅱ采取纯策略$\beta_i$βi​时，相应的赢得函数为$E(y,j) = \sum\limits_ia_{ij}x_i$E(y,j)=i∑​aij​xi​

  则有$E(x,y)=\sum\limits_iE(i,y)x_i=\sum\limits_jE(x,j)y_j$E(x,y)=i∑​E(i,y)xi​=j∑​E(x,j)yj​

• 平衡局势存在的其它充要条件：

  • $\exist x^*,y^*:\forall i,j, E(i,y^*)\le E(x^*,y^*)\le E(x^*,j)$∃x∗,y∗:∀i,j,E(i,y∗)≤E(x∗,y∗)≤E(x∗,j)

  • 以下两个方程组有同解$v$v
    $(Ⅰ)\begin{cases}\sum\limits_ia_{ij}x_i\ge v,j=1,2,\dots,n \\ \sum\limits_ix_i=1 \\ x_i\ge0,i=1,2,\dots,m\end{cases} (Ⅱ)\begin{cases}\sum\limits_ia_{ij}y_j\le v,i=1,2,\dots,m \\ \sum\limits_jy_j=1 \\ y_j\ge0,j=1,2,\dots,n\end{cases}$(Ⅰ)⎩⎪⎪⎪⎨⎪⎪⎪⎧​i∑​aij​xi​≥v,j=1,2,…,ni∑​xi​=1xi​≥0,i=1,2,…,m​(Ⅱ)⎩⎪⎪⎪⎨⎪⎪⎪⎧​i∑​aij​yj​≤v,i=1,2,…,mj∑​yj​=1yj​≥0,j=1,2,…,n​

  • 此时$v = V_G$v=VG​

• 基本定理的构造性证明：求解以下对偶线性规划问题
  $\begin{aligned} & \ \ \ \max w \\(P)&\begin{cases}\sum\limits_ia_{ij}x_i\ge w,j=1,2,\dots,n \\ \sum\limits_ix_i=1 \\ x_i\ge0,i=1,2,\dots,m\end{cases} \\& \ \ \ \min v \\(D)&\begin{cases}\sum\limits_ia_{ij}y_j\le v,i=1,2,\dots,m \\ \sum\limits_jy_j=1 \\ y_j\ge0,j=1,2,\dots,n\end{cases} \end{aligned}$(P)(D)​   maxw⎩⎪⎪⎪⎨⎪⎪⎪⎧​i∑​aij​xi​≥w,j=1,2,…,ni∑​xi​=1xi​≥0,i=1,2,…,m​   minv⎩⎪⎪⎪⎨⎪⎪⎪⎧​i∑​aij​yj​≤v,i=1,2,…,mj∑​yj​=1yj​≥0,j=1,2,…,n​​

• 最优混合策略的性质：

  设$(x^*,y^*)$(x∗,y∗)为矩阵对策$G$G的解，$v = V_G$v=VG​，则

  • $x_{i^*}\gt0\implies\sum\limits_ja_{ij}y_{j^*}=v$xi∗​>0⟹j∑​aij​yj∗​=v

    $y_{j^*}\gt0\implies\sum\limits_ia_{ij}x_{i^*}=v$yj∗​>0⟹i∑​aij​xi∗​=v

  • $\sum\limits_ja_{ij}y_{j^*}\lt v\implies x_{i^*}=0$j∑​aij​yj∗​<v⟹xi∗​=0

    $\sum\limits_ia_{ij}x_{i^*}\gt v\implies y_{j^*}=0$i∑​aij​xi∗​>v⟹yj∗​=0

5）记矩阵对策$G$G的解集为$T(G)$T(G)

• 设有2个矩阵对策$\begin{cases}G_1 =\{S_1,S_2,A_1\}\\G_2=\{S_1,S_2,A_2\}\end{cases}${G1​={S1​,S2​,A1​}G2​={S1​,S2​,A2​}​，其中$A_1=(a_{ij}),A_2=(a_{ij}+L)$A1​=(aij​),A2​=(aij​+L)

  则有$V_{G_2}=V_{G_1}+L,T(G_1)=T(G_2)$VG2​​=VG1​​+L,T(G1​)=T(G2​)

• 设有2个矩阵对策$\begin{cases}G_1 =\{S_1,S_2,A\}\\G_2=\{S_1,S_2,\alpha A\}\end{cases}${G1​={S1​,S2​,A}G2​={S1​,S2​,αA}​

  则有$V_{G_2}=\alpha V_{G_1}+L,T(G_1)=T(G_2)$VG2​​=αVG1​​+L,T(G1​)=T(G2​)

• 若$A$A为斜对称矩阵($A=-A^T$A=−AT，又称对称对策)，则$V_G=0,T_1(G)=T_2(G)$VG​=0,T1​(G)=T2​(G)。$T_1(G),T_2(G)$T1​(G),T2​(G)为Ⅰ,Ⅱ最优策略集

6）优超策略：$\forall j,a_{i_1j}\ge a_{i_2j}$∀j,ai1​j​≥ai2​j​，称策略$\alpha_{i_1}$αi1​​优超$\alpha_{i_2}$αi2​​。即无论Ⅱ做出何种决策，策略$\alpha_{i_1}$αi1​​总是比$\alpha_{i_2}$αi2​​获利更多

• 若$\alpha_i$αi​被其余所有策略优超，或被其线性组合优超，去除该策略对应的行，新对策的最优解仍是原对策最优解。

  (注意到，这种表述说明可能导致解集变小，但是$V_G$VG​不会发生变化)

7）解法：

• 通过优超策略的化简，有时可化为简单的形式

  • $2\times2$2×2矩阵对策：先寻找鞍点，若无鞍点，解方程组

  $(Ⅰ)\begin{cases}a_{11}x_1 + a_{21}x_2=v\\a_{12}x_1 + a_{22}x_2=v\\x_1+x_2=1\end{cases} ,(Ⅱ)\begin{cases}a_{11}y_1 + a_{12}y_2=v\\a_{21}y_1 + a_{22}y_2=v\\y_1+y_2=1\end{cases}$(Ⅰ)⎩⎪⎨⎪⎧​a11​x1​+a21​x2​=va12​x1​+a22​x2​=vx1​+x2​=1​,(Ⅱ)⎩⎪⎨⎪⎧​a11​y1​+a12​y2​=va21​y1​+a22​y2​=vy1​+y2​=1​

  • $2\times n$2×n矩阵对策：图解法。做两垂线。0处做垂线标注$a_{1j},j=1,2,\dots,n$a1j​,j=1,2,…,n,1处做垂线标注$a_{2j},j=1,2,\dots ,n$a2j​,j=1,2,…,n。连接$a_{1j}a_{2j},j=1,2,\dots,n$a1j​a2j​,j=1,2,…,n,最低交点为所求
  

• 线性方程组方法：注意利用最优混合策略的性质化简矩阵
  $(Ⅰ)\begin{cases}\sum\limits_ia_{ij}x_i= v,j=1,2,\dots,n \\ \sum\limits_ix_i=1 \\ x_i\ge0,i=1,2,\dots,m\end{cases} (Ⅱ)\begin{cases}\sum\limits_ia_{ij}y_j= v,i=1,2,\dots,m \\ \sum\limits_jy_j=1 \\ y_j\ge0,j=1,2,\dots,n\end{cases}$(Ⅰ)⎩⎪⎪⎪⎨⎪⎪⎪⎧​i∑​aij​xi​=v,j=1,2,…,ni∑​xi​=1xi​≥0,i=1,2,…,m​(Ⅱ)⎩⎪⎪⎪⎨⎪⎪⎪⎧​i∑​aij​yj​=v,i=1,2,…,mj∑​yj​=1yj​≥0,j=1,2,…,n​
  若无非负解，需要将部分等式改为不等式，根据共轭定理对偶使一些量为0

• 线性规划方法：

  • 先查找鞍点

  • 再验证$v=0 = V_G$v=0=VG​是否满足

  • 求解矩阵对策$G = \{S_1,S_2,\frac{1}{v}A\}$G={S1​,S2​,v1​A}，即：
    $(Ⅰ)\begin{cases}\sum\limits_ia_{ij}x_i'= 1,j=1,2,\dots,n \\ \max{\sum\limits_ix_i'} \\ x_i\ge0,i=1,2,\dots,m\end{cases} (Ⅱ)\begin{cases}\sum\limits_ia_{ij}y_j'= 1,i=1,2,\dots,m \\ \min{\sum\limits_jy_j'} \\ y_j'\ge0,j=1,2,\dots,n\end{cases}$(Ⅰ)⎩⎪⎪⎪⎨⎪⎪⎪⎧​i∑​aij​xi′​=1,j=1,2,…,nmaxi∑​xi′​xi​≥0,i=1,2,…,m​(Ⅱ)⎩⎪⎪⎪⎨⎪⎪⎪⎧​i∑​aij​yj′​=1,i=1,2,…,mminj∑​yj′​yj′​≥0,j=1,2,…,n​
    一般从Ⅱ开始解，可以在开始就找到一个基本可行解

  • 由解集性质得到原对策的解

C3 其它类型对策简介

1）二人无限零和对策：

• 最优纯策略：$\max\limits_{\alpha\in S_1}\min\limits_{\beta\in S_2}{H(\alpha,\beta)}=\min\limits_{\beta\in S_2}\max\limits_{\alpha\in S_1}{H(\alpha,\beta)}=H(\alpha^*,\beta^*)\iff\exist\alpha^*,\beta^*: \forall \alpha,\beta,H(\alpha,\beta^*)\le H(\alpha^*,\beta^*)\le H(\alpha^*,\beta)$α∈S1​max​β∈S2​min​H(α,β)=β∈S2​min​α∈S1​max​H(α,β)=H(α∗,β∗)⟺∃α∗,β∗:∀α,β,H(α,β∗)≤H(α∗,β∗)≤H(α∗,β)

• 混合策略：策略为策略集上一个连续型概率分布

  • 获利函数：$H(X,y)=\int_{S_1}{H(x,y)}\mathrm{d}F_X;H(x,Y)=\int_{S_2}{H(x,y)}\mathrm{d}F_Y;H(X,Y)=\int_{S_1}\int_{S_2}H(x,y)\mathrm{d}F_XF_Y$H(X,y)=∫S1​​H(x,y)dFX​;H(x,Y)=∫S2​​H(x,y)dFY​;H(X,Y)=∫S1​​∫S2​​H(x,y)dFX​FY​

  • 最优混合策略：

    $\sup\limits_X\inf\limits_Y{H(X,Y)}=\inf\limits_Y\sup\limits_X{H(x,y)}=V_G\iff \exist X^*,Y^*:\forall X,Y,H(X,Y^*)\le H(X^*,Y^*)\le H(X^*,Y)$Xsup​Yinf​H(X,Y)=Yinf​Xsup​H(x,y)=VG​⟺∃X∗,Y∗:∀X,Y,H(X,Y∗)≤H(X∗,Y∗)≤H(X∗,Y)

• 连续对策：$S_1 = S_2 =[0,1],H(x,y)\in C(S_1\times S_2)$S1​=S2​=[0,1],H(x,y)∈C(S1​×S2​)

  • 连续对策一定有最优混合策略

2）多人非合作对策：

• 局中人：$I=\{1,2\dots,n\}$I={1,2…,n}

• 局势：$s = (s_1,s_2,\dots,s_n)\in S_1\times S_2\times\dots\times S_n$s=(s1​,s2​,…,sn​)∈S1​×S2​×⋯×Sn​，记更换局势分量i(局中人i改变策略)为 $s\lVert s_i^0$s∥si0​

• 获利函数：$H_i(s)$Hi​(s)

• 纯策略平衡局势：$\forall i \in I,s_i^0\in S_i:H_i(s)\ge H_i(s\lVert s_i^0)$∀i∈I,si0​∈Si​:Hi​(s)≥Hi​(s∥si0​)，即所有人在该局势下改变策略不会带来更多获利

• 混合局势：$x = (x^1,x^2,\dots,x^n),x^i$x=(x1,x2,…,xn),xi为局中人$i$i的一个混合策略。$E_i(x)$Ei​(x)为该局势下局中人$i$i的获利期望，局中人$i$i改变策略为：$x\lVert z_i$x∥zi​

  混合策略平衡局势：$\forall i\in I,z_i,E(x\lVert z_i)\le E(x_i)$∀i∈I,zi​,E(x∥zi​)≤E(xi​)

• Nash定理：非合作n人对策在混合策略意义下的平衡局势一定存在

  • 特化：二人有限非零和对策（双矩阵对策）$\forall x,y:x^{*T}Ay^*\ge x^TAy^*,x^{*T}By^*\ge x^{*T}By$∀x,y:x∗TAy∗≥xTAy∗,x∗TBy∗≥x∗TBy

3）合作对策：允许形成联盟

​