N人合作博弈的Nash及演化均衡稳定策略分析

ComputerEngineeringandApplications计算机工程与应用2010，46（17）

11

N人合作博弈的Nash及演化均衡稳定策略分析

2

黄武军1，刘天虎2，许维胜2，吴启迪1，

2

HUANGWu-jun1，LIUTian-hu2，XUWei-sheng2，WUQi-di1，

上海2000921.同济大学经济与管理学院，

上海2000922.同济大学电子与信息工程学院，

1.SchoolofEconomics&Management，TongjiUniversity，Shanghai200092，China

2.SchoolofElectronicsandInformationEngineering，TongjiUniversity，Shanghai200092，ChinaE-mail：[email protected]

HUANGWu-jun，LIUTian-hu，XUWei-sheng，etal.StablestrategyanalysisofNashandevolutionaryequilibriumbased

（17）：onN-personcooperativegames.ComputerEngineeringandApplications，2010，4611-14.Abstract：ThispaperanalyzesthesymmetricNashequilibriumofN-personcooperativegamesbasedonboundedrationality.Andthestablestrategyofevolutionaryequilibriumisrealizedthroughadoptingevolutionarygamestheoryandtheequilibriumpoints

aregotunderdifferentstrategies.Furthermore，byusingmechanismofreplicatordynamic，thestablesetofreplicatordynamicisresearchedunderdiscretetimeandcontinuoustime.Eventually，apracticalexampleisprovidedtoillustratethevalidityofthismethodfortheselectionofgameequilibrium.Keywords：cooperativegames；evolutionaryequilibrium；stablestrategy

摘要：在有限理性的基础上，对N人合作博弈的对称Nash均衡进行了分析，并引入演化博弈理论分析了参与人的演化均衡稳定策略，得到了不同策略选择下的均衡点。进而应用生物复制动态理论对离散时间及连续时间下的复制动态稳定集进行了研究。最后通过实例说明了该方法在博弈均衡选择上的有效性。关键词：合作博弈；演化均衡；稳定策略DOI：10.3778/j.issn.1002-8331.2010.17.004

文章编号：（2010）1002－833117-0011-04

文献标识码：A

中图分类号：C934

1引言

演化博弈均衡基于个体的有限理性，个体的决策通过模仿、学习和动态突变来实现，通过复制动态来描绘有限理性个体的群体行为变化趋势，并能有效预测个体的群体行为。相互作用的个体的均衡行为常用博弈模型加以描述，虽然参与博弈的盟友可能相当多，但他们之间的行为策略常被简化为两人博

[1]

弈的情形，如：（1990）分析了演化博弈稳定性的动态Bomze等因素，提出在复制动态下的演化均衡的纯动态特性。Cressman

[2]

（1995）研究了两种生物复制动态系统，指出该系统的最优解

[3]

也就是复制动态系统的稳定集。（1997）分析了2×2演化Maria

博弈复制动态下的混合策略均衡，利用严格的Ljapunov减函数对复制动态进行了修正，描述了连续时间下的最佳回报模

[4]

型。Ellison（2000）对长期动态均衡及演化均衡的形成速率进行了系统研究。近十年间，也有相当多地学者对于多人合作博

[5]

弈进行了系统的研究，如Kobayashi（2000）分析了两个以上演

[6]

化稳定均衡情形。Oechssler（2001）研究了无限策略空间下的演化博弈复制动态行为，提出了一种新的稳定性条件。Hof－

[7]

（2002）认为，在两个策略下的N人对称合作博弈的bauer等

标准支付配置可转移到具有Nash均衡和演化稳定均衡策略的

[8]

超对称合作博弈。Dominik等（2005）分析了三人合作博弈多演化稳定策略的随机均衡，指出在一定的博弈条件下，演化稳

[9]

定均衡不一定能得到满足。Clemens等（2006）分析了有限理性下的动态博弈行为模式，应用复制动态演化算法得到了纯策

[10]

