博弈中的纳什均衡求解

Posted on 2021-04-21 In 学术 Views:

纳什均衡简介

纳什均衡指在一个博弈过程中的策略组合, 满足这样的性质: 对任意一位参与者而言, 在其他所有参与者的策略确定的情况下, 该参与者选择的策略是最优的.

纳什均衡还可以被理解为: 在该策略组合上, 任何参与人单独改变策略都不会得到好处. 如果在一个策略组合上, 当所有其他人都不改变策略时, 没有人会主动改变自己的策略, 这个策略组合即为纳什均衡.

本文接下来会从数学角度对此问题进行分析, 对博弈与纳什均衡建立严格的数学模型, 进行一系列性质与定理的证明, 并给出可求解纳什均衡的程序.

理论分析

问题定义

矩阵博弈 (Matrix Game)

在纳什均衡中, 博弈被定义为矩阵博弈 (matrix game). 对于博弈双方, 分别有 $m$ 和 $n$ 种策略供选择. 存在 2 个收益矩阵 $A$ 和 $B$, 都为 $m\times n$ 维, 表示了两者的选择对双方造成的收益.

记 $R$ 为行选择者, 其收益矩阵为 $A[m][n]$; $C$ 为列选择者, 其收益矩阵为 $B[m][n]$. 在一场博弈中, 二人分别选择了 $i$ 和 $j$ 作为相应的策略, 这决定了他们最终的收益, 分别为 $A[i][j]$ 与 $B[i][j]$.

纯策略 (Pure Strategy)

对于一个矩阵博弈, 纯策略的过程分为 3 步:

行选择者 $R$ 选择某一行 $i$.
列选择者 $C$ 选择某一列 $j$.
行选择者得到收益 $A[i][j]$, 列选择者得到收益 $B[i][j]$.

混合策略 (Mixed Strategy)

对于一个矩阵博弈, 混合策略不再使用固定的策略, 而是采取某种概率分布. 行选择者的策略为 $p\in S^m$, 其中 $p=\{p_0,p_1,\cdots,p_{m-1}\}$, $p_i$ 表示选择策略 $i$ 的概率, 并满足 $\displaystyle \sum_{i=0}^{m-1}p_i=1$. 列选择者的策略为 $q\in S^n$, 其中 $q=\{q_0,q_1,\cdots,q_{n-1}\}$, $q_i$ 表示选择策略 $i$ 的概率, 并满足 $\displaystyle \sum_{i=0}^{n-1}q_i=1$.

$R$ 与 $C$ 的收益期望分别为: $p^TAq$ 与 $p^TBq$.

