双人博弈纳什均衡求解

Table of Contents:

纳什均衡
纯策略均衡算法
混合策略均衡算法
实验结果
实验心得

纳什均衡#

纳什均衡是一个策略组合，其中每个博弈者的均衡策略都旨在让自己期望收益达到最大，因而没有人愿意独自背离该均衡。为了方便算法设计，我们可以如下进一步理解这一定义：

对于纯策略纳什均衡，我们理解为“没有博弈者有意愿去改变自己的策略”。
对于混合策略纳什均衡，我们理解为“个人混合策略的选择使得他人的任意选择期望收益一致”。

纳什证明了n人有限博弈中，纳什均衡的普遍存在性。纯策略可以被理解为选定策略概率为1的混合策略特例，因此存在性定理也可以说是必定有混合策略存在。

纯策略均衡算法#

本次实验中只考虑双人博弈情况，朴素的算法可以遍历两人的 $n^2$ 对选择，然后考虑行列方向上两人有没有更优的选择，是否能为更高收益背离当前策略。这样的算法复杂度是 $O(n^3)$ 的。

假设行博弈者为a，列博弈者为b。考虑借助经济学上常用的“划线法”来优化至 $O(n^2)$ ：

固定行，找每列中b收益最大的格子，标记+1

固定列，找每行a收益最大的格子，标记+1
所有格子中被标记达到2的格子即为纯策略

max_a = np.amax(pay_a, axis=0)  # for each column (choice of b), select the max a
max_b = np.amax(pay_b, axis=1)	# for each row (choice of a), select the max b
choice_a = np.zeros((n, n))
choice_b = np.zeros((n, n))
for i in range(n):  # Suppose that a selected the row i
    choice_b[i][np.where(pay_b[i, :] == max_b[i])] += 1   # best grids for b
for i in range(n):  # Suppose that b selected the col i
    choice_a[i][np.where(pay_a[:, i] == max_a[i])] += 1   # best grids for a
choice_a = choice_a.T
choice = choice_a + choice_b
print(np.where(choice == 2))    # count the number of favored grids

这个算法的正确性很好理解，每次标记都说明行（列）博弈者在这个格子中时，列（行）固定，没有意愿更改行（列）选择。如果一个格子被两次标记，就说明行列博弈者都没有意愿改变，即为纯策略结果。且算法选取最大值的所有索引，因此不会遗漏可行的纯策略。

找最大值索引并标记的过程是 $O(n^2)$ 的，因此划线算法相较朴素的验证更优。因为划线法遍历一遍就直接找到了最优的格子，而不用考虑去检验一些一定不是均衡的格子。

混合策略均衡算法#

优化：去除严格非优策略#

延续纯策略的理念，混合策略均衡也可以利用最大值索引来完成“去除严格非优策略”的优化。我们已经求解纯策略得到了choice_a，choice_b两个矩阵，他们用01矩阵分别记录了“固定列，a收益最大的行”，“固定行，b收益最大的列”。也就是说，在choice_a中如果有一行全为0，说明b取任意列，这一行都不会被a选择，即它被其他行严格支配，我们可以删除这一行。choice_b的全0列也同理。

所以优化部分的算法设计如下：

找到choice_a中的全0行和choice_b中的全0列
在两个矩阵中删除这些行列
重复1、2，直到没有被严格支配的行或列

def delete(choice_a, choice_b):
    while True:
        del_a = (choice_a == 0).all(1)  # del choice_a all 0 row
        del_b = (choice_b == 0).all(0)  # del choice_b all 0 col
        temp_a = choice_a.copy()
        temp_b = choice_b.copy()
        choice_a[:, del_b] = 0
        choice_b[del_a, :] = 0
        if (temp_a == choice_a).all() and (temp_b == choice_b).all():
            print('del_a', del_a)
            print('del_b', del_b)
            return del_a, del_b

求解：线性方程组分情况讨论#

这样得到了要删除的行列，直接在payoff矩阵中删除他们，得到了新的payoff矩阵，然后再进行矩阵求解。求解即分别对行列博弈者列出“使得另一人的任意选择期望收益一致”的线性方程组。通过矩阵秩判断无解、无穷解和唯一解的情况。