略下的Nash均衡。Heifetz等（2007）对动态演化的参数选择进行了研究，分析了博弈参数的有限配置，得到了独立参数的

[11]

演化规律。孙锐等（2009）利用演化博弈方法对动态联盟知识共享机制进行了研究，分析了知识共享系统的演化规律。蔡玲

[12]

如等（2009）利用系统动力学的方法建立了一个混合战略演化博弈模型，通过仿真验证了非对称结构的2×2混合策略演化博弈模型不存在演化均衡。在以上研究的基础上，针对N人合作博弈具有两个不同策略的情形，研究了其对称Nash均衡和演化稳定均衡策略。

2有限理性假设

经典的博弈理论要求参与博弈的双方是完全理性的。然

基金项目：国家重点基础研究发展规划（973）（theNationalGrandFundamentalResearch973ProgramofChinaunderGrantNo.2002CB312200）。作者简介：黄武军（1972-），男，博士生，主要研究方向：决策管理及博弈论研究；刘天虎（1974-），男，博士后，主要研究方向：控制科学与工程、博弈

论及系统动力学研究；许维胜（1966-），男，教授，博导，主要研究方向：自动化控制系统理论与工程研究；吴启迪（1947-），女，教授，博导，主要研究方向：智能自动化系统理论与应用研究。

修回日期：

12

2010，46（17）ComputerEngineeringandApplications计算机工程与应用

）（）（）。E（iλ=Σλsξis

s∈S

而，在现实生活中这种完全理性的情况很难实现，主要考虑到

其一是每个人的认知能力是不同的，在收集两方面的原因[13]：

与获取信息时难免存在失真；其二是信息沟通方面的限制使得信息传递过程中难免存在失真。于是这里引入有限理性的假设，存在有限理性参与人的博弈就形成的有限理性博弈。

博弈双方具有有限理性，也就意味着博弈过程中各方不可能通过一次博弈就能找到获得最大收益的理想策略，而是通过多个重复博弈过程来实现，这里的多个重复博弈过程也就是一个持续的学习过程，博弈参与人能通过模仿来找到理想的策略。有限理性也暗示着在一次博弈中总会存在盟友选择不完全理性的均衡策略的情形，盟友通过改变自身的策略来实现再次均衡，最终找到最佳策略。这种对有限理性下的博弈行为的研究具有重要的现实意义，它可以用来解释大量的经济现象，如房地产开发商Cartel联盟谈判均衡的演化稳定策略等。

定义4如果对于任意i∈Ψ，有E（，）（，），ki∈Γi，iλiλ-i≥Eikiλ-i

则λ∈Ω是一个Nash均衡，有限个盟友的Nash均衡是非空集，可表示为ΩOE。

这里仅考虑对称Nash均衡的情形，其特点可表示为ΓOE=（λ，其中（λ，（λ，…，），其支付函{λ∈Γ：λ）∈ΩOE}，λ）=λ，λ数可表示为ξ（λ，。λ）

定理1对于对称合作博弈，如果λ∈ΓOE，则对于任意s∈（λ），有E（θ，（λ，为常数；如果λ∈intΓ，当且仅SPλ）=Eλ）当E（θ，（λ，为常数时，有λ∈ΓOE。λ）=Eλ）

证明这里可利用反证法证明。如果λ∈ΓOE，对于所有s，有E（θ，（λ，，如果存在s∈SP（λ）使得E（θ，λ）≤Eλ）λ）

n-1s

n-1

n-1

s

n-1

s

n-1

n-1

s

n-1

n-1

n-1

n-1

n-1

3N人合作博弈的对称Nash均衡

3.1对称合作博弈策略

定义1N人合作博弈可表示为v=（Ψ，），其中Ψ={1，S，ξ2，…，而S为盟友的策略空间，…，n}是盟友的集合，si={s1，s2，si}∈S是每位盟友的策略集，ξ：S→R是每个纯策略的支付函数，（s）（s），（s），…，（s）ξ={ξ1ξ2ξn}。这里仅考虑具有对称结构的合作博弈，因为在这种情况下，所有Cartel联盟中的盟友在合作博弈中具有相同的角色，同时盟友的支付函数仅由他所采取的策略及其他不同策略的盟友数决定。