纳什均衡 (Nash's Equilibrium)

对于纯策略矩阵博弈和混合策略矩阵博弈, 都存在纳什均衡 (Nash's equilibrium) 的概念.

对于纯策略矩阵博弈而言, 对于某个策略组合, 如果其他人不改变策略, 任何一个人单独改变自己的策略都不会得到任何好处, 那么也不会改变策略. 那么称这个组合为纳什均衡.

对于混合策略矩阵博弈而言, 如果存在 $R$ 与 $C$ 的混合策略 $p^{0}$ 和 $q^{0}$, 满足如下条件:

$\forall p,p^TAq^{0}\leq p^{0T}Aq^{0},$

且

$\forall q,p^{0T}Aq\leq p^{0T}Aq^{0}.$

那么称这个策略的组合为纳什均衡.

纳什均衡存在性

对于任何一个矩阵博弈, 有可能存在纯策略的纳什均衡点, 一定存在混合策略的纳什均衡点.

下面给出几个例子说明纯策略纳什均衡点的存在情况.

情况1: 有且仅有一个纳什均衡点.

	抵赖	坦白
抵赖	$(-1,-1)$	$(-10,1)$
坦白	$(1,-10)$	$(-4,-4)$

上述例子是经典的"囚徒困境"问题. 显然该博弈有且仅有一个纳什均衡点: (坦白, 坦白).

情况2: 存在多个纳什均衡点.

	看球赛	去舞会
看球赛	$(1,2)$	$(0,0)$
去舞会	$(0,0)$	$(2,1)$

上述例子是经典的"情侣博弈"问题. 在选择约会活动时, 俩人各有自己的喜好, 但也更倾向于彼此陪伴. 显然该矩阵有两个纳什均衡点: (看球赛, 看球赛) 和 (去舞会, 去舞会).

情况3: 不存在纳什均衡点.

	石头	剪刀	布
石头	$(0,0)$	$(1,-1)$	$(-1,1)$
剪刀	$(-1,1)$	$(0,0)$	$(1,-1)$
布	$(1,-1)$	$(-1,1)$	$(0,0)$

上述例子是"剪刀石头布"游戏, 也是一个经典的"零和博弈"问题. 显然它不存在纳什均衡点.

下面考虑混合策略的纳什均衡点, 并证明: 对于任意的矩阵博弈, 都存在混合策略的纳什均衡点.

令 $c_i(p,q)=\max(0,e_i^TAq-p^TAq),d_i(p,q)=\max(0,p^TBe_j-p^TBq)$, 二者分别表示 $R$ 和 $C$ 从纯策略切换到混合策略的损失. 此处 $e_i$ 表示第 $i$ 位为 $1$, 其余位全为 $0$ 的向量.

定义映射 $f: (p,q)\rightarrow(p',q')$, 满足:

$p'_i=\frac{p_i+c_i(p,q)}{1+\sum_{j=0}^{n-1}c_j(p,q)},\quad q'_i=\frac{q_i+d_i(p,q)}{1+\sum_{j=0}^{m-1}d_j(p,q)}.$

那么 $f$ 实际上是 $S^m\times S^n\rightarrow S^m\times S^n$ 的映射. 注意, 此处 $S^m\times S^n$ 是一个凸集且是一个紧集. 因此可以使用引理不动点定理.

不动点定理 (Brouwer's Fixed-point Theorem)

现有一个集合 $B\subset R^d$, 它是一个凸集且是一个紧集. 对于一个连续的映射: $f:B\rightarrow B$, 一定存在 $x\in B$ 满足 $x=f(x)$.

证明略去.

那么根据不动点定理, 对于上述的映射 $f$, 一定存在一个不动点 $(p^{0},q^{0})$, 满足 $f(p^{0},q^{0})=(p^{0},q^{0})$. 下面证明这个不动点即是该矩阵博弈的纳什均衡点.

不动点与纳什均衡点

下面证明不动点 $(p^{0},q^{0})$ 就是纳什均衡点.

如果某个点是纳什均衡点, 那么所有的 $c_i$ 与 $d_i$ 都应当是0.

由 $f(p^{0},q^{0})=(p^{0},q^{0})$ 可以推出:

$p_i^{0}\sum_{j=1}^{n-1}c_j(p^{0},q^{0})=c_i(p^{0},q^{0}).$

如果有 $c_i(p^{0},q^{0})>0$, 那么 $p_i^{0}>0$ 且 $e_i^TAq^{0}>p^{0T}Aq^{0}$, 定义集合 $I=\{i\mid c_i(p^{0},q^{0})>0\}$.

那么有:

$p^{0T}Aq^{0}=\sum_{i\in I}p^{0}e_i^TAq^{0}>(\sum_{i\in I}p_i^{0})p^{0T}Aq^{0}=p^{0T}Aq^{0}.$

即推出矛盾. 因此有 $c_i(p^{0},q^{0})=0$, 亦即 $e_i^TAq^{0}\leq p^{0T}Aq^{0}$.

对于 $\forall p \in S^m$, 当 $q^{0}$ 不变, 就有:

$p^TAq^{0}=\sum_{i=0}^{n-1}p_ie_i^TAq^{0}\leq(\sum_{i=1}^{n-1}p_i)p^{0T}Aq^{0}=p^{0T}Aq^{0}.$

对于 $d_i(p,q)$ 与 $q^{0}\in S^n$, 证明过程类似. 这就说明了 $(p^{0},q^{0})$ 为纳什均衡点.

算法设计

本节将给出进行纳什均衡点寻找的算法, 对于纯策略与混合策略分别给出相应的方案, 进行正确性分析, 空间与时间复杂度分析, 并给出一些实验结果.

不失一般性地, 假设我们的问题中行选择者和列选择者的可用策略数量相同. 将 $R$ 与 $C$ 的收益矩阵分别用二维数组 $A[n][n]$ 与 $B[n][n]$ 来表示. 其中, $n$为行选择者和列选择者的策略空间维度.

纯策略纳什均衡

对于纯策略纳什均衡, 我们给出一个基础算法和一个优化后的算法.

基础算法

该算法的思路基于纳什均衡的定义. 对于所有的策略组合 $\{(i,j)\mid 0\leq i,j < n\}$, 逐一检查它是否为纳什均衡点, 即是否满足行选择者处于该列中的最优行, 且列选择者处于该行中的最优列.

主要代码如下 (使用 C 撰写):

bool nash_check(int i, int j)
{
	for (int t = 0; t < total_N; ++t)
	{
		if (A[t][j] > A[i][j])return false;
		if (B[i][t] > B[i][j])return false;
	}
	return true;
}
void solve()
{
    for (int i = 0; i < total_N; ++i)
            for (int j = 0; j < total_N; ++j)
            {
                if (nash_check(i, j))
                    printf("pure strategy: A choose %d and B choose %d\n", i, j);
            }
}

由于该算法对所有策略组合按照定义进行检查, 因此一定可以找出所有的纯策略纳什均衡点, 正确性即证.

该算法的时间复杂度为 $O(n^3)$. 其中, 遍历所有策略组合需要 $n^2$ 次循环, 对每个策略进行检查需要 $2n$ 次循环, 因此总的时间复杂度为 $2n^3=O(n^3)$.

该算法的空间复杂度为 $O(n^2)$. 唯一的空间开销为存储收益矩阵的 $A$ 与 $B$ 数组.

优化算法

在上一种算法中, 对所有的策略组合进行遍历显然是冗余的. 在遍历过程中很有可能遇到一些显然的非优策略.

考虑到对于任何一个矩阵而言, 只有每行中的最大值所在列, 与每列中的最大值所在行, 有可能作为该行与该列的纳什均衡点.

因此本优化算法的思路即为首先找出纳什均衡点的"备选点". 该算法首先标记收益矩阵中每行的最大值, 再标记收益矩阵中每列的最大值. 一旦存在一个位置被标记两次, 这个位置就一定是纳什均衡点.

主要代码如下 (使用 C 撰写):

void op_solve()
{
	for (int i = 0; i < total_N; ++i)
	{
		double tmp_max = B[i][0];
		for (int j = 1; j < total_N; ++j)
			if (B[i][j] > tmp_max)tmp_max = B[i][j];
		for (int j = 0; j < total_N; ++j)
			if (B[i][j] == tmp_max)++Mark[i][j];
	}
	for (int j = 0; j < total_N; ++j)
	{
		double tmp_max = A[0][j];
		for (int i = 1; i < total_N; ++i)
			if (A[i][j] > tmp_max)tmp_max = A[i][j];
		for (int i = 0; i < total_N; ++i)
			if (A[i][j] == tmp_max)++Mark[i][j];
	}
	for (int i = 0; i < total_N; ++i)
		for (int j = 0; j < total_N; ++j)
		{
			if (Mark[i][j] == 2)
				printf("pure strategy: A choose %d and B choose %d\n", i, j);
		}
}

由于对于组合策略 $(i,j)$ 是纳什均衡点, 当且仅当满足行选择者处于该列中的最优行, 且列选择者处于该行中的最优列. 而对于任意的组合策略所在点, 只要被该算法标记两次, 就一定满足上述条件. 因此一定可以找出所有的纯策略纳什均衡点, 正确性即证.

该算法的时间复杂度为 $O(n^2)$. 其中, 标记两个收益矩阵时, 找到每行与每列的最大值需要 $n^2$ 次循环, 找到后标记最大值点 (由于最大值点可能有多个) 需要 $n^2$ 次循环, 最后找出标记两次的点需要 $n^2$ 次循环. 因此总的时间复杂度为 $3n^2=O(n^2)$.

该算法的空间复杂度为 $O(n^2)$. 空间开销为存储收益矩阵的 $A$ 与 $B$ 数组, 与用于标记的 $Mark$ 数组.

混合策略纳什均衡

混合策略的纳什均衡可以使用"无差异原理"来求解. 在下文中我们首先会介绍最简单的无差异原理求解办法, 并指出该方法存在的问题, 并提出一种改进方法: 排除严格非优策略.

但实际上, 寻找纳什均衡的过程并不容易. 首先, 找出所有的混合支配策略是一个 NP 问题. 一个策略可能被 $k$ 种策略联合支配, 此处 $2\leq k \leq n-1$. 因此找到混合支配策略无法在多项式时间内解决 (除非 P=NP).

任意一个策略双人博弈纳什均衡的计算复杂度是 PPAD complete 的, 同样无法在多项式时间内解决 (除非 P=NP).

由于该部分的求解过程较为复杂, 因此使用 python 撰写相关代码.

无差异原理算法

考虑混合策略下的纳什均衡, 假设 $R$ 的混合策略为数组 $a[n]=\{p_0,p_1,...p_{n-1}\}$, 分别对应的是 $C$ 使用策略 $0,1,\cdots,n-1$ 的概率. 根据无差异原理的定义, 当 $R$ 使用该策略时, 应使得 $C$ 的任意策略有相同收益C, 即导致 $C$ "出什么都一样"的结果. 因此, 应当有如下线性方程组:

$\begin{equation} \begin{aligned} &p_0 B[0][0]+p_1 B[1][0]+\cdots+p_{n-1}B[n-1][0]=X\\ &p_0 B[0][1]+p_1 B[1][1]+\cdots+p_{n-1}B[n-1][1]=X\\ &\cdots\\ &p_0 B[0][n-1]+p_1 B[1][n-1]+\cdots+p_{n-1}B[n-1][n-1]=X\\\\ &p_0+p_1+\cdots+p_{n-1}=1. \end{aligned} \end{equation}$

该方程组由 $n+1$ 行构成. 前 $n$ 行表示 $C$ 的所有策略收益一致 (都是 $X$), 最后一行表示 $R$ 的策略概率和为 1 (归一化).

因此可以将该问题用一个线性方程组来表示:

$\begin{pmatrix}B[0][0]& B[1][0]&\cdots &B[n-1][0] &-1\\ B[0][1]& B[1][1]&\cdots & B[n-1][1]&-1\\ B[0][2]& B[1][2]&\cdots& B[n-1][2] &-1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ B[0][n-1]& B[1][n-1]&\cdots & B[n-1][n-1] &-1\\ 1&1&\cdots&1 &0 \end{pmatrix} \cdot \begin{pmatrix}p_0\\p_1\\p_2\\\vdots\\ p_{n-1}\\X\end{pmatrix} =\begin{pmatrix}0\\0\\0\\\vdots\\ 0\\1\end{pmatrix}.$

求解该线性方程组, 得到的解 $(p,X)=(p_0,p_1,\cdots,p_{n-1},X)$ 即为行选择者的混合策略, 以及在这样的策略下, 列选择者的预期收益.

类似地, 用收益矩阵 $A$ 各项作为系数, $Y$ 表示行选择者的预期收益, $q=(q_0,q_1,q_2,\cdots,q_{n-1})$ 表示列选择者的混合策略, 列出类似的线性方程组, 也可以求解, 得到列选择者的混合策略.

上述求解过程可能有唯一解, 也可能有多个解, 任何一组解都对应着一组混合策略的纳什均衡点.

求解线性方程组的主要代码如下 (使用 python 撰写):

def solveB():
	(x,y) = A.shape
	C = np.zeros([x+1, y+1])
	for i in range(x):
		for j in range(y):
			C[i][j]=A[i][j]
		C[i][y] = -1
	for j in range(y):
		C[x] = 1
	C[x][y] = 0
	D = np.zeros([y+1])
	for j in range(y):
		D[j]=0
	D[y] = 1
	x=linalg.solve(C,D)
	print(x)

上述代码为求解列选择者的纳什均衡混合策略, 因此使用的是行选择者 $A$ 的收益矩阵. 行选择者的纳什均衡混合策略求解方法类似, 不再赘述.

理论上, 该算法的时间复杂度为 $O(n^3)$. 这是因为 $n$ 维线性方程组的求解复杂度为 $O(n^3)$, 在具体使用迭代方法时, 会根据迭代次数与误差设置有所不同.

该算法的空间复杂度为 $O(n^2)$. 唯一的空间开销为存储收益矩阵的 $A$ 与 $B$ 数组, 以及存储线性方程组的 $C$ 和 $D$ 数组.

但是, 上述算法得出的结果有可能存在某些概率为负值的情况. 这是不符合纳什均衡点的定义的. 出现这种情况的原因是有"支配策略"的存在. 前面已经提到, 找出支配策略是 NP 的, 无法通过找到所有支配策略对我们的算法进行改进. 考虑支配策略的一个特例: 上述结果也可能是由于"严格非优策略"的存在.

以行选择者为例. 策略 $i$ 对于行选择者是"严格非优的"的定义如下: 存在另一个策略 $i'$, 无论列选择者的策略如何, 行选择者选择 $i'$ 的收益总高于选择 $i$ 的收益. 可以对其形式化定义如下:

$\exists i',s.t.\forall j, A[i][j]<A[i'][j].$

这时显然行选择者无论如何都不应当选择策略 $i$. 但如果直接使用上述的方法求解, 会使得解向量的第 $i$ 位为负值, 不满足纳什均衡点的定义. 因此, 我们在刚才算法的基础上给出一个预处理的步骤: 对双方选手排除所有严格费油策略.

排除严格非优策略

该优化算法直接使用"严格非优策略"的定义, 对于双方的收益矩阵, 先让行选择者排除所有的严格非优策略, 再让列选择者排除所有的严格非优策略, 再让行选择者排除...以此类推, 直到双方都不再有严格非优策略为止.

注意: 该过程可能需要许多步, 因为每次迭代, 某方排除一些策略后, 对于另一方可能有新的"严格非优策略"产生, 因此需要一直迭代, 而不能只执行一步.

以行选择者为例, 排除某项策略 $i$ 的方法严格依照定义, 即 $\exists i',s.t.\forall j, A[i][j]<A[i'][j]$. 具体算法为: 使用 3.1.2 中的优化算法得到标记矩阵 $Mark_A$, 其中, $Mark_A[i][j] = 1$ 表示在第 $j$ 列中, 第 $i$ 行为最大值. 对于矩阵中的每一行, 查看是否它在任意列中都无法取得最大值. 如果是, 则证明第 $i$ 个策略是无效的, 因为不论列选择者选择什么策略, 行选择者都应有其他收益更高的策略.

预处理的主要代码如下 (使用 python) 撰写:

def exclude_column()
	flag = 0
	global A
	global B
	(x,y) = A.shape
    i = 0
	while i < x:
		if x == 1:
			break
		tmp_flag = 0
		for j in range(y):
			if Mark_A[i][j] == 1:
				tmp_flag = 1
				break
		if tmp_flag == 0:
			flag = 1
			A = np.delete(A, i, axis=0)
			B = np.delete(B, i, axis=0)
			i = i - 1
		(x,y) = A.shape
		i = i + 1
	return flag        

def presolve():
    flag = 0
    flag = flag + exclude_row() + exclude_column()
	return flag

res = 1
while res > 0:
	res = presolve()

上述代码为排除行选择者与列选择者的严格非优策略, 涉及到的函数只写出了行选择者的 exclude_row, 列选择者的函数与之类似, 不再赘述.

该算法的时间复杂度为 $O(n^3)$. 其中, 每次寻找博弈任一方的严格非优策略为 $O(n^2)$ 的. 寻找的过程运用到前面已有的 3.1.2 中优化算法的结果.

该算法的空间复杂度为 $O(n^2)$. 唯一的空间开销为存储收益矩阵的 $A$ 与 $B$ 数组, 与用于标记的 $Mark_A$ 和 $Mark_B$ 数组.