规划法求解Nash均衡

两人的情况

原理

所谓规划求解法，就是将求解博弈问题的混合战略Nash均，转换为一个规划问题进行求解。相对于支撑求解法，规划求解法对两人有限博弈问题的Nash均衡求解尤为有效。下面对规划求解法的基本原理和步骤进行介绍。

在一个两人有限战略式博弈中，设 $S1={s_1^1,…,s_1^m},S_1={s_2^1,…,s_2^n}$ 。用矩阵 $\mathbf U_1=(a{ij}){m\times n}$ 表示参与人 $1$ 的支付，其中 $a$ 表示参与人 $1$ 在战略组合 $(s_1^i,s_2^j)$ 下的支付，即 $a{ij}=u1(s_1^i,s_2^j)$ ；用矩阵 $\mathbf U_2=(b{ij}){m\times n}$ 表示参与人 $2$ 的支付，其中 $b{ij}$ 表示参与人 $2$ 在战略组合 $(s1^i,s_2^j)$ 下的支付，即 $b{ij}=u_2(s_1^i,s_2^j)$ 。设参与人 $1$ 和参与人 $2$ 的混合战略分别为 $\boldsymbol \sigma_1=(\sigma_1^1,\cdots,\sigma_1^m) $和$\boldsymbol \sigma_2=(\sigma_2^1,\cdots,\sigma_2^n) $,则

$v_1(\boldsymbol {\sigma_1,\sigma_1})=\boldsymbol {\sigma_1 U_1\sigma_2^T}\\ v_2(\boldsymbol {\sigma_1,\sigma_1})=\boldsymbol {\sigma_1 U_2\sigma_2^T}$

一个两人有限战略式博弈的 Nash均衡可以通过求解以下规划问题得到：

$\begin{aligned} &\max &&z =\boldsymbol{\sigma_{1}U_{1}\sigma_{2}^{T}-v_{1}+\sigma_{1}U_{2}\sigma_{2}^{T}-v_{2}} \\ &\text{s.t.}&& \boldsymbol{U_{1}\sigma_{2}^{T}\leq\upsilon_{1} E_{m}^{T}}\\ &&&\left(\boldsymbol{\sigma}_{1}\boldsymbol{U}_{2}\right)^{\mathrm{T}}\leqslant\boldsymbol{\upsilon}_{2}\boldsymbol{E}_{n}^{\mathrm{T}} \\ &&&\boldsymbol {\sigma_{1}E_{m}^{\mathrm{T}}=\sigma_{2}E_{n}^{\mathrm{T}}}=1 \\ &&&\sigma_{1}^{i}\geqslant0,i=1,\cdots,m \\ &&&\sigma_{2}^{j}\geqslant0,j=1,\cdots,n \end{aligned}$

其中，

$\boldsymbol E_m=[1,\cdots ,1]_{1\times m}\\ \boldsymbol E_n=[1,\cdots ,1]_{1\times n}$

$v_1、v_2$ 分别是参与人 $1$ 和参与人 $2$ 在Nash均衡下的期望支付。

例

	$A(\sigma_2^A)$	$B(\sigma_2^B)$	$C(\sigma_2^C)$	$D(\sigma_2^D)$
$U(\sigma_1^U)$	$3,5$	$1,4$	$5,7$	$4,2$
$L(\sigma_1^L)$	$4,3$	$2,5$	$0,3$	$2,6$

上述博弈问题中，

$\boldsymbol U_1= \begin{bmatrix} 3 & 1 &5 &4\\ 4 &2 &0 &2 \end{bmatrix} \qquad \boldsymbol U_2= \begin{bmatrix} 5 & 4 &7 &2\\ 3 &5 &3 &6 \end{bmatrix} \\ \boldsymbol \sigma_1=(\sigma_1^U,\sigma_1^L) \qquad \boldsymbol \sigma_2=(\sigma_2^A,\sigma_2^B,\sigma_2^C,\sigma_2^D)$

设 $\boldsymbol {v_1、v_2}$ 分别是参与人 $1$ 和参与人 $2$ 在Nash均衡下的期望支付。

我们可以列出来以下方程:

