复杂网络上的博弈演化

《复杂网络上的博弈演化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、刘伟2009.11.21Qingdao复杂网络上的博弈演化1、博弈2、复杂网络上的演化博弈2.1、网络演化博弈的策略更新规则2.2、网络拓扑对合作的影响2.3、记忆对网络博弈中的影响2.4、博弈动力学与网络拓扑共演化2.5、学习机制导致合作的涌现3、展望一个个性和另一个个性的联结对被联结的个性的命运具有多大的意义？你要知道，这是一生的事情，在我们的背后隐藏着无数的枝节。——陀思妥耶夫斯基,《白痴》第501页一个游戏：两人轮流向圆桌上放一元硬币，谁无法再在圆桌上放硬币则判负，另一方获胜，假设所有的硬币不允许重叠。你会先放还是后放，以何种策略确保自己获胜?博弈研究的对

2、象是游戏(Game)，更确切的说，是指在具有双方相互竞争对立的环境条件下，参与者依靠所掌握的信息，在一定的规则约束下，各自选择策略并取得相应结果(或收益)的过程。博弈论就是使用数学模型研究冲突对抗条件下最优决策问题的理论。博弈论被认为是研究自然和人类社会中普遍存在的合作行为最为有力的手段。一、博弈论博弈模型反映了自私的个体之间的合作竞争关系，能够很好地刻画生物系统中生物体之间的相互作用关系及演化动力学。不论在自然或是社会系统中，经典博弈论告诉我们自私个体博弈的结果必然是背叛。显然是一个和实际情况不完全吻合结论。社会经济活动中的绝大多数任务不可能由单人完成，需要群体

3、的分工和合作。问题:为什么自私的个体组成的群体会产生合作行为，存在什么样的机制，以及什么样的条件才会有合作行为涌现？通常博弈由以下4个部分所组成:(l)博弈个体：在一个博弈中至少有两位决策者(agent)参与博弈.(2)策略集：个体的博弈策略可以是纯策略，也可以是混合策略博弈的策略集由参与博弈的个体所有可能采用的策略所组成.(3)收益矩阵：当博弈个体选定好自己的策略后，其所获取的收益由收益矩阵中的相应元素来确定.(4)策略演化:在多轮博弈过程中，博弈个体遵循自身收益最大化的最终目标，即以此目标为指导原则来进行策略调整。纳什均衡真实生活中的博弈问题是很复杂的，可能会

4、有很多的参与者，每个参与者都有不同的策略。当参与者们在进行一项博弈的时候，他们应该选择什么样的策略?是否有办法预言出他们的策略组合(s1，s2，…，sN)?纳什(Nash)均衡：其核心思想是对于两人或多人博弈，个体的策略演化会趋向于一个均衡态，在此均衡态下所有的个体会同时采取“纳什均衡策略”。Nash认为，博弈问题的解应该是这样的一组策略，在这组策略中，每一个参与者都无法通过单独改变自己的策略而获得更多的收益。这样的状态就被称作纳什均衡态.实际上纳什均衡态对所有的参与者来说，不一定是最好的结局。下面以囚徒困境博弈和雪堆博弈为例来阐述纳什均衡经典博弈模型囚徒困境博弈

5、:两个小偷A和B合伙作案，被捕后被隔离审讯.如果双方都拒绝坦白同伴的罪行，两人将会被轻判1年徒刑;为此，警方设计了一个机制:如果A揭发B的罪行，B拒不供认A的罪行，则A将无罪释放，而B将被重判5年徒刑;如果A、B都揭发对方罪行，则双方均被判刑3年.在此情况下，自私的个体应如何做出抉择?合作(Cooperate-C)or背叛(defect一D)不论对手采取哪种策略，选择背叛策略都是最佳的，即理性的个体最终会处于相互背叛的状态(注意到此时的集体收益低于两人同时选择合作时的情况).这种相互背叛的状态(D，D)就是系统的纳什均衡态。对于两人博弈，收益矩阵元通常用(R、S、

6、T、P)来表示相互合作则二人同获得较大收益R，相互背叛则同获较小收益P，一方合作一方背叛，则背叛者获得最高收益T，而合作者获得最低收益S，即参数满足关系:T>R>P>S，此外2R>T+S，即相互合作能获得集体最高收益.在一个风雪交加的夜晚，两人开车相向而行，被一个雪堆所阻，如图所示.白色和灰色分别表示合作策略与背叛策略.与囚徒困境博弈不同，对于雪堆博弈，收益矩阵元满足关系:T>R>S>P雪堆博弈:假设铲除这个雪堆使道路通畅需要付出的劳动量为c，道路通畅则带给每个人的好处量化为b(>c)。如果两人一齐动手铲雪，则他们的收益为R=b一c/2(分别承担劳动量c/2);如

7、果只有一人下车铲雪，虽然两人都能及时回家，但是背叛者逃避了劳动，它的收益为T=b，而合作者的收益为S=b一c;如果两人都选择不合作，则两人都无法及时回家，其收益量化为P=0.雪堆模型的收益矩阵可表示为那么，理性个体的最优选择是什么呢?如果对方选择背叛策略(呆在车中)，那么另一方的最佳策略是下车铲雪(因为按时回家的利益b一c好于呆在车中的背叛收益0);反之，如果对方下车铲雪，则自己的最佳策略是呆在舒服的车中.所以，不同于囚徒困境博弈，在雪堆博弈中存在两个纳什均衡态：(C，D)和(D，C).即雪堆博弈中的NE为两人均以概率r选择背叛，概率1-r选择合作，其r=c/(2

8、b-c)称