定义2如果对于每位盟友序列集有η：，，…，Ψ→Ψ，ξ（is1s2（sη，，…，）成立，则称N人合作博弈具有对称sn）=ξη（i）sηsη（1）（2）（n）

-1

），则有

s

n-1

（λ）s∈SP

Σ

（θ，λiEλ

n-1

sn-1

）

（λ）s∈SP

Σ

（λ，λiEλ

n-1

n-1

），而

n-1

（λ）s∈SP

（θ，λΣλE

i）（λ，，ΣλiE（λ，（λ，，=Eλ）λ）=Eλ）

（λ）s∈SP

n-1

n-1

Ψ

可见不可能存在E（λ，（λ，。同样，如果λ∈intΓ，对λ）

（）s∈SPβ

s

n-1

n-1

s

n-1

（β）s∈SP

Σ

（λ，βiEλ

n-1

n-1

），而

（β）s∈SPn-1

Σ

（θ，βiEλ

sn-1

）=E（β，λ

n-1

n-1

），

（β）s∈SP

（λ，λΣβE

i

）（λ，，故有：（β，（λ，为常=Eλ）Eλ）=Eλ）

n-1

数成立，λ∈ΓOE。

结构。

定义3如果对于任意盟友序列集有η：，，Ψ→Ψ，坌i，ξ（is1s2…，（sη，，…，），则称N人合作博弈具有超对称性。sn）=ξ1sηsη（1）（2）（n）例如已知盟友具有m个策略，其支付函数可以用一个m×

（uij），而对于三位盟友参与的合作谈判的支m的矩阵表示，U=付配置可表示为：（U1，…，，其中，对于坌i∈（1，U=U2，Um）2，…，），m

坌

坌坌坌坌坌坌坌坌坌坌坌坌

3.2合作博弈的对称Nash均衡分析

N人合作博弈的对称Nash均衡的讨论是比较复杂的过程，不失一般性，在这里以三位盟友的双策略集作为研究示例，对于推导至N人合作博弈的对称Nash均衡具有重要的参考价值。三位盟友的双策略集如下：

U=

222222

u10

0u2

，0

u2

0u3

2

u11iu12i…u1miu21iu22i…u2mi

…um1ium2i…ummi

…

…

Ui=

坌坌坌坌坌坌坌坌坌坌坌坌坌

由定理1可知内部点（λ，）要形成对称Nash均衡的条1-λ件如下：

（1-λ）（1-λ）圯（u1+2u2-u3）（u2-u3）u1λ=2u2λ+u3λ-2λ-u3=0如果u2=（u3-u1）则以上等式可以简化为：（u1+u3）/2，λ=u3。此时，当u1+u3=0，则不存在内部对称Nash均衡解；u1，u3≠0时，当u1=u2=u3=0时，每一点都是对称Nash均衡解；当u1+u3≠0，是内部Nash均衡解。令（）为二次方u1u3>0时，λ=u3（/u1+u3）fλ函数，则可得到：

（1）（）（）f1=u1，f0=-u3

（2）f（′λθ）=0圳λθ=

s

2

2

2

特别地，当三位盟友各具有两个不同策略时，U=u

22u

111211

u121uu

，112122

u221u212u222

2222

m

对于盟友i路径下的混合策略可表示为λi，而所有路径下的混合策略可表示为Γi，…，其Γi={λi∈R：λi={λi1，λi2，λim}}，中λij≥0，Σλij=1。

j=1m

u2-u3

123

对于纯策略通常可表示为θ=（0，…，…，），而混合策1，0略λi是纯策略的非零集，可表示为SP（λi）全体混={s∈Si：λij}，合策略的集合可由Ω表示，如果s={s1，…，且有λ∈Ω，s2，sn}，则有λ（s）这样可得到盟友i路径下的期望支付为=仪λis，

