摘 要：针对P2P系统中的搭便车问题，提出了一种基于混合策略博弈的激励机制。将信誉值作为激励节点贡献资源和提供服务的基础,节点是否能获得服务也是与节点当前信誉值成比例的，节点只能通过提供服务来增加其信誉值。同时节点是否响应服务请求是以某一概率来进行的，通过调节该概率来有效的激励节点提供服务。仿真实验表明，节点在经过一段时间的博弈之后，其响应次数和请求次数基本相等，提高了节点在系统中的参与度。
关键词：混合战略博弈； P2P； 激励； 信誉

P2P系统是一个灵活的分布式系统，节点既是服务器也是客户机，相互之间可以提供各种服务。然而传统的P2P系统没有设计有效的激励机制，从而导致了搭便车和公地悲剧的发生。参考文献[1]提出，在Gnutella中，70%的用户从来不提供文件共享，而其中50%的文件查询响应来自1%的共享用户。搭便车现象已经严重影响了目前P2P系统的发展。目前已经提出一些机制来抑制搭便车现象：(1)微支付机制，服务提供者从服务获得者处收取一定的报酬，可以是现实货币，也可以是虚拟货币；(2)信誉机制，高信誉的节点可以获得更好的服务质量。然而从实际情况来看，微支付机制需要提供一个正规的经济模型，实际操作上相对比较困难，而基于信誉的激励机制目前看来更有发展前景。本文以节点的信誉作为激励节点行为的基础，通过混合策略博弈的方法来激励节点共享资源并提供服务。
1 相关工作
　对于存在自私节点的P2P系统，博弈论是一个理想的分析节点行为的工具。笔者模拟了一个无限重复博弈的P2P系统，并计算每一次博弈中所存在的纳什均衡。
　假设网络的生命周期是无限长的，并将其划分成一个个小的时间段t，t=0,1，…,∞。在每一个时间段里，每个节点都收到一个服务请求，同时自己也发出服务请求。如果服务提供者同意提供服务，则请求将得到满足。如果一个节点在一个时间段内获得了多次服务，则其收益为0。在实际应用中，一些节点可能会同时收到一些服务请求，然而其中有些请求可能是来自信誉较低的节点，可以将其忽略。当一个节点在时间段t内响应了一个服务请求，则其战略为{响应}。
　将节点间的交互模拟成一个无限重复博弈的模型。在每一个时间段t内进行一次博弈G，节点请求服务，同时决定是否响应其他节点的请求服务。
在此博弈中，参与者为P2P系统中所有的节点，而节点的战略集为{响应，不响应}，节点的收益函数将在后面进行定义。本文将无限重复的博弈G记为G′。
2 信誉模型

3 纯战略博弈
下面分析无限重复博弈的纳什均衡的可能性。由无名氏定理[2]可知：如果a’是博弈G的纳什均衡的战略集，那么当G重复进行无限次后，a’仍然是其纳什均衡的战略集。则求无限重复博弈G’的纳什均衡可以简化为求一次博弈G的纳什均衡。
　首先讨论纯战略博弈纳什均衡的情况。当所有的节点都选取战略{不响应}时，也是一个纳什均衡的解，此时每个节点的收益都为0。当某一节点i想改变战略对服务请求进行响应时，其收益为-C，比不响应时的收益降低了。因为节点都是理性的，所以节点不会采取这种策略。另外战略{不响应}也是一种不理想的均衡，在P2P系统中，如果所有的节点都不提供服务，系统将无法运行下去。所以这种均衡是无法达到的，而且在系统中总会有少数的利他主义节点存在。同样如果所有节点都选择{响应}战略，也不能达到纳什均衡。很明显，某一节点改变策略选择{不响应}的话，其收益明显比选择{响应}高，因为它既能在网络中获得服务，同时也不会因提供服务而产生系统开销。因此，在P2P系统中纯战略博弈是无法达到纳什均衡的。
4 混合战略博弈
　现在来分析混合战略均衡的的可能性，在此，节点不再是确定的选择某一战略，而是以某一概率来选择其战略。

参考文献[2]给出了混合战略博弈纳什均衡的一个重要特点：在纳什均衡中每个参与者的期望收益应为其在符合正向概率时选择任意策略时的期望收益。
由这个混合策略纳什均衡的特点可以得出：

