网络博弈Network games

1、第一节. 博弈论介绍第二节. 网络上的两人两策略演化博弈第三节. 网络上的多人两策略演化博弈第四节. 网络上自适应的演化博弈 自从自从数学家数学家von Neumannvon Neumann和经济学家和经济学家MorgensternMorgenstern的合著的合著博弈论与经博弈论与经济行为济行为问世以来，人们把博弈方法用于分析经济竞争、军事冲突及物种问世以来，人们把博弈方法用于分析经济竞争、军事冲突及物种演化等问题。博弈论为解释自私个体之间的交互行为提供了理论框架。特演化等问题。博弈论为解释自私个体之间的交互行为提供了理论框架。特别的，博弈论还被用于理解个体合作行为和种群的进化，揭示底层自私

2、行别的，博弈论还被用于理解个体合作行为和种群的进化，揭示底层自私行为之间的竞争和现实生活中广泛存在的合作行为之间看似矛盾实则统一的为之间的竞争和现实生活中广泛存在的合作行为之间看似矛盾实则统一的内在动因内在动因。 博弈论博弈论模型中的个体（模型中的个体（IndividualIndividual）也称为参与者（）也称为参与者（PlayerPlayer）, ,它们可它们可以在多个策略（以在多个策略（StrategyStrategy）间进行选择。一个个体的行为会影响到其他个）间进行选择。一个个体的行为会影响到其他个体，每个个体也能够从与其他个体的互动中获得一定的体，每个个体也能够从与其他个体的互动中

3、获得一定的收益（收益（PayoffPayoff）. .博博弈论研究理性个体的策略选择，即在他人选择既定的情况下，如何使自己弈论研究理性个体的策略选择，即在他人选择既定的情况下，如何使自己的利益最大化。博弈论中最核心的概念是纳什均衡（的利益最大化。博弈论中最核心的概念是纳什均衡（Nash equilibriumNash equilibrium），），它是指自私个体在相互作用过程中达到的一种均衡状态，在这种状态下没它是指自私个体在相互作用过程中达到的一种均衡状态，在这种状态下没有个体可以通过单方面改变自己的策略而增加收益。有个体可以通过单方面改变自己的策略而增加收益。 合作合作无处不在，无论对于生

4、物界种群的进化还是人类社会的发展无处不在，无论对于生物界种群的进化还是人类社会的发展, ,合合作都扮演着至关重要的角色。纵观整个合作过程，种群中存在两类个体：作都扮演着至关重要的角色。纵观整个合作过程，种群中存在两类个体：合作者和背叛者。合作（合作者和背叛者。合作（Cooperation,CCooperation,C）是指付出一定的代价使对手）是指付出一定的代价使对手获益的行为；而背叛者（获益的行为；而背叛者（Defection,DDefection,D）是指不付出任何代价却可以从）是指不付出任何代价却可以从合作者处获益合作者处获益。在博弈论研究中，通常用一些生动有趣的博弈模型来描。在博弈论研

5、究中，通常用一些生动有趣的博弈模型来描述个体之间的冲突竞争，比如囚徒困境博弈（述个体之间的冲突竞争，比如囚徒困境博弈（Prisoners dilemma,PDPrisoners dilemma,PD）等。等。 在复杂环境中个体没有足够的能力去选择最佳策略以最大化收益，在复杂环境中个体没有足够的能力去选择最佳策略以最大化收益，此时个体通常会根据所掌握的局部信息采取启发式的方法，做出令其满此时个体通常会根据所掌握的局部信息采取启发式的方法，做出令其满意的决策。个体的这种选择过程表明它是有限理性的。演化博弈理论着意的决策。个体的这种选择过程表明它是有限理性的。演化博弈理论着重研究有限理性的个体如何随

6、着时间的推移在不断地重复博弈过程中通重研究有限理性的个体如何随着时间的推移在不断地重复博弈过程中通过自适应学习而优化收益。演化博弈理论（过自适应学习而优化收益。演化博弈理论（Evolutionary game theoryEvolutionary game theory）着重研究有限理性的个体如何随着时间的推移在不断的重复博弈过程中着重研究有限理性的个体如何随着时间的推移在不断的重复博弈过程中通过自适应学习而优化收益。演化博弈理论将经典博弈论中的收益对应通过自适应学习而优化收益。演化博弈理论将经典博弈论中的收益对应于进化论中的适应度（于进化论中的适应度（FitnessFitness）：适应度越

