potential

【博弈论】势博弈（potentialgame）、EPG以及最佳响应、Nash均衡和帕累托

（。。。

⽂章⽬录

前⾔

本⽂主要详细讲解potentialgame的概念以及Exactpotentialgame的定义和分类，以及这么博弈⽅法是如何在论⽂中引⼊并使⽤的，本

⽂仅是对⾃⼰在该模块学习的⼀个总结，如果理解有误，还请批评指正，谢谢~

⼀、Potentialgame

Potentialgame即势博弈。在⼀场博弈中，每个⽤户可以做出⾃⼰的策略，并且通过调整策略使⾃⼰的效⽤（utility或者收益payoff）最

⼤，假设这种通过调整策略得到的函数为效⽤函数，即Utilityfunction，且与策略有关，我们写作,其中表⽰第n次出牌的策略。

由于我们建⽴该game的⽬的是让每个⽤户的效⽤最⼤，也就是每个⽤户对⾃⼰策略的改变⼀定的单调的，所以，假设每个⽤户的效⽤函数

的改变都能映射到⼀个势函数（Potentialfunction）中，那么potentialfunction也是单调的，此时将这种博弈称作势博弈。

定义：如果存在⼀个函数,满⾜任意,有

其中，表⽰不同于的策略，⽽表⽰系统中其他⽤户的策略，具体如果要在代码中实现，可以理解为上⼀轮其他所有⽤户的策略集

合，再以此得到⾃⼰本轮的策略。（不确定这样理解是不是对的，如有不对，望指正谢谢~）

⼆、Nash均衡和Pareto-optimal（帕累托最优）

这两种均是得到上述最优策略的⽅法。

均衡

⽤户通过不断改变⾃⼰的策略使⾃⾝的效⽤或收益最⼤，直到所有⽤户都满意，并不再改变策略为⽌，此时即为Nash（纳什）均衡，有：

Nash均衡的存在性和唯⼀性证明：

1.存在性：⾸先⾃变量是空间上⾮空闭合有界凸集，其次是在区间上拟凹或者拟凸的

2.唯⼀性：分为⾮负性、单调性以及可伸缩性

当然Nash均衡也有细分，分为纯策略（pure-strategy）纳什均衡和混合策略（mixed-strategy）纳什均衡，两者分别是纯策略的⽤户最

优结果实现的均衡以及混合策略的⽤户最优结果实现的均衡，其中纯策略使指每个⽤户只做出⼀个策略选择并始终坚持这个策略；⽽⽤户使

选择的策略随机化，并根据不同的重要性对每个策略制定⼀个概率，这种依据概率做出的策略即为混合策略。

最优

上述讲的势博弈以及nash均衡中的最优都是针对⼀个⽤户⽽⾔，⽤户根据⾃⼰的策略选择，使⾃⾝的效益最⼤化；但是pareto最优是使整

体效益最优，谋求的是⼀个集体利益或者说社会福利最⼤化，因此pareto最优是指对每⼀个和效⽤最⼤的策略组合。

如果将囚徒困境的例⼦引⼊，

f(s)nsn

f(s)n

p:S→Rn∈N

U(s,s)−nn

′

−nU(s,s)=nn

−np(s,s)−n

′

−np(s,s)n

−n

sn

′

sns−n

U(s,s)≥nn

∗

−n

∗

U(s,s)nn

−n

∗

snU(s,s)nn

−n

假设有两个⼩偷A和B联合犯事、私⼊民宅被警察抓住。警⽅将两⼈分别置于不同的两个房间内进⾏审讯，对每⼀个犯罪嫌疑⼈，警⽅给出

的政策是：

1.如果⼀个犯罪嫌疑⼈坦⽩了罪⾏，交出了赃物，于是证据确凿，两⼈都被判有罪。如果另⼀个犯罪嫌疑⼈也作了坦⽩，则两⼈各被判

刑8年。

2.如果另⼀个犯罪嫌⼈没有坦⽩⽽是抵赖，则以妨碍公务罪（因已有证据表明其有罪）再加刑2年，共10年，⽽坦⽩者有功被减刑8年，