def solve_equation(m, n):	# m为系数矩阵，n为系数矩阵的行数
    y = np.zeros(n)
    y[-1] = 1
    r = np.column_stack((m, y.T))
    rank_r = matrix_rank(r)
    rank_m = matrix_rank(m)
    if rank_r > rank_m:
        print('No solution.')
    elif rank_r < m.shape[1]:
        print('Infinite solutions.')
    else:
        x = solve(m, y)
        print('Probability is: ', x)

实验结果#

Game1：多个纯策略均衡，混合策略取概率分布#

博弈矩阵如下，红色的格子表示算法找到的纯策略均衡：

15,11	0,0	0,-5	0,0	0,0	0,-4	0,0	0,-3	0,0	-4,0
0,0	0,0	0,-1	0,0	15,12	0,0	0,0	0,0	0,0	0,0
0,-1	0,0	15,14	0,0	0,0	0,0	-3,0	0,0	0,0	0,0
-4,-4	0,0	0,-3	15,10	-1,0	0,0	0,-1	-2,-2	0,0	0,0
-1,0	15,15	0,0	0,0	0,0	0,-1	0,0	0,0	0,-4	0,-5
0,-5	0,-4	0,0	0,-3	0,0	15,14	0,0	0,0	0,0	0,0
0,0	0,0	0,-1	0,0	0,-4	0,0	0,0	-5,-2	14,14	0,0
0,0	-3,0	0,0	0,-1	0,0	0,0	15,13	0,0	0,0	-2,0
-4,-5	0,0	-3,-4	0,-3	-1,-2	0,0	0,-1	11,13	0,0	0,0
-3,-4	0,0	-2,0	0,0	-1,0	0,0	0,0	0,-3	0,0	14,13

比较显然，纯策略的结果是合理的，每个格子都是自己行列里的绝对最大，到其中任意一个格子里都没有人有意愿移动。

去严格非优的优化显示没有要删除的行或列，这也可以解释，从纯策略结果可以看到纯策略分布占据了所有行列，因此没有被严格支配的行或列。

二者混合战略均衡的概率分配如下：

Player a: 
Probability is:  [0.21515994 0.07186778 0.17512398 0.11367798 0.05471334 0.0964474
 0.04669742 0.05145731 0.1203566  0.05449824]
Player b: 
Probability is:  [0.096489   0.07363228 0.08651383 0.11826693 0.06719968 0.06719968
 0.09657079 0.15642657 0.12786629 0.10983496]

Game2：单个纯策略均衡，混合策略与纯策略一致#

13,-4	8,10	13,-5	1,9	10,11	0,-4	11,10	5,-3	2,6	-4,8
15,14	15,7	15,4	15,9	15,15	15,-1	15,2	11,14	14,-4	14,-5
2,-1	1,4	12,6	2,5	12,14	8,10	-3,13	5,11	0,2	8,2
-4,-4	10,4	14,-3	12,-3	-1,10	13,6	14,-1	-2,-2	9,0	1,6
8,8	9,2	3,-1	14,11	0,12	3,9	4,0	0,0	10,6	5,8
2,-5	12,-4	5,5	2,-3	3,14	7,13	0,7	10,2	11,3	11,10
14,10	-3,0	10,9	7,-1	8,13	13,6	12,7	10,0	12,9	-2,8
-4,-5	9,12	-3,-4	6,-3	-1,13	14,9	10,-1	9,8	11,9	5,3
9,8	5,11	11,-1	2,5	14,14	1,13	13,10	-5,-2	4,8	2,4
-3,-4	14,12	-2,4	0,10	-1,13	14,7	1,6	0,-3	13,1	8,1

这个博弈中纯策略只有第二行第五列的(15,15)，容易检验它是符合纳什均衡定义的。

调出choice_a，choice_b可以发现前者只有第2行为1，后者只有第5列为1。这一现象说明第2行的a收益严格支配其他行，第5列的b收益严格支配其他列，检查确实如此。

也因此混合策略优化后，只剩下这一格，自然两者选它的概率都为1，混合策略与纯策略一致。