$\begin{aligned} \max \quad z &=\begin{pmatrix} \boldsymbol \sigma_{1}^{U} & \boldsymbol \sigma_{1}^{L} \end{pmatrix} \begin{bmatrix} 3 & 1 & 5 & 4 \\ 4 & 2 & 0 & 2 \end{bmatrix} \begin{pmatrix} \boldsymbol \sigma_{2}^{A} \\ \boldsymbol \sigma_{2}^{B} \\ \boldsymbol \sigma_{2}^{C} \\ \boldsymbol \sigma_{2}^{D}\end{pmatrix} - \boldsymbol v_1 \\ &\quad + \begin{pmatrix} \boldsymbol \sigma_{1}^{U} & \boldsymbol \sigma_{1}^{L} \end{pmatrix} \begin{bmatrix} 5 & 4 & 7 & 2 \\ 3 & 5 & 3 & 6 \end{bmatrix} \begin{pmatrix}\boldsymbol { \boldsymbol \sigma_{2}^{A} \\ \boldsymbol \sigma_{2}^{B} \\ \boldsymbol \sigma_{2}^{C} \\ \boldsymbol \sigma_{2}^{D} }\end{pmatrix} - \boldsymbol v_2 \\ \text{s.t.} \quad & \begin{bmatrix} 3 & 1 & 5 & 4 \\ 4 & 2 & 0 & 2 \end{bmatrix} \begin{pmatrix} \boldsymbol\sigma_{2}^{A} \\ \boldsymbol \sigma_{2}^{B} \\ \boldsymbol \sigma_{2}^{C} \\ \boldsymbol \sigma_{2}^{D} \end{pmatrix} \leqslant \begin{pmatrix} \boldsymbol v_1 \\ \boldsymbol v_1 \end{pmatrix}, \\ &\left(\begin{pmatrix} \boldsymbol \sigma_{1}^{U} & \boldsymbol \sigma_{1}^{L} \end{pmatrix} \begin{bmatrix} 5 & 4 & 7 & 2 \\ 3 & 5 & 3 & 6 \end{bmatrix}\right)^T \leqslant \begin{pmatrix} \boldsymbol v_1 \\ \boldsymbol v_2 \\ \boldsymbol v_3 \\ \boldsymbol v_4 \end{pmatrix}, \\ &\boldsymbol {\sigma_{1}^{U} + \sigma_{1}^{L}} = 1, \\ &\boldsymbol {\sigma_{2}^{A} + \sigma_{2}^{B} + \sigma_{2}^{C} + \sigma_{2}^{D}} = 1, \\ &\boldsymbol \sigma_{1}^{U} \geq 0, \ \boldsymbol \sigma_{1}^{L} \geq 0, \\ &\boldsymbol \sigma_{2}^{A} \geq 0, \ \boldsymbol \sigma_{2}^{B} \geq 0, \ \boldsymbol \sigma_{2}^{C} \geq 0, \ \boldsymbol \sigma_{2}^{D} \geq 0. \end{aligned} $$ {&} 求解上述规划问题，可以得到三个Nash均衡，即一个纯战略Nash均衡和两个混合战略Nash均衡:$

(U,C)\
\left(
\left(\frac{1}{3},\frac{2}{3}\right),
\left(0,\frac{2}{3},0,\frac{1}{3}\right)
\right)\
\left(
\left(\frac{2}{5},\frac{3}{5}\right),
\left(0,\frac{5}{6},\frac{1}{6},0\right)
\right)

$## 多人博弈情况利用规划问题求解Nash均衡的思路，还可以推广到有限 $n$ 人的战略式博弈 $G=<\Gamma;S_1,\cdots,S_n;u_1,\cdots,u_n>$ ,对 $\forall i \in \Gamma$ ,设$S_{i}=\left\{s_{i}^{1},\cdots,s_{i}^{K_{i}}\right\},\sigma_{i}=\left(\sigma_{i}^{1},\cdots,\sigma_{i}^{K_{i}}\right)$,求解下列规划问题即可得到博弈问题的解。$

\begin{aligned}
&\max z = && \sum{i=1}^{n}\left(v{i}\left(\boldsymbol \sigma{i},\boldsymbol \sigma{-i}\right) - \boldsymbol v{i}\right) \
&\text{s.t.} && v{i}\left(s{i}^{j},\boldsymbol \sigma{-i}\right) \leqslant \boldsymbol v{i}, && \forall i \in \Gamma, \forall s{i}^{j} \in S{i}, \
&&& \sum{j} \boldsymbol \sigma{i}^{j} = 1, && \forall i \in \Gamma, \
&&& \boldsymbol \sigma{i}^{j} \geqslant 0, && \forall i \in \Gamma, \forall j \in \left{1,\cdots,K_{i}\right}.
\end{aligned}

