双人矩阵博弈中的纳什均衡

双人矩阵博弈中的纳什均衡

引用

CSDN

1.

https://blog.csdn.net/weixin_45673389/article/details/129625227

本文将介绍双人矩阵博弈中的纳什均衡概念及其在线性规划中的应用。文章从双人矩阵博弈的基本定义出发，详细阐述了零和博弈和一般和博弈的区别，并通过线性规划方法求解纳什均衡。文章还通过猜硬币游戏的例子，具体展示了如何使用线性规划方法求解纳什均衡，并提供了相应的Python代码实现。

双人矩阵博弈

1. 对于双人矩阵博弈，可建立一个由包含各个联合行为对回报的元素所构成的矩阵。由此，玩家i(i=1,2)的回报函数Ri可表示为一个矩阵。

2. 如果两个玩家完全竞争，则该双人矩阵博弈称为零和博弈。在这种情况下，R1 =-R2。在期望回报上，零和博弈只有唯一的纳什均衡。这意味着，尽管在零和博弈中每个玩家可能具有多种纳什均衡策略，但在这些纳什均衡策略下，期望回报值V均相同。

3. 一般和矩阵博弈是指各种类型的矩阵博弈。在一般和矩阵博弈中，纳什均衡不再唯一，可能具有多个纳什均衡。

4. 在双人矩阵博弈中，定义玩家 i 行为集Ai(i =1,2)的所有概率分布集合为
   ，由此，Vi可为
   （因为Ri要靠执行对应的动作才能获得，因此两边乘上对应策略的概率，便是当前情况下的Vi）

5. 双人矩阵博弈的纳什均衡是指对于两个玩家的策略对
   ,具有
   ，式中，-i是指玩家i以外的其他玩家；PD(Ai)为玩家i的行为集Ai的所有概率分布集合。这个公式的含义是，固定除i以外的其他玩家的策略，玩家i采取最优策略的V值，比采取其他策略的V值要大。

6. 假定每个玩家在游戏中只有两种行为，则双人-双行为的一般和矩阵博弈可以定义如下：
   ，式中，
   ，其中
   ，式中，-l和-f分别表示除行l之外的其他行和除列f之外的其他列。

双人零和矩阵博弈中的线性规划

线性规划

1. 求解双人零和矩阵博弈中的纳什均衡等价于寻找下列方程的最小解
   ，
   是指玩家 i 的行为
   的概率分布，
   表示除玩家i以外的其他玩家的所有行为，根据上式，每个玩家都试图在与对手对抗的最坏情况下得到最大化回报。为求解上式，可采用线性规划方法。

2. 假设给定一个2x2的零和矩阵博弈如下：
   
   式中，R1为玩家1的回报矩阵，R2为玩家2的回报矩阵。

3. 定义pj(j=1,2)为玩家1第j个行为的概率分布，而qj为玩家2第j个行为的概率分布。

4. 由此，玩家1的线性规划问题可表示为寻找(p1,p2)以使得V1最大化，且满足：
   玩家2的线性规划问题可表示为寻找(p1,p2)以使得V2最大化，且满足：
   为解决上述线性规划问题，可采用单纯形法来寻找几何最优点。

线性规划举例 -- 猜硬币

• 猜硬币游戏中，玩家1的回报矩阵如下：
• 由于 p2=1-p1，则玩家1的线性规划问题为：寻找p1使得V1最大化，且满足
• 根据上述线性约束画图，如下：
  
• 其中横轴为V1，纵轴为p1；图中灰色区域为V1区域（V1<=那两条线上的V1值）；当p1=0.5时，V1最大，为0；则寻找到p1=0.5使得V1最大，那p2=1-0.5=0.5，那玩家1的纳什均衡为：（0.5，0.5）
• 对玩家2做同样操作，也能得到，玩家2的纳什均衡也为（0.5，0.5）

猜硬币纳什均衡代码

import numpy as np

def Nash_LP_Point(R):
    x = np.arange(0, 1.1, 0.1)
    line1 = {}
    line2 = {}
    point = []
    for i in x:
        i = round(i, 2)
        j = round(R[0][0] * i + R[1][0] * (1 - i), 2)
        line1[i] = j
    for i in x:
        i = round(i, 2)
        j = round(R[0][1] * i + R[1][1] * (1 - i), 2)
        line2[i] = j
    # print(line1)
    # print(line2)
    # print(f'line1两个端点：0:{line1[0]},1:{line1[1]}')
    # print(f'line2两个端点：0:{line2[0]},1:{line2[1]}')
    for i1 in x:
        for i2 in x:
            i1 = round(i1, 2)
            i2 = round(i2, 2)
            if i1 == i2:
                if line1[i1] == line2[i2]:
                    # print(f'交点：{i1, line1[i1]}')
                    point.append((i1, line1[i1]))
                    break
    e_point = {'10': line1[0], '11': line1[1], '20': line2[0], '21': line2[1]}
    e_point_sort = sorted(e_point.items(), key=lambda x: x[1], reverse=False)
    # print(e_point_sort)
    if e_point_sort[0][1] >= e_point_sort[1][1]:
        a = int(e_point_sort[0][0]) % 10
        b = e_point_sort[0][1]
        point.append((a, b))
    else:
        a = int(e_point_sort[1][0]) % 10
        b = e_point_sort[1][1]
        point.append((a, b))
    #print(point)
    point = sorted(point, key=lambda x: x[1], reverse=True)
    print(point[0])

R1=[[1,-1],[-1,1]]
Nash_LP_Point(R1)
R2=[[-1,1],[1,-1]]
Nash_LP_Point(R2)
R3=[[1,2],[-1,1]]
Nash_LP_Point(R3)