假定博弈中,博弈双方均采用纯策略,S是所有纯策略的集合,代表所有在t阶段采用纯策略的行为主题集合,定义状态变量表示t阶段采用纯策略s的节点的群体比例向量,于是有:
在t阶段采用纯策略s的节点的期望效用为:
式中,表示采用纯策略s的节点在博弈对手采用纯策略r时的期望效用。于是群体的平均期望效用为:
根据前面的假设,有限理性的行为主体有一定的分析能力和对不同策略收益的判断能力,收益较差的主体迟早会发现这种差异,并开始学习模仿收益较高的主体的行为,因此,行为人的比例是随时间变化的,是时间的函数。上述比例随时间变化的速度取决于行为主体的学习模仿能力,而学习模仿能力取决于模仿对象数量的多少和模仿对象的成功程度两个因素。
于是,根据进化博弈论理论,我们可得如下模仿者动态模型:
根据上述方程,可知随着系统的演化,采用收益超过平均值的策略的节点比例将增加,采用收益少于平均值的策略的节点比例将减少,并最终稳定在一定的水平,达到动态均衡。
3.2对等网进化博弈模型
(1)博弈方。博弈双方均来自系统中随机选取的两个参与者。
(2)行为策略。博弈双方都有两种行为方式:积极参与、消极参与。如果两个消极参与者进行交互,双方都获得较低的收益,并且为参与网络交互付出一个较低的代价,如果博弈双方一方为消极参与者一方为积极参与者,则消极参与者能够获得较高的收益,付出较低的参与代价,积极参与者获得较低的收益而付出相对较高的参与代价,但是积极参与者能够在提供资源同时获得一定的情感满足,这种情感满足是由人的互惠行为所决定的。若两个是同样的节点则无所谓情感满足。如果两个积极参与者交互,那么他们都从中获得较高的收益并且都付出参与代价。相应的收益矩阵如下表1所示:
表1博弈双方收益矩阵
博弈方2
博弈方1
积极参与
消极参与
积极参与
-,-
-+,-
消极参与
-,-+
-,-
(3)行为策略的采取比例。博弈方均有可能采取消极参与或积极参与,假定初始状态下,系统中采取“积极”和“消极”策略的比例为。
由得益矩阵可知,该博弈的纳什均衡取决于、、、、的具体水平或者相对水平,根据上述假设,按照一般博弈的分析公式:
博弈方1中,“积极参与”类型参与人的收益为: (式1)
“消极参与”类型参与人的收益为:
(式2)
则博弈方1的期望收益为:
(式3)
根据模仿者动态方程,积极参与类型参与人比例的动态变化表示为:
(式4)
将式1、式3代入式4得:
要讨论该博弈的进化稳定策略,必须先找出模仿者复制动态方程的稳定态。令,可以求出三个不动点,也就是可能的稳定状态点,分别为:
(式5)
根据进化稳定的性质,一个稳定状态必须对微小扰动具有稳健性才称之为进化稳定策略。也就是说,作为进化稳定策略得点,除了本身必须是均衡状态外,还必须有这样的性质:如果某些博弈方由于偶然的错误偏离了该均衡,复制动态还会使得系统状态恢复到均衡点。
根据微分方程的“稳定性原理”可知:稳定状态处函数的导数小于0。下面分别讨论以上三个解成为进化稳定均衡得可能性及其性质。
由行为策略及其收益矩阵的定义假设可知:,因此
(式6)
下面分两种情况进行讨论,
(1)当时,复制动态方程的三个解都处于有效解范围内,即,此时,复制动态方程的相位如图1所示:
dx/dt
0
1
x
1-(Cp-Cn)/S
图1 0
由图1可以看出,是进化稳定策略。这意味着在一个完全由积极参与者的P2P系统中,一旦有少数成员改变策略消极参与,随着收益的增加,就会有更多的成员效仿,开始只消费资源而不贡献资源,此时,“搭便车”节点开始出现,直到整个系统中积极参与者与消极参与者的比例达到。反之亦然。
(2)当,复制动态方程的不动点只有和。此时复制动态方程的相位如图2所示:
dx/dt
0
1
x
图2 x3<0时的复制动态方程相位图
此时复制动态方程唯一稳定的均衡点就是,也就是说P2P系统中的成员都是消极参与类型的。只要不是一开始所有成员都是积极参与类型的,最终都会在长期的系统动态演化过程中趋于消极参与。即使是所有成员都积极参与,只要出现突变成员,即有消极类型的参与者出现,就会破坏整体积极参与的现状,最终使得系统演化为集体消极参与。
的情况下,复制动态方程的相位如图3所示:
dx/dt
0
1
x
图3 x3>1时的复制动态方程相位图
唯一的进化稳定策略是,也就是所有成员都积极参与。
由以上分析可知,第三种情况是我们所期盼的。遗憾的是由于积极参与者比消极参与者要提供更多的共享资源,即参与成本更高,这种情况永远不会发生。我们只能通过调整中的参数、、的值,使得在系统稳定状态下,有更多比例的节点采取积极的参与策略。
消极参与者的参与成本是由P2P软件的最低使用条件决定的,我们可以认为其近似等于0,这个参与成本是固定的。所以只能降低积极参与者的参与成本,使得的分子最小;分母表示的情感满足是不同参与人对相同代价的承受能力,因参与人所处环境和情感因素而定,我们无法左右参与人所处的环境和情感等因素,但是可以通过建立激励制度使积极参与者获益、消极参与者受到惩罚,从而变相提高值,这就是前面所说的强互惠者所扮演的角色。
整个系统总是处于动态之中,节点根据自身对性能的要求和付出代价的承受能力,不断选择或放弃不同的策略,最终选择不同参与策略节点的比例维持在侵入边界附近,因此,提高侵入边界的值是改善整体效用的根本,即通过一定的机制设置,降低积极参与者参与成本,并给予其激励,使得积极参与者更容易地获取资源,是维持整个对等网络良性发展的必然选择。
4. 小结
本文运用进化博弈论的相关理论分析对等节点的有限理性及间接互惠行为,针对对等节点的自私和有限理性特征提出了基于进化博弈的对等网激励模型,通过描述对等网的演化过程,分析了模型的进化均衡策略,为拓扑构造和资源发现机制的研究提供了基础。
5. 参考文献
< >中国互联网大会报告,URL:http://www.internetdigital.org/2007,北京,2007.09.24-26.Dejan S. Milojicic, Vana Kalogeraki, Rajan Lukose, Peer- to-Peer Computing, HP Labs, Palo Alto, Tech Report:HpL-2002-57,2002.张维迎 著,博弈论与信息经济学,上海人民出版社.1997.5:82-90.A.Kim, L.J. Hoffman, Pricing Napster and Other Internet Peer-to-Peer Applications, Tech Rept:CPI-2001-02, George Washington University,2001.1.J.Lackey, Riverstone Networks, Coping with P2P Applications, Mitigating Bandwidth Consumption on Managed Networks White Paper, URL:http://www.riverstonenet.com /pdf/p2p.pdf,2002.10.B.Chun, Y.Fu, Bootstrapping a Distributed Computational Economy with Peer-to-Peer Bartering, Workshop on Economics of Peer-to-Peer Systems, 1nte1 Research, IRB-TR-03-031. Berkeley,2003.6.张良桥,理性与有限理性:论经典博弈理论与进化博弈理论之关系,世界经济,2001(8):74-78.杨栎,徐立译赫伯特·西蒙.现代决策理论的基石[M].北京:北京经济学院出版社,1989:20-22.李少斌,企业家形成机制:进化博弈论的研究视角(M).经济科学出版社.2005.12:216-226.杨舰,对等网有效搜索机制研究,复旦大学博士学位论文,2004.04.唐九阳,张维明,肖卫东等,类人类社会基于社区的对等网自组织构造,计算机研究与发展,2006.43(8):1383-190.黄道颖,黄建华,庄雷,李祖鹏.基于主动网络的分布式P2P网络模型.软件学报,2004.15(7):1081-1089.田慧蓉,P2P网络信任模型及激励机制的研究,博士学位论文,北京邮电大学,2006.4S. Saroiu, P. K. Gummadi, S. D. Gribble. A Measurement Shady of Peer-to-Peer File Sharing Systems. In MMCN’02.2002.张维迎 著,博弈论与信息经济学,上海人民出版社.1997.5:82-90.