$其中， $\boldsymbol v_i(i=1,\cdots,n)$ 为参与人 $i$ 在Nash均衡下的期望支付。 # 零和博弈所谓零和博弈，指的是在任何博弈情况下两个参与人的支付之和为 $0$ ,即对于 $\forall i \in \{1,2,\cdots,m\}$ 和 $\forall j \in \{1,2,\cdots,n\}$ ,有 $a_{ij}+b_{ij}=0$ ,我们设 $\boldsymbol {U_1=U}$ ,那么 $\boldsymbol {U_2=-U}$ ,所以给定了支付矩阵 $\boldsymbol U$,就给出来了所有参与人的支付。 ## 极大极小化行为和鞍点(saddle point) 所谓极大极小化行为，指的是某一参与人在使自己的支付最小化的战略中，选择使得自己支付最大化的行为。如下表所示:$

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \min\
\ \ \ \ \ \ \ \ \ \ \ \ U = \begin{bmatrix}
1 & 4 & 2 \
4 & 3 & 2 \
1 & 0 & 1
\end{bmatrix}
\begin{array}{c}
1 \
(2) \
1
\end{array}
\
\max \ \ \ \ \ \ \ \ \ \ 4\quad 4\quad \left(2\right)

$上述是参与人 $1$ 的支付矩阵。对于参与人 $1$ ,当他分别选择战略 $a_1,a_2,a_3$的时候，参与人 $2$ 知道自己和参与人 $1$ 的支付之和为 $0$ ,所以参与人 $2$ **为了使自己的支付最大化，必然要使得参与人 $1$ 的支付最小化**，即参与人 $2$ 会在对应的行中，选择参与人 $1$ 获得支付最小的，即参与人 $2$ 会分别选择战略 $b_1,b_3,b_2$ ,这样可以使得参与人 $1$ 支付最小，自己的支付达到最大。此时参与人 $1$ 和参与人 $2$ 的支付分别为 $v_1=1,2,0,v_2=-1,-2,0$. 但是参与人 $1$ 也知道这一点，他知道上面的支付是自己最小的支付，所以他要**“瘸子里挑将军”，在所有不利于自己的战略中，挑选一个最有利的**。所以参与人 $1$ 一定会选择战略 $a_2$ ,这个时候，按照上述分析，参与人 $2$ 选择战略 $b_3$ 以使对方支付最小，自己支付最大。这样的话，参与人 $1$ 和参与人 $2$ 的支付分别为 $v_1=2,v_2=-2$ . 回顾上述思路，参与人 $1$ 先是站在参与人 $2$ 的角度考虑，挑选了一个对于参与人 $1$ 来说支付最小的，然后又从中挑选了一个支付最大的。因此这种行为被称为参与人$1$的“**极大极小化行为**” 对于参与人 $2$ 来说，也可以照此分析，由于上述矩阵是参与人 $1$ 的支付矩阵，因此参与人 $2$ 就表现出 “**极小极大化行为**”。 >**定义：鞍点** > >对于给定的零和博弈的支付矩阵 $U$ ,如果存在某个 $i^*$ 和 $j^*$ ,使得: >$

a{i^,j^}=\max_i \min_j a{ij}= \minj\max_i a{ij}

$$
那么称 $i^$ 行 $j^$ 列对应的点为鞍点(saddle point)

关于鞍点和Nash均衡，我们有如下定理:

定理：鞍点和Nash均衡

在Nash均衡中，如果支付矩阵 $\boldsymbol U$ 存在鞍点，那么鞍点对应的战略组合即为Nash均衡。

我们可以定义混合战略的鞍点

定义:混合战略意义下的鞍点

对于给定的零和博弈的支付矩阵 $\boldsymbol U$ ，如果存在参与人 $1$ 的某个混合战略 $\boldsymbol \sigma_1^=(\sigma_1^{1},\cdots,\sigma_1^{m})$和参与人 $2$ 的某个混合战略 $\boldsymbol \sigma_2^=(\sigma_2^{1},\cdots,\sigma_2^{n})$ ,使得:
$v_1(\boldsymbol \sigma_1^*,\boldsymbol \sigma_2^*)=\max_{\sigma_1} \min_{\sigma_2} v_1(\boldsymbol \sigma_1,\boldsymbol \sigma_2)=\min_{\sigma_2} \max_{\sigma_1}v_1(\boldsymbol \sigma_1,\boldsymbol \sigma_2)$
那么称战略组合$(\boldsymbol \sigma_1^,\boldsymbol \sigma_2^)$ 为支付矩阵 $\boldsymbol U$ 的鞍点。

von Neumann极大极小定理

von Neumann极大极小定理

在零和博弈中，对于给定的支付矩阵 $\boldsymbol U$ ，如果存在混合战略 $\boldsymbol \sigma_1^=(\sigma_1^{1},\cdots,\sigma_1^{m})$ 和 $\boldsymbol \sigma_2^=(\sigma_2^{1},\cdots,\sigma_2^{n})$以及一个常数 $v$ ,使得
$\forall j,\qquad \sum\limits _{i=1}^m a_{ij}\boldsymbol \sigma_1^{i*}\geq v\\ \forall i,\qquad \sum\limits _{j=1}^n a_{ij}\boldsymbol \sigma_2^{j*}\leq v$
那么称战略组合 $(\boldsymbol \sigma_1^,\boldsymbol \sigma_2^)$ 为博弈的Nash均衡，其中 $v$ 为参与人 $1$ 在均衡中所得到的期望支付，亦称该博弈的值。