i=1

i

u+uu

（3）（fλθ）=-213

123

是（的导数，从式（1）可以看出，如果u1u3>0，则（）f（′λθ）fλθ）fλ存在唯一的根在（0，之间，也就是说存在唯一的内部对称1）

如果u1u3

n

黄武军，刘天虎，许维胜，等：N人合作博弈的Nash及演化均衡稳定策略分析

足以下条件：

（1）1>λθ>0

u+uu

（2）（）（f0fλθ）=213×u3≤0

123

从（1）可知，或者有u2>Max（u3，（-u3，，或者-u1）=-Minu1）有u2

由（2）可以推出u3>0，u2≤-姨13或u3

称Nash均衡解；当u2>姨13，则存在两个Nash均衡解。此外，当u1u3=0时，如果u1=0，则存在以下等式：

（）（2u2-u3）（u2-u3））（2u2-u3）（u2-u3）fλ=λ-2λ-u3圯f（′λ=2λ-2（））当且仅当u2u3

（）（u1+2u2））（u1+2u2）fλ=λ-2u2λ圯f（′λ=2λ-2u2

于是可得到，（））当且仅当u1u2>0时，（）存f0=0，f（′0=-2u2，fλ在介于（0，）之间的根。1

同理，可以将对称Nash均衡解推广到N人合作博弈的情形。

22

2

2010，46（17）

13

略。该定理只对两人合作博弈有效，而对于三人以上的合作博

弈则不一定有效。对于三人合作博弈有以下推论1：

推论1对于三位谈判盟友的对称合作博弈，如果λ，β∈ΓESS，且λ≠β时，则必然有SP（λ）（β）。≠SP

4.2演化稳定均衡分析

前面分析了演化稳定策略的相关定义及定理，在这里，继

仍假设存在三位盟续分析演化稳定均衡点。为了不失一般性，

友的双策略集：

U=

u00

，埭埭埭埭u0u

1

2

2

u3

埭埭

22

通过定理3可知，当且仅当λ的邻域内β=（β，）1-β∈Γ

时，存在λ∈ΓESS的演化稳定策略。于是可以进一步推导如下：

（1）（1-β）（1-β）>0λ>β圳u1β-2u2β-u3（2）（1-β）（1-β）

当且仅当λ的邻域内β∈Γ时，有λ∈ΓESS的演化稳定策略，当）））求导f（），可以得λ>β时（fβ>0；λ

（1）两个纯策略均衡点和一个混合策略均衡点

（1，），（0，）（λ，）ΓESS={01}，ΓOE\ΓESS={1-λ}

（u-u）+u+uu当u1>0，（u3-u1）u3>0，u2≠/2时，λ=23213；

123

特别地，当u2=（u3-u1）；当u1>0，/2时，λ=u3（/u1+u3）u2>0，u3=0时λ=（2u2）（；当u1=0，。/u1+2u2）u20时，λ=-u3（/2u2-u3）

（2）一个纯策略均衡点和两个混合策略均衡点

（1，），（λ1，（λ2，当u1>①ΓESS={01-λ1）}，ΓOE\ΓESS={1-λ2）}，0，u2>姨13

2

22

4人合作博弈的演化稳定均衡策略

4.1演化稳定策略

接下来，引入N人合作博弈的演化稳定策略的相关定义及定理[14-17]：

定义5如果存在φ∈（0，），对于φ∈（0，）及任意β∈Γ，1φ都必然存在下式成立：

（λ，（φβ+（1-φ）））（β，（φβ+（1-φ）））Eλ>Eλ则称λ∈Γ是演化稳定策略（ESS）。

定义6如果存在λ的一邻域W，及所有的β∈W∩Γ，存（β，（λ，，则称λ∈Γ是优元，当且仅当λ=β在Eβ）≤Eβ）时，等号成立。

定理2当且仅当λ∈Γ是优元时，（证明略）λ∈ΓESS。

令λ，定义如下激励函数：β∈Γ，

