纳什均衡中的网络节点极小覆盖问题

发表于 | 分类于

纳什均衡中的网络节点极小覆盖问题

一、目标

当雪堆博弈满足r<1/kmax时，网络博弈的纳什均衡中的采用合作策略的节点构成极小节点覆盖。编程验证该结论，网络自定，节点数目不少于10。

二、原理分析

1、雪堆博弈

“雪堆”博弈模型是一种两人对称博弈模型。

在一个风雪交加的夜晚,两人相向而来,被一个雪堆所阻,假设铲除这个雪堆使道路通畅需要的代价为c,如果道路通畅则带给每个人的好处量化为b。如果两人一齐动手铲雪,则他们的收益为R=b-c/2;如果只有一人铲雪,虽然两个人都可以回家,但是背叛者逃避了劳动,它的收益为T=b,而合作者的收益为S=b-c;如果两人都选择不合作,两人都被雪堆挡住而无法回家,他们的收益都为P=0。这里假设收益参数满足下面的条件:T>R>S>P。

2、纳什均衡

纳什均衡是一种策略组合，使得同一时间内每个参与人的策略是对其他参与人策略的最优反应。

假设有n人参与博弈，如果某种情况下无一参与者可以独自行动而增加收益（即为了自身利益的最大化，没有任何单独的一方愿意改变其策略），则此策略组合被称为纳什均衡。所有局中人策略构成一个策略组合。
纳什均衡，从实质上说，是一种非合作博弈状态

3、网络节点极小覆盖问题

网络节点极小覆盖问题是一个著名组合优化问题，其目的在于找出给定网络的最小节点集合以覆盖所有的边。

极小节点覆盖：节点集合中去掉任何一个点，就不能覆盖网络所有边。

最小节点覆盖：极小节点覆盖中节点数目最少的。

三、解题思路

1、定义无向网络

定义一个如图所示的无向网络图，其中绿色代表合作，红色代表背叛。

纳什均衡1

该无向图的矩阵为：
0,1,1,0,0,0,0,0,0,0;
1,0,0,1,0,0,0,0,0,0;
1,0,0,1,0,0,0,0,0,0;
0,1,1,0,0,1,1,0,0,0;
0,0,0,1,0,0,1,0,0,0;
0,0,0,1,0,0,1,0,0,0;
0,0,0,0,1,1,0,1,1,0;
0,0,0,0,0,0,1,0,0,1;
0,0,0,0,0,0,1,0,0,1;
0,0,0,0,0,0,0,1,1,0;

图中k max为4，则取r<1/k max=0.25，r=0.2。

矩阵status为：0.2,0.2,0.2,0.2,0.8,0.8,0.2,0.2,0.8,0.2

2、分析纳什均衡

设当前节点为k[i]，与之相连的节点为k[j]。

如果k[i]为合作策略，则status[i]=0.2，读取k[j]。如status[j]=0.2，则k[i]、k[j]均采取合作策略，收益为1。如status[j]=0.8，则k[i]采取合作策略，k[j]采取背叛策略，收益为1-status[i]。最后计算得到共同收益IncomeA。

如果k[i]为背叛策略，则status[i]=0.8，读取k[j]。如status[j]=0.2，则k[i]采取背叛策略，k[j]采取合作策略，收益为1+status[i]。如status[j]=0.8，k[i]、k[j]均采取合作策略，收益为0。最后计算得到共同收益IncomeB。

将IncomeA和IncomeB进行比较。如果IncomeA>=IncomeB，则在当前节点k[i]采取合作策略。如果IncomeA<IncomeB，则在当前节点k[i]采取背叛策略。

3、改变初始状态

更改初始状态，并在不同的初始状态下分析纳什均衡，得到节点状态，直至得到最小节点覆盖。

四、数据处理

Status= 0.2000 0.8000 0.8000 0.2000 0.8000 0.8000 0.2000 0.8000 0.8000 0.2000

由Status可知，当达到纳什均衡时，第1、4、7、10号节点采取合作策略，第2、3、5、6、8、9号节点采取背叛策略。无论删掉2、3、5、6、8、9号节点中的哪个节点，都不能覆盖网络图中的所有边，即构成了极小节点覆盖。

纳什均衡2

由此可证，当雪堆博弈满足r<1/kmax时，网络博弈的纳什均衡中的采用合作策略的节点构成极小节点覆盖。

五、核心代码

1、初始值定义

1
2
3
4
5
6
7
8
9
10
11
12
network=[0,1,1,0,0,0,0,0,0,0;
1,0,0,1,0,0,0,0,0,0;
1,0,0,1,0,0,0,0,0,0;
0,1,1,0,0,1,1,0,0,0;
0,0,0,1,0,0,1,0,0,0;
0,0,0,1,0,0,1,0,0,0;
0,0,0,0,1,1,0,1,1,0;
0,0,0,0,0,0,1,0,0,1;
0,0,0,0,0,0,1,0,0,1;
0,0,0,0,0,0,0,1,1,0;];                  

status=[0.2,0.2,0.2,0.2,0.8,0.8,0.2,0.2,0.8,0.2];

2、主程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
for i=1:10             
	status(1,i)=0.2;            
    income=0;        
    IncomeA=0;             
    for j=1:10                
    	if net(i,j)==1                               
    		if status(1,j)==0.2                               
    			income=1;                     
      	    elseif status(1,j)==0.8   
      	        income=1-status(1,i);                     
      	    end                     
      	    IncomeA=IncomeA+income;                
      	end             
    end      
    status(1,i)=0.8;       
    income=0;         
    IncomeB=0;             
    for j=1:10                 
    	if net(i,j)==1                            
    		if status(1,j)==0.2                              
    			income=1+status(1,j);                      
    		elseif status(1,j)==0.8                         
    		    income=0;                     
    		end                      
    		IncomeB=IncomeB+income;                 
    	end             
    end              
if IncomeA>=IncomeB                      
	  status(1,i)=0.2;         
else             
	  status(1,i)=0.8;         
end     
end 
disp(status)