博弈论（一） ：极小节点覆盖

• 问题描述

可以验证：当雪堆博弈满足时，网络博弈的纳什均衡中的采用合作策略的节点构成极小节点覆盖。（自己编程序验证这个结论，网络自定，节点数目不少于 10）。

• 基本原理

• 实验结果

    1、网络结构

    2、邻接矩阵

上表是该网络的邻接矩阵，0 表示不相邻，1 表示两个节点相邻。我们用一个矩阵 S 表示每个节点的策略集合。S=[1,0,1,0,1,0,1,0,0,0]

 

    3、实验结果

    S = [1 0 1 0 1 0 1 0 0 1]是该网络的极小覆盖。

上图中红色表示选择合作策略，且所有红色节点构成极小节点覆盖。数字是每个节点的标号。

• 代码展示

import numpy as np
# 邻接矩阵
adj_matrix = np.array([[0, 1, 0, 0, 0, 0, 0, 1, 1, 0],
                       [1, 0, 1, 0, 0, 0, 0, 0, 0, 0],
                       [0, 1, 0, 1, 0, 0, 1, 0, 0, 0],
                       [0, 0, 1, 0, 1, 0, 0, 0, 0, 0],
                       [0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
                       [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
                       [0, 0, 1, 0, 0, 1, 0, 1, 0, 1],
                       [1, 0, 0, 0, 0, 0, 1, 0, 0, 0],
                       [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
                       [0, 0, 0, 0, 0, 0, 1, 0, 1, 0]])
b_C = np.zeros(10)  # 当选取合作策略时的收益矩阵
b_D = np.zeros(10)  # 当选取背叛策略时的收益矩阵
r = 0.1
s = np.array([1, 0, 0, 0, 1, 0, 1, 0, 1, 1])  # 初始化策略集合
adj_list = []
for i in range(10):     # 统计每个节点邻点的标号
    list = []
    for j in range(len(adj_matrix[i])):
        if adj_matrix[i][j] == 1:
            list.append(j)
    adj_list.append(list)

while (True):
    s_last = s.copy()  # 保存上一次迭代的结果
    for i in range(len(s)):
        num_C = 0;num_D = 0
        for j in range(len(adj_list[i])):
        # 统计第 i 个节点邻点中合作性的节点个数 num_C
        # 以及背叛性的节点个数 num_D
            if s[adj_list[i][j]] == 1:
                num_C += 1
            else:
                num_D += 1
            # 计算第 i 个节点取两种不同策略时的收益
        b_C[i] = num_C + num_D * (1 - r)
        b_D[i] = num_C * (1 + r)

        if b_C[i] > b_D[i]:
            s[i] = 1
        else:
            s[i] = 0

    if (s == s_last).all():  # 若本次迭代结果与上次一样则停止迭代输出结果
        print(s)
        break