（）（θ，（θ，fβ=Eβ）-Eβ）

定理3存在两个策略集的N人对称合作博弈，当且仅当有λ∈ΓESS，并存在以下条件成立：（1）如λ的邻域内β∈Γ时，

果λ>β，则有（）（2）如果λ0；fβ

证明考虑到以下函数：

（β）（λ-β，，通过定理2可知当且仅当λ的邻域内fλ=Eβ）有λ∈ΓESS，且λ≠β，可得fλ（β）所以有下式成立：β∈Γ时，>0，

（β）（λ-β）（E（θ，（θ，）（λ-β）（）fλ=β）-Eβ）=fβ于是以上条件得证。可以看出，当且仅当（）是λ邻域上的减函数时，fβλ∈ΓESS是演化稳定集。

当n≤3时，可以得到以下结论：当且仅当（））fβ=0和f（′β

定理4对于两位谈判盟友的对称合作博弈，如果λ，β∈ΓESS，且λ≠β时，则必然存在SP（λ）（β）。埭SP

特别地，如果λ∈ΓESS∩IntΓ，则λ是唯一的演化稳定策

1

n-1

2

n-1

n-1

1

n-1

2

n-1

n-1

n-1

*

*

n-1

*

*

n-1

*

（u-u）-u+uu

，u3

123

（u2-u3）+u2+u1u3

；

u1+2u2-u3

（0，），（λ1，（λ2，当u1

（u-u）-u+uu

，u3>0时，λ1=23213，λ2=

123

（u2-u3）+u2+u1u3

。

123

（3）一个纯策略均衡点和一个混合策略均衡点

（1，）（λ，）①ΓESS={0}，ΓOE\ΓESS={1-λ}，当u1>0，u2=u3

（0，）（λ，）当u10时，λ=

3；当u1=0，u2>0，u3

+姨1姨3

3；当u1

+姨1姨3

（4）一个混合策略均衡点（λ，）当u2=（u3-u1）ΓESS={1-λ}，ΓOE\ΓESS=Φ，u1

；当u2≠（u3-u1）λ=u3（/u1+u3）/2时，λ=23213。

123