Game3：无纯策略均衡，有无穷混合策略解#

0,0	-1,1	1,-1	-1,1	1,-1	0,0	1,-1	0,0	-1,1	0,0
-1,1	0,0	-1,-1	1,-1	-1,1	1,-1	0,0	1,-1	0,0	-1,1
1,-1	1,-1	0,0	0,0	0,0	-1,1	-1,1	-1,1	1,-1	1,-1
0,0	-1,1	1,-1	-1,1	1,-1	0,0	1,-1	0,0	-1,1	0,0
-1,1	0,0	-1,1	1,-1	-1,1	1,-1	0,0	1,-1	0,0	-1,1
1,-1	1,-1	0,0	0,0	0,0	-1,1	-1,1	-1,1	1,-1	1,-1
0,0	-1,1	1,-1	-1,1	1,-1	0,0	1,-1	0,0	-1,1	0,0
-1,1	0,0	-1,1	1,-1	-1,1	1,-1	0,0	1,-1	0,0	-1,1
1,-1	1,-1	0,0	0,0	0,0	-1,1	-1,1	-1,1	1,-1	1,-1
0,0	-1,1	1,-1	-1,1	1,-1	0,0	1,-1	0,0	-1,1	0,0

这个博弈中不存在纯策略均衡，其实也可以直接从表格中看出。a每行和b每列最大值都是1，因此标记的数量其实就是格子中1的数量。然而不存在(1,1)的格子，因此不存在二者都喜欢的格子，即不存在纯策略均衡。

同时也不存在被严格支配的行或列，因此没得优化。然后进入解线性方程组的阶段：

a的系数矩阵和增广矩阵秩同为4，小于未知数个数10，因此有无穷解。
B的系数矩阵和增广矩阵秩同为3，小于未知数个数10，因此有无穷解。

Game4：无纯策略均衡，混合策略取概率分布#

0,0	-1,1	0,0	0,0	0,0	0,0	0,0	1,-1	1,-1
1,-1	0,0	-1,1	0,0	0,0	0,0	0,0	0,0	0,0
0,0	1,-1	0,0	-1,1	0,0	0,0	0,0	0,0	0,0
0,0	0,0	1,-1	0,0	-1,1	0,0	0,0	0,0	0,0
0,0	0,0	0,0	1,-1	0,0	-1,1	0,0	0,0	0,0
0,0	0,0	0,0	0,0	1,-1	0,0	-1,1	0,0	0,0
0,0	0,0	0,0	0,0	0,0	1,-1	0,0	-1,1	0,0
0,0	0,0	0,0	0,0	0,0	0,0	1,-1	0,0	-1,1
-1,1	0,0	0,0	0,0	0,0	0,0	0,0	1,-1	0,0

和Game3的相同点在于1的个数就是格子的标记数，且不存在(1,1)的格子，因此不存在纯策略均衡，也不存在被严格支配的行和列。

与Game3的区别在于被设计过的payoff矩阵使得a和b的系数矩阵满秩，因此方程有唯一解，各行列的概率分布如下：

Player a: 
Probability is:  [0.125      0.06944444 0.13888889 0.08333333 0.15277778 0.09722222
 0.16666667 0.11111111 0.05555556]
Player b: 
Probability is:  [0.11111111 0.16666667 0.09722222 0.15277778 0.08333333 0.13888889
 0.06944444 0.125      0.05555556]

实验心得#

能直接找到解的算法比遍历再检验的更优。不过能想到这个算法，是因为经济学上的划线法解纯策略给我留下的印象太深（太好用了），于是直接动手实现了这个，并没有绕太多弯路。
很高兴代码跑出来的结果能够和实际直观对的上，切实感受到了用代码跑结果，根据结果再反推收益矩阵特性的便利。不过遗憾的是没能找到比较直观解释混合策略的概率分布结果的方式，只能说检验一下确实另一方是无差异选择，但很难一看表格就知道概率分布的大致样子。
一开始没看到数据写的文件读取还是不够鲁棒，都没考虑到后面几个数据会有空格哈哈。