零和博弈问题转化为对偶的规划问题

对于给定的零和博弈问题，如果博弈的值 $v>0$ ，那么博弈的 Nash均衡为下列对偶问题的解:

$\begin{aligned} &\min \sum_{i=1}^{m} p_{i} \\ &\text{s.t.} \quad \sum_{i=1}^{m} a_{ij} p_{i} \geq 1 \quad (j = 1, \cdots, n), \\ &\quad \quad \ p_{i} \geq 0 \quad (i = 1, \cdots, m), \\ &\quad \text{和}\\ &\max \sum_{j=1}^{n} q_{j} \\ &\text{s.t.} \quad \sum_{j=1}^{n} a_{ij} q_{j} \leq 1 \quad (i = 1, \cdots, m), \\ &\quad \quad \ q_{j} \geq 0 \quad (j = 1, \cdots, n). \end{aligned}$

其中，Nash均衡支付为 $v=\frac{1}{\sum\limits{i=1}^m p_i}=\frac{1}{\sum\limits{j=1}^n q_j}$ ,Nash均衡战略 $\sigma_1^=(vp_1,\cdots,vp_i,\cdots,vp_m),\sigma_2^=(vq_1,\cdots,vq_j,\cdots,vq_n)$.

如果支付矩阵 $\boldsymbol U=(a{ij}){m\times n}$中每个元素都大于零，即 $a_{ij}>0$ ,则博弈的值 $v>0$ ;

由此，如果发现给定的支付矩阵 $\boldsymbol U$ 中存在小于 $0$ 的元素，那么可以把每个元素都加上一个常数，从而使得每个元素都大于 $0$ ,这样的话，可以保证博弈的值 $v>0$ ,就可以应用上面的方法求解博弈问题了。

例题

给定博弈如下，求解Nash均衡

	$L$	$M$	$N$
$U$	$2,-2$	$-2,2$	$1,-1$
$C$	$-1,1$	$1,-1$	$0,0$
$D$	$3,-3$	$0,0$	$2,2$

解:

支付矩阵为:

$\boldsymbol U=\begin{bmatrix} 2 &-2&1\\ -1 &1&0\\ 3 &0&2 \end{bmatrix}$

我们可以加上一个常数 $2$ ,得到下面的支付矩阵:

$\boldsymbol U'=\begin{bmatrix} 4 &0&3\\ 1 &3&2\\ 5 &2&4 \end{bmatrix}$

设参与人 $1$ 和参与人 $2$ 的混合战略分别是 $\sigma_1=(v’p_1,v’p_2,v’p_3),\sigma_2=(v’q_1,v’q_2,v’q_3)$, $v$ 为原博弈的值， $v’$ 为新博弈的值，且 $v’=v+2$ ,利用对偶线性规划方法求解新战略式博弈的Nash均衡，构造规划问题如下:

$\begin{aligned} &\min \{p_1 + p_2 + p_3\} \\ &\text{s.t.} \quad 4p_1 + p_2 + 5p_3 \geq 1, \\ &\quad \quad \ 3p_2 + 2p_3 \geq 1, \\ &\quad \quad \ 3p_1 + 2p_2 + 4p_3 \geq 1, \\ &\quad \quad \ p_1 \geq 0, \ p_2 \geq 0, \ p_3 \geq 0, \\[10pt] &\max \{q_1 + q_2 + q_3\} \\ &\text{s.t.} \quad 4q_1 + 3q_3 \leq 1, \\ &\quad \quad \ q_1 + 3q_2 + 2q_3 \leq 1, \\ &\quad \quad \ 5q_1 + 2q_2 + 4q_3 \leq 1, \\ &\quad \quad \ q_1 \geq 0, \ q_2 \geq 0, \ q_3 \geq 0. \end{aligned}$

上述对偶问题的解是

$(p_1,p_2,p_3)=(0,\frac{3}{13},\frac{2}{13})\\ (q_1,q_2,q_3)=(\frac{1}{13},\frac{4}{13},0)\\ v'=\frac{13}{5}\\$

因此，所求的混合战略Nash均衡为:

$\boldsymbol { (\sigma_1^*,\sigma_2^*) } =\left( \left(0,\frac{3}{5},\frac{2}{5}\right), \left(\frac{1}{5},\frac{4}{5},0\right) \right)\\ v_1=v'-2=\frac{3}{5}\\ v_2=-v_1=-\frac{3}{5}$