7、高的策略随着时间演化更）：适应度越高的策略随着时间演化更有可能被保留下来，适应度差的策略会被淘汰。最终策略在种群中会达有可能被保留下来，适应度差的策略会被淘汰。最终策略在种群中会达到一个均衡状态，任意少量的变异策略的个体无法入侵整个种群，而长到一个均衡状态，任意少量的变异策略的个体无法入侵整个种群，而长期来看整个种群没有发生变化。这种策略是纳什均衡的一个子集，称为期来看整个种群没有发生变化。这种策略是纳什均衡的一个子集，称为演化稳定策略。演化稳定策略。1.1.囚徒困境博弈囚徒困境博弈 考虑两考虑两个小偷（张三和李四）合伙作案，被捕后被隔离审讯。他们都知道：个小偷（张三和李四）合伙作案，被捕后被

8、隔离审讯。他们都知道： a. a.如果双方都坦白罪行，两人均被判刑如果双方都坦白罪行，两人均被判刑3 3年年 b. b.如果双方都拒绝坦白，两人均被判刑如果双方都拒绝坦白，两人均被判刑2 2年年 c. c.如果一方坦白，另一方拒不认罪，前者被判如果一方坦白，另一方拒不认罪，前者被判1 1年，后者被判年，后者被判5 5年年 如果C表示与同伴合作，即拒绝坦白；D表示背叛同伴，即坦白罪行，假设两个小偷不能相互交流,收益矩阵为：此博弈为两人两策略博弈，包括如下策略组合：a.双方都选择合作，记为（双方都选择合作，记为（C,C）。每个人收益记为）。每个人收益记为R，即，即“对双对双方合作的奖励方合作的奖励

9、”（Reward for mutual cooperation）b.一方合作而另一方背叛记为（一方合作而另一方背叛记为（C,D）或（）或（D,C）。背叛者会获得）。背叛者会获得“背叛的诱惑背叛的诱惑”T，合作者会得到，合作者会得到“傻瓜的报酬傻瓜的报酬”Sc.双方都选择背叛，记为（双方都选择背叛，记为（D,D）。每个人的收益记为）。每个人的收益记为P，即，即“对对双方都背叛的惩罚双方都背叛的惩罚”囚徒困境的收益矩阵中R=-2，S=-5，T=-1，P=-3。（D,D）是囚徒困境博弈的纳什均衡状态，但此时收益低于两人同时选择合作时的收益，在这种情况下理性个体将面临两难的困境。此为TRPS的情形。2

10、.重复囚徒困境重复囚徒困境 如果两个个体仅进行一轮囚徒困境博弈，个体通常会选择背叛策略。如果两个个体仅进行一轮囚徒困境博弈，个体通常会选择背叛策略。然而，在现实生活中，两个个体之间经常进行重复的交互，并且经常不然而，在现实生活中，两个个体之间经常进行重复的交互，并且经常不清楚这种博弈关系何时结束。此时，个体会乐于帮助那些曾经帮助过自清楚这种博弈关系何时结束。此时，个体会乐于帮助那些曾经帮助过自己的个体。己的个体。20世纪世纪70年代，年代，Axelrod发起了著名的发起了著名的“重复囚徒困境重复囚徒困境”计计算机游戏竞赛，研究什么样的规则是最好的。算机游戏竞赛，研究什么样的规则是最好的。 Ax

11、elrod设计了博弈收益矩阵中参数为：设计了博弈收益矩阵中参数为：R=3，P=1，S=0, T=5并邀请各个领域的专家提交他们认为最好的规则参赛，每个规则与其他并邀请各个领域的专家提交他们认为最好的规则参赛，每个规则与其他所有规则以及一个随机规则分别进行重复囚徒困境博弈，参加竞赛的规所有规则以及一个随机规则分别进行重复囚徒困境博弈，参加竞赛的规则可以利用博弈双方以往的历史信息，然后统计哪个规则最终收益最高。则可以利用博弈双方以往的历史信息，然后统计哪个规则最终收益最高。共进行了两轮竞赛，获胜者都是所有程序中最简单的规则共进行了两轮竞赛，获胜者都是所有程序中最简单的规则“针锋相针锋相对对”（Ti

