题目简述
证明：当雪堆博弈满足$r<\frac{1}{k_{max}}$时，网络博弈的纳什均衡中的采样合作策略的节点构成极小节点覆盖。（作业：自己编写程序验证这个结论，网络可自定，节点数目不少于20）
问题背景简述
雪堆博弈
在一个风雪交加的夜晚，两人相向而来，被一个雪堆所阻，假设铲除这个雪堆使道路通畅需要的代价为c，如果道路通畅则带给每个人的好处量化为b。如果两人一齐动手铲雪，则他们的收益为R=b-c/2；如果只有一人铲雪，虽然两个人都可以回家，但是背叛者逃避了劳动，它的收益为T=b，而合作者的收益为S=b-c；如果两人都选择不合作，两人都被雪堆挡住而无法回家，他们的收益都为P=0。这里假设收益参数满足下面的条件：T>R>S>P。
纳什均衡
在博弈论中，如果任意一位参与者在其他所有参与者的策略确定的情况下，其选择的策略是最优的，那么这个组合就被定义为纳什均衡。即若$\displaystyle p_{i} (s)=max_{r_{i}}[p_i(s;r_i)]$，则称s为纳什均衡点，其中：$p_i$为参与者i的收获（payoff），$s_{i}$代表所有参与者之策略，$r_{i}$代表参与者i的一种可能策略，$(s;r_i)$指参与者i单方面改变策略为$r_i$。
环境
python=3.7.4
Windows10
实验过程
- 给每个节点的初始状态随机设置为
C或者D - 依次计算每个节点采用
C行为和D行为的收益，通过改变策略使收益最大 - 重复步骤2直到每个节点的状态信息不再发生变化
采取不同策略时，收益表如下：
迭代流程图
实验结果
本次实验选取的网络结构如下：
$k_{max}=7$，设置$r=0.08$
运行之后，结果如下：
其中第一列表示节点序号，第二列表示节点当前的策略，第三列表示执行当前策略的收益值，最后一行表示总的收益。其对应的结果图像如下：
其中红色表示策略C，蓝色表示策略D
多次实验后，我们发现每一次网络满足纳什均衡的策略组合都能满足最小节点覆盖。雪堆博弈模型在实现的方面较很多网络算法更为简单，且一定能够搜索到极小节点覆盖，具有很强的实用性。同时，作为博弈论模型，反映出个体在博弈中寻求最大利益的属性，使得整个群体在数次迭代后趋向于一个对整体较为有利的情况，也就是每条边两端都有至少有一个C节点使得该边得以通行，使得整个群体得到最大的利益。
代码展示
import random
# 收益矩阵
r=0.08
interest={
'C':{'C':(1,1),'D':(1-r,1+r)},
'D':{'C':(1+r,1-r),'D':(0,0)}
}
# 结点数据结构
class Node(object):
def __init__(self):
if (random.random()<0.5):
self.state='C'
else:
self.state='D'
self.value=0
self.all_value=0
self.neighbour_number=0
self.nb=list()
pass
pass
class Network(object):
def __init__(self,n):
self.numbers=n
self.nodes=list()
self.edges=list()
self.generateNode()
# 生成n个结点
def generateNode(self):
for i in range(self.numbers):
tmp_node = Node()
self.nodes.append(tmp_node)
def addEgde(self,es):
for e in es:
self.edges.append(e)
# 保存结点的邻居
def saveNb(self):
for a, b in self.edges:
a.nb.append(self.nodes.index(b))
b.nb.append(self.nodes.index(a))
for i in range(self.numbers):
self.nodes[i].neighbour_number=len(self.nodes[i].nb)
# 计算每个结点的平均收益
def calValue(self):
for i in range(self.numbers):
self.nodes[i].all_value=0
for a, b in self.edges:
a.all_value+=interest[a.state][b.state][0]
b.all_value+=interest[a.state][b.state][1]
for i in range(self.numbers):
self.nodes[i].value=self.nodes[i].all_value/self.nodes[i].neighbour_number
# 最优邻居法更新状态
def updateState_1(self):
for i in range(self.numbers):
max_value=self.nodes[i].value
for j in range(self.nodes[i].neighbour_number):
if(self.nodes[self.nodes[i].nb[j]].value>max_value):
self.nodes[i].state=self.nodes[self.nodes[i].nb[j]].state
max_value=self.nodes[self.nodes[i].nb[j]].value
# 逐项扫描反转试探法更新状态
def updateState_2(self):
for i in range(self.numbers):
if(self.nodes[i].state=='C'):
reward1=self.getReward(i)
self.nodes[i].state='D'
reward2=self.getReward(i)
if(reward2<=reward1):
self.nodes[i].state = 'C'
elif(self.nodes[i].state=='D'):
reward1=self.getReward(i)
self.nodes[i].state='C'
reward2=self.getReward(i)
if(reward2<=reward1):
self.nodes[i].state = 'D'
# 计算单个结点的收益
def getReward(self,i):
all_value=0
for s in self.nodes[i].nb:
all_value+=interest[self.nodes[i].state][self.nodes[s].state][0]
value = all_value / self.nodes[i].neighbour_number
return value
# 获得总收益
def getAllReward(self):
self.reward = 0
for a, b in self.edges:
self.reward+=sum(interest[a.state][b.state])
return self.reward
def outputState(self):
print('----------------')
for i in range(self.numbers):
print('%d:%c %f ' % (i,self.nodes[i].state,self.nodes[i].value))
print(self.reward)
print('----------------')
def designNet():
net=Network(20)
edge_list=[(0,2),(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),
(4,5),(4,6),(1,6),(6,3),(7,5),(15,5),(15,0),
(10,0),(10,15),(10,18),(18,0),(11,2),(19,2),
(12,2),(3,13),(14,6),(6,9),(17,1),(8,17),(17,9),
(14,3),(14,13),(12,13),(19,12),(11,19),(18,11),
(7,15),(16,7),(16,8),(8,1),(16,5),(16,1),(9,14),
(4,3),(3,12),(17,6),(18,2)
]
net.addEgde(
({net.nodes[a], net.nodes[b]} for a, b in edge_list))
return net
if __name__ == '__main__':
mynet=designNet()
# print(mynet.edges)
mynet.saveNb()
max_reward=0
# i=0
# max_reward保持3次才输出
i1=0
while True:
reward=mynet.getAllReward()
# print(reward)
# mynet.outputState()
if(max_reward==reward):
i1+=1
if(i1==3):
mynet.calValue()
mynet.outputState()
break
elif(reward>max_reward):
i1=0
max_reward=reward
mynet.updateState_2()