（5）两个纯策略均衡点①当u1=0，u2>0，u3=0或u1>0，u2≥0，u3=0时，ΓESS=（）（0，）0}，ΓOE\ΓESS={1}；{1，

②当u1=0，u20时，ΓESS=（）（1，）1}，ΓOE\ΓESS={0}。{0，

（6）一个纯策略均衡点

①当u1>0，u2

②当u1-姨13，u3>0或u1

（7）无限均衡点当u1=0，u2=0，u3=0时，ΓOE\ΓESS=Γ。

，（01

图1两个纯策略均衡点和一个混合策略均衡点

（2）情形2

u100

，U=

u20u2

∩∩∩∩∩∩≠∩∩∩∩∩

u3

=

4

00，01010-9

4.3复制动态的渐进稳定集

根据有限理性假设，知道不同的盟友会学习与模仿对方，合

作博弈均衡将是一个随时间变化的函数，这里可以利用复制动态来分析N人合作博弈的动态均衡，其状态在时刻t可由一矢量表示为λ（t）（t），（t），…，（t）（t）），={λ1λ2λn}，λ∈Γ，Σλ（it=1

i

由于u1=4>0，所以有：u3=-9

弈而言，在时刻t离散策略的复制动态的期望支付可表示为[18]：

（θi，））（θi，））Eλ（t=Σξθλ（it

s∈S

s

n-1

s

故有：1-λ1=2/3，1-λ2=2/11。所以这时的合作博弈谈判有3个均衡点，（1，），（1/3，）（9/11，）包括ΓESS={02/3}，ΓOE\ΓESS={2/11}：一个纯策略均衡点和两个混合策略均衡点。如X-Y相图2所示。

而t+1时刻的离散复制动态方程可表示为：）（λ（it+1=λit

（））ξ（iλt=λ（itn-1s（λ（t），））Eλ（t）（，（t））Σλ（jtEθjλ

j

（θi，））Eλ（t

sn-1

，（01

连续时间的复制动态可描述如下：觶（t））λ=λ（sst×π觶（t+1））λ=ελ（sst[1+△×π]

其中：（θ，））（λ（t），））。其中：π=Eλ（t-Eλ（t△>0用于表示

一定的时间间隔，π为动态变量，ε为常数。同样以三位盟友的双策略集作为分析对象，可以得到其复制动态的稳定集为：Γ=（t）（θ，））（λ（t），）），内部均衡{λ∈Γ：Eλ（t=Eλ（t}，坌s∈SP（λ）点为Γ=Γ∩intΓ。

*

△

s

n-1

n-1

△

s

n-1

n-1

图2一个纯策略均衡点和两个混合策略均衡点

6结论

房地产开发商的Cartel联盟往往通过谈判来实现演化均

衡的稳定策略，而演化均衡是一个学习的过程，经过重复博弈以三位合作博的纠偏与试错来找到最佳策略。基于有限理性，

弈参与人为例对其对称Nash均衡进行了分析，同时引入演化博弈理论得到了不同策略选择下的演化均衡点，并分析了离散该方法可预测Cartel联时间及连续时间下的复制动态稳定集。

盟合作博弈的稳定策略，当然对于复制动态的系统转化规律还需进行深入研究，接下来的工作将引入系统动力学理论对其进行探索。

5实例分析

假设在一个区域的房地产市场上有三家实力相当的开发商，连同一些小的开发商策划形成Cartel联盟，以谋求价格上的垄断，获取更多的消费者剩余。其间以这三家为代表的开发商通过谈判来达到利益的演化均衡，考虑如下两种情况：

）情形1（1

u0000，00U=01u，uu=3

010107232

∩∩∩∩

∩∩∩∩∩∩

∩∩

参考文献：

[1]BomzeIM.Dynamicalaspectsofevolutionarystability[J].Mathematik，

（3/4）：1990，110189-206.

[2]CressmanR.Evolutionarygametheorywithtwogroupsofindividu－

als[J].GamesandEconomicBehavior，1995，11：237-253.

[3]MariaSM.Ontheasymptoticconvergencetomixedequilibriain

2×2asymmetricgames[J].InternationalJournalofGameTheory，（4）：1997，26549-559.

由于u1=3>0，（u3-u1）（7-3）所以有：u3=7>0，/2=/2=2≠u2，（u-u）+u+uu）+3×7=7λ=23213=（u1+2u2-u33+2×10-78

故有：1-λ=1/8，所以这时的合作博弈谈判有3个均衡点ΓESS=（），（0，）（7/8，）包括两个纯策略均衡点和{1，01}，ΓOE\ΓESS={1/8}：一个混合策略均衡点。如X-Y相图1所示。

（下转26页）

4323221Z

11Â（a）DS算法所得的MSE

图4误差帧的比较图

Z

（b）APS算法所得的MSE

为参考帧，块的大小同样采用8×8，匹配准则仍然使用MSE。分

别用DS算法及APS算法得到第六帧的误差帧。图4中所示为DS算法和APS算法产生的误差帧。

实验3搜索匹配时间的比较

（360×288）的第五帧作为测试选取视频序列missamerica

帧，块的大小为8×8。对于FS、分别得到TSS、DS和APS算法，第六帧的恢复帧。匹配时间如表1。

表1

各种算法搜索匹配时间表

匹配时间/s0.03930.01460.01350.0083

FSTSSDSAPS搜索算法

通过分析视频图像中运劣与否直接决定整个编码性能的好坏。

动对象的特点，提出了基于区域生长的改进BP神经网络的自适应预测编码算法。从不同的角度出发，采用传统的分割方法和现代信号处理技术相结合的方法，将区域生长法、边缘检测法和改进的BP神经网络构成一个分割体系，然后进行自适应压缩编码。从实验结果上看，系统提高了对环境的适应能力，用较短的时间取得了很好的分割及压缩效果。

参考文献：

[1]FanJP，YauDKY.Automaticimagesegmentationbyintegrating

color-edgeextractionandseededregiongrowing[J].IEEETransactions（10）：onImageProcessing，2001，101454-1466.

[2]ShihFY，ChengShou-xian.Automaticseededregiongrowingforcolor

2005，23：877-886.imagesegmentation[J].ImageandVisionComputing，

[3]ChenT，MetaxasD.Ahybridframeworkfor3Dmedicalimageseg－

（6）：mentation[J].MedicalImageAnalysis，2005，9547-565.[4]ChenG，TianG.Ahybridboundarydetectionalgorithmbasedon

（9）：watershedandsnake[J].PatternRecognitionLetters，2005，261256-1265.

复旦大学出版社，[5]张立明.人工神经网络模型及其应用[M].上海：

1992.

王建华.神经网络技术及其应用[M].哈尔滨：哈尔滨工业大[6]吴简彤，

学出版社，1998.

赵大丽.动态联盟知识共享的演化博弈分析[J].运筹与管理，[11]孙锐，

（1）：2009，1892-96.王红卫，曾伟.基于系统动力学的环境污染演化博弈问题[12]蔡玲如，

研究[J].计算机科学，（8）：2009，36234-238.杨梅英，陈良猷.合作竞争博弈中的复杂性与演化均衡的稳[13]吴昊，

（2）：定性分析[J].系统工程理论与实践，200490-94.陆柳，严广东，等.不完全信息条件下演化博弈均衡的稳定[14]孙庆文，

性分析[J].系统工程理论与实践，（7）：200311-16.[15]KobayashiJ.Evolutionarilystablestrategyinmorethantwoplayer

2000，15：209-216.games[J].SociologicalTheoryandMethod，SchusterP，SigmundK.Anoteonevolutionarilystable[16]HofbauerJ，

strategiesandgamedynamics[J].JournalofTheoryBiology，1979，81：609-612.[17]BroomM，CanningsC，VickersGT.Multi-playermatrixgames[J].

BulletinofMathematicalBiology，1997，59：931-952.[18]YazarJ.Evolvingdensitiesincontinuousstrategygamesthrough

particlesimulations[J].JournalofEconomicInteractionandCoor－

（2）：dination，2006，1171-187.

在实验1中，对于forman序列的第一帧，采用APS算法重

建的第二帧，主观上看，视频图像非常接近视频图像的原始帧。在实验2中，通过误差帧的比较，可以看出APS算法比DS算

在实验3中，用3种经典算法产生的误差平均降低了约800；

法与APS算法进行搜索，比较可得改进算法的匹配时间比DS算法减少了40%左右。因此，提出的新算法达到了预期目的，运算简单有效。

5结论

视频对象分割及预测编码是视频压缩中的重要环节，其优

（上接14页）

[4]EllisonG.Basinsofattraction，long-runstochasticstability，andthe

speedofstep-by-stepevolution[J].ReviewofEconomicStudies，2000，67：17-41.

[5]KobayashiJ.Evolutionarilystablestrategyinmorethantwoplayer

games[J].SociologicalTheoryandMethod，2000，15：209-216.[6]OechsslerJ，RiedelF.Evolutionarydynamicsoninfinitestrategy

（1）：2001，17141-162.spaces[J].EconomicTheory，

[7]HofbauerJ，SorgerG.Adifferentialgameapproachtoevolutionary

equilibriumselection[J].InternationalJournalofGameTheoryRe－view，2000，4：17-31.

[8]DominikK，JacekM，MarcinZ.Stochasticstabilityinthree-player

（6）：games[J].BulletinofMathematicalBiology，2005，671195-1205.[9]ClemensC，RichmannT.Evolutionarydynamicsinpublicgood

（4）：2006，28399-420.games[J].ComputationalEconomics，

[10]HeifetzA，ShannonC，SpiegelY.Thedynamicevolutionofprefer－

（2）：ences[J].EconomicTheory，2007，32251-286.