12、t-for-tat,TFT） TFT以合作开始，然后模仿对手上一步的策略。以合作开始，然后模仿对手上一步的策略。TFT能成为冠军主能成为冠军主要得益于以下三点要得益于以下三点:nice(不会首先背叛对手）；不会首先背叛对手）；quickly “punish”(可被激怒的，报复适当可被激怒的，报复适当)；immediately“forgive”(如果如果对手知错能改，选择原谅对手知错能改，选择原谅)。但。但TFT不能纠正任何的失误，因而丧失合不能纠正任何的失误，因而丧失合作优势，为此作优势，为此Nowak提出了慷慨的提出了慷慨的TFT规则（规则（Generous-tit-for-tat,GTFT

13、）（面对背叛行为时仍以一定概率保持合作）和赢存输变）（面对背叛行为时仍以一定概率保持合作）和赢存输变（Win-stay,lost-shift,WSLS）(设定心理阈值，高于它保持，低于它设定心理阈值，高于它保持，低于它纠正纠正)3.雪堆博弈（雪堆博弈（Snowdrift game,SG） 考虑在一个风雪交加的夜晚，两人开车相向而行，被同一个雪堆所考虑在一个风雪交加的夜晚，两人开车相向而行，被同一个雪堆所阻。假设铲除这个雪堆使道路通畅需要的代价为阻。假设铲除这个雪堆使道路通畅需要的代价为c，道路通畅带给每个，道路通畅带给每个人的好处为人的好处为b，bc.如果两人一起动手铲雪，每人的收益均为如果两

14、人一起动手铲雪，每人的收益均为b-c/2；如果只有一人铲雪，虽然两人都可以回家，但是背叛者逃避了劳动，如果只有一人铲雪，虽然两人都可以回家，但是背叛者逃避了劳动，它的收益为它的收益为b，而合作者的收益为，而合作者的收益为b-c；如果两人都不铲雪，两人都无；如果两人都不铲雪，两人都无法及时回家，收益均为法及时回家，收益均为0.雪堆博弈中存在两个纯纳什均衡（雪堆博弈中存在两个纯纳什均衡（C,D）和）和（D,C） 在存在多个纳什均衡的情况下，个体如何抉择是一个难题。可以根据一些线索进行选择均衡，如果没有线索可以用的时候，个体可以以概率1-r选择铲雪，以概率r选择待在车里，r=c/(2b-c)为双方合

15、作时的损益比（Cost-to-benefit）。此时对对手来说选择合作或者背叛的期望收益是相同的这样对手无法通过改变策略来提高自己的收益，此时为演化稳定策略，然而此时的平均收益低于同时选择合作时的收益，所以个体在合作与背叛之间抉择的两难困境。与囚徒困境问题相比，合作更容易在雪堆博弈中存在。 鹰鸽博弈和胆小鬼博弈都可以归结为TRSP的情景，最好选择采取对手的反策略。4.猎鹿博弈（Stag-hunting game,SH） 如果两个猎人打猎同时发现一头鹿和两只兔子，他们必须齐心协力才能抓到鹿，然后平分这头鹿每人收益为5，这样兔子就抓不到了；每个猎人也可以毫不费力的各抓到一只兔子，获利为3，然而鹿会

16、跑掉；如果一个猎人抓兔子另一个抓鹿，前者（背叛者）获利3，后者（合作者）获利0。两个人的决策必须在同时做出。则（C,C）和（D,D）为两个纯纳什均衡。混合纳什均衡为：每个猎人以3/5概率抓鹿，2/5概率抓兔子，此时对手选择抓鹿或者兔子的期望收益相同。此为RTPS情形。考虑在均匀混合种群中，每个个体可与种群中的其他所有个体进行博弈。每对个体按照收益矩阵进行博弈。假设采用合作策略的个体比例为x,选择成为背叛者的比例为y，则种群中合作/背叛者的收益分别为： Taylor和Jonker利用复制动力学（Replicator dynamics,也称为模仿者动态）描述演化过程中策略的动态变化：种群中某个策略

17、比例的变化速度与采用这个策略的个体比例及其收益成正比：其中是种群的平均收益。由上面两组公式及x+y=1可以得到合作者的复制动力学方程：对于囚徒困境博弈来说，TRPS,观察到所以合作者的数量会逐渐减少并最终在种群中消亡。x=0为稳定的平衡点。网络上的博弈介绍1正则格子上的两人两策略博弈2BA无标度网络上的两人两策略博弈3 3 度相关无标度网络上的两人两策略博弈4 4 聚类的无标度网络上的两人两策略博弈51.网络上的博弈介绍 网络博弈理论首先由Nowak和May提出，考虑每个节点代表一个个体，节点间的边代表个体之间的相互作用关系，在每一轮中它们根据某个博弈模型进行交互作用，并采取统一的演化规则进行

18、策略的更新以使未来的收益最大化。网络结构与演化博弈之间有密切的联系，这方面的研究也称为网络演化博弈（Network evolutionary game）。博弈模型、网络结构和演化规则是网络演化博弈的3个要素。 一个广泛使用的演化规则为一个个体i随机选择一个邻居j,如果它们有不同的策略，i模仿j的策略的概率可表示为收益差的函数：2. 正则格子上的两人两策略博弈 正则格子（Regular Lattices）是每个节点的度都相同的格子网络。Nowak和May首先将空间结构引入囚徒困境，研究二维方格格子上的重复weak囚徒困境，即R=1，P=S=0，T=b。b1时个体更倾向于选择背叛策略。假设个体采用

19、简单的最优规则进行策略演化：每个个体与直接连接的邻居进行一轮博弈后，在下一轮中它会采取邻居（包含本身）中收益最高的个体在本轮的策略，这是一个确定性的演化规则。与种群均匀混合情况下合作行为消失不同，合作现象能在具有周期边界的二维方格格子上涌现：合作者通过结成紧密的簇来抵御背叛者的入侵。 初始时刻为网络中每个个体随机分配合作或背叛策略，（a）图显示了种群合作策略随时间的演化，经过一段长期暂态过渡过程，合作者的数目会逐渐趋于稳定.稳态合作者的比例是衡量合作涌现程度的重要指标。（b）说明随着“背叛者的诱惑”b的增加，网络会由全部合作变为合作背叛共存再变为全部背叛。变化过程中有两个阈值：背叛者出现的阈值

20、和合作者湮灭的阈值，它们也是衡量合作涌现程度的重要指标 我们可以从一个子图来理解正则格子上的合作行为涌现。考虑上图的三角形对顶子图。实心节点代表背叛者，空心代表合作者。考虑如下的演化规则：每个个体x与每个邻居按照weak囚徒困境进行一轮博弈，之后x会随机选择一个邻居y比较两者的本轮收益，如果被选择的邻居y的本轮收益高于x，则x会学习y的本轮策略并在下一轮博弈中使用，反之下一轮x会坚持其原有策略。 这种三角形对顶格子可扩展为（d）所示的Kagome格子，其聚类系数为1/3.在这种规则格子上，当b1.5时，只要初始有少量合作者构成三角形合作簇，合作行为可以有效在格子上扩展蔓延。 不同格子网络上合作

21、行为的涌现情况是不同的。以PD game为例，考虑一种随机策略演化规则Fermi规则：假设在每一轮博弈中，个体x会随机选择一个邻居y,并比较二者的本轮收益；下一轮x采取y本轮策略的概率为 若x的收益比y低，则x很容易接受y的本轮策略；若x的收益高于y，x仍会以微弱的概率采取y的策略，x的这一非理性选择由k来刻画，它描述了环境的噪音因素，反映了个体在策略更新时的不确定性。它趋于0意味着策略更新是确定的；趋于无穷意味着个体处于噪声环境中无法做出理性决策，只能随机更新自己的策略。上图显示了平均度为4的5种正则格子上的囚徒困境行为。 左图为具有不同平均度的带有周期边界的格子上雪堆博弈的合作频率fc随损

22、益比r的变化情况。更新规则：W（sxsy）=(Px - Py)/(1+r)3. BA无标度网络上的两人两策略博弈 考虑BA无标度网络上的PD game，在每一轮中，每个个体x与所有邻居进行一次博弈，累计收益Px作为该个体的适应度。策略演化时用公式： 与随机网络相比，BA无标度网络能够极大地促进合作行为的涌现，使合作者在网络中占据主导地位。可以通过分析背叛行为在BA网络上的扩散过程，来阐述中心节点能够有效抵抗背叛者入侵的机理。假设初始时刻只有一个最大度节点x为D，其余均为C。观察x对网络中合作行为的入侵性。上图说明了取不同的参数b时，x周围合作邻居比例随时间的变化情况。 从稳定状态的个体之间的动

23、态组织出发，可以进一步将处于稳定状态的节点分为三类：始终保持合作/背叛策略不变的称为纯合作者/背叛者，不断改变自己策略的个体称为骑墙者（Fluctuating individuals）。上图显示了ER随机网络和BA无标度网络上的囚徒困境博弈个体的动态组织行为。4. 度相关无标度网络上的两人两策略博弈 上图为在具有不同度相关性的同配无标度网络上个体进行囚徒困境博弈时，fc随b的变化情况。 当网络变得同配时，一方面，面对相同的诱惑，同配网络中会有更多的个体选择背叛，合作频率低于不相关网络；另一方面，合作湮灭的阈值也随rk的增加而递减，同配网络中合作者更容易消失。图为当变化不同的同配系数时背叛中心节点和合作中心节点周围合作邻居的比例随时间演化的变化情况。b=1.5图为稳定策略下无标度网络的合作者和背叛者分布情况，其中b=1.5(a)图中rk=0,(b)图中rk=0.3图为异配网络时合作频率fc随参数b的