⽴即释放，即0年。

3.如果两⼈都抵赖，则警⽅因证据不⾜不能判两⼈的偷窃罪，但可以私⼊民宅的罪名将两⼈各判⼊狱1年。

两⼈的选择见下表：表中的数字表⽰A，B各⾃的判刑结果：

如上所⽰，当两者都坦⽩时，是对⾃⼰最好的结果，此时针对Nash均衡点即为（-8，-8）的点，但是如果针对pareto最优，就是两者都抵

赖的为该最优点，即（-1，-1）。

三、Bestrespon（最佳响应）

基于上述Potentialgame的定义，当通过调整策略使效⽤最⼤的点即为最优策略，下式即为最佳响应公式：

四、Exactpotentialgame(EPG)

针对上述Potentialgame的定义：

如果存在⼀个函数,满⾜任意,有

如果处处可微，则严格势博弈（EPG）的充分条件为：

可以理解为严格势博弈是势博弈的⼀种，并且当满⾜上式时，为严格势博弈，因此严格势博弈也⼀样满⾜效⽤函数之差等于势函数之差。同

时严格势博弈主要分为以下5中博弈：

以下参考《博弈论》书籍，具体哪个作者忘记了

1.合作-傀儡博弈

如果博弈的所有参与者的效⽤函数可以⽤表⽰，其中与n⽆关，则其势函数为：

定义了⼀个合作函数，所有博弈参与者对于具有的策略s都会得到相应的回报，定义了⼀个傀儡函数，参与者n的结构不依赖

于⾃⾝的策略，⽽是依赖于其他参与者的策略

由于满⾜：,故C(s)为该博弈的势函数。

2.合作博弈

即只有合作函数，因此上述，即

3.傀儡博弈

即只有傀儡函数，，，此时傀儡博弈的势函数都是⼀个常函数。

4.⾃激博弈

如果所有的博弈者都有如下的效⽤函数，那么这种类型的博弈就叫做⾃激博弈：

s=n

∗

U(s,s)s

n

argmax

nn

−n

p:S→Rn∈N

U(s,s)−nn

′

−nU(s,s)=nn

−np(s,s)−n

′

−np(s,s)n

−n

Un

=∂s∂si

j

∂U(s)2

i,i,j∈∂s∂sj

i

∂U(s)2

j

N

U(s)=nC(s)+D(s)n

−nC(s)p=C(s)

C(s)D(s)n

−n

U(s,s)−nn

′

−nU(s,s)=nn

−nC(s,s)−n

′

−nC(s,s)n

−n

D(s)=n

−n0U(s)=nC(s)

U(s)=nD(s)n

−nC(s)=0

其中,由于博弈被定义为⼀种相互影响的决策过程，⽽⾃激博弈确是没有相互影响的交互过程，因此严格上说不算是博弈，其

势函数为：

5.双边对称交互博弈

如果每个博弈的参与者的效⽤函数都可以表达如下的形式：

其中为双边交互函数，为⾃利函数，如果对于所有,有,那么这种博弈称为双边对称博

弈，其势函数为：

其中第⼀项是交互部分，后⼀项是仅关于i的部分。

使⽤理解

⾸先要证明建⽴的游戏理论模型符合势博弈的定义，其次要证明存在Nash均衡点，并根据不断调整策略（迭代的过程）利⽤最佳响应得到

Nash均衡点（即最优策略）以及最⼤的效⽤。其中势函数的建⽴过程可以证明是否符合EPG，并根据具体的博弈模型建⽴势函数，也可以

直接⾃⼰找到具体的对应关系。

U(s)=nK(s)nn

K:ns→nR

P=K(s)n∈N

∑

nn

U(s)=iwj(s,s)−j∈N

∑

i,j

i

jK(s)ii

wi,jKi(s,s)∈i

jS×iSjw(s,s)=i,j

i

jw(s,s)i,jj

i

p(s)=(wj(s,s)−i∈N

∑

j=1

∑

i−1

i,j

i

jK(s))ii