从式(5)可以看出，P不是一个定值。每一时间段的P是随着上一次博弈结束后，节点的信誉值的变化而变化的。如果每一个节点都采取这种混合策略，那么对他们而言，该策略是最佳策略。本文认为这个策略比都不提供服务的策略稳定，因为如果都不提供服务，那么系统将失效。另外，在P2P系统中总会有少数的利他主义节点存在。所以，在该系统中不会有不合作的情况出现。
5 实验及结果分析
　仿真实验采用peersim仿真工具，该仿真工具是基于Java开发的，由很多组件构成，适合于大规模的动态的P2P网络。在本实验中模拟了1 000个节点的P2P网络，每个节点都采取混合策略博弈算法，在一段时间的重复博弈之后，从中随机地取出了一些节点进行观察，发现他们的行为基本趋于一致。
图1是在纳什均衡策略下节点可能的信誉变化的仿真结果。图示表明,在节点信誉值增加的时间段表示节点响应了其他节点的服务请求，而信誉值下降则表明节点拒绝了其他节点的服务请求。可以看出，经过10个时间段后，混合策略纳什均衡使得每个节点信誉值处于一个相差不大的水平，这说明节点都采取了该策略。在图1中，笔者随机地选取了3个节点，设定其初始信誉值分别为0.8、0.5和0.2，其中α=0.8，β=1，C/U=0.1。

　从仿真实验中随机选取了一个节点，对其α的取值进行了3次不同的实验。从图2可以看出，节点的上传和下载比在经过一段时间后都几乎达到了1，这说明节点响应其他节点服务请求的次数和自己本身发出的得到响应的服务请求次数基本相等，节点在获得服务的同时也为他人提供了服务，有效地抑制了节点搭便车现象。而对于不同的α取值来看，α取值越大，节点的上传和下载比趋近于1的速度越快。而从信誉模型来看，α取值越大在实际中也是比较合理的，这样节点不能通过一次的服务提供来大幅度地提高节点的信誉度，而且节点也不会因为一次拒绝响应服务而大幅度降低信誉值。

再来分析一下C/U对于响应概率P的影响。前面已经介绍了C是节点在响应其他节点服务请求时所产生的系统开销，例如在文件共享系统中网络带宽的消耗以及硬盘的磨损等等。U是节点获得服务响应后所得到的理论最大收益，但并不是实际收益。节点的实际收益还与其信誉值是挂钩的。例如在文件共享系统中，节点下载一部电影获得的理论最大收益为U，而节点当前信誉值为R，则节点的实际收益为UR。也就是说节点的信誉值越高，节点所获得的收益越大，比如可以获得更好的下载带宽以及较高的优先级。从实际中来分析C/U肯定是一个较小的数值，因为C要小于U在实际的系统中才比较合理。在仿真中取了几个C/U的值进行了实验。
　从图3来看，C/U越大,节点响应服务请求的概率也会增大，但是C/U如果太大的话，在实际应用中又会降低系统的总体效率，因此C/U的取值应该根据不同的系统应用来设置，以求达到一个平衡。在实际应用中，如果节点响应服务请求的概率P的平均值能维持在50%左右的话，就基本上是满意的。在图3中α=0.8，β=1。

针对目前P2P网络中比较盛行的搭便车现象，本文引入了混合策略博弈的方法，有效地激励了P2P网络中的节点积极响应其他节点的服务请求。通过仿真实验发现，该机制实现了抑制自私节点，鼓励节点为系统多贡献资源的目的。
参考文献
[1] ADAR E, HUBERMAN B, Free riding on gnutella[J]. First Monday, 2000,5(10):42-68
[2] OSBORNE M J. A course in game theory. Cambridge, Mass.: MIT Press, c1994.
[3] NASH J F. Equilibrium points in N-person games, Proc. Natl. Acad. Sci. USA,1950,36:48-49.
[4] BURAGOHAIN C, AGRAWAL D, SURI S. A game theoretic framework for incentives in P2P systems. In Proc. of the Third International Conference on Peer-to-Peer Computing(P2P’03), 2003.
[5] GOLLE P. Incentives for sharing in peer-to-peer networks. In Proc. of 2001 ACM Conference on Electronic Commerce.