Two Standard Representations 两种标准表达方式
Normal Form:分别定义Players、Actions、Payoffs。
Extensive Form:扩展定义Timing、Information。
简单的博弈论问题可以使用矩阵表达,如1-1所示。
复杂问题无法用矩阵表达,如经典的造反问题。共有10000000个人,每个人可以选择造反或者不造反,只有达到2000000个人才算造反成功。如果造反达到人数要求,无论决策者选择什么收益都是1;如果造反没有达到人数要求,则决策者选择造反的收益是-1;如果造反没有达到人数要求,则决策者选择不造反的收益是0。
Players: N = { 1 , . . . , 10 , 000 , 000 } N=\{1,…,10,000,000\} N={
1,...,10,000,000}
Actions Set for player i i i: A i = { R e v o l t , N o t } A_i=\{Revolt,Not\} Ai={
Revolt,Not}
Utility Function for player i i i:
(1) u i ( a i ) = 1 i f { j : a j = R e v o l t } > = 2 , 000 , 000 u_i(a_i)=1 \space if \{j:a_j=Revolt\}>=2,000,000 ui(ai)=1 if{
j:aj=Revolt}>=2,000,000
(2) u i ( a i ) = − 1 i f { j : a j = R e v o l t } < 2 , 000 , 000 a n d a i = R e v o l t u_i(a_i)=-1 \space if \{j:a_j=Revolt\}<2,000,000 \space and \space a_i=Revolt ui(ai)=−1 if{
j:aj=Revolt}<2,000,000 and ai=Revolt
(3) u i ( a i ) = − 0 i f { j : a j = R e v o l t } < 2 , 000 , 000 a n d a i = N o t u_i(a_i)=-0 \space if \{j:a_j=Revolt\}<2,000,000 \space and \space a_i=Not ui(ai)=−0 if{
j:aj=Revolt}<2,000,000 and ai=Not
Game of Pure Competition 纯竞争博弈
博弈的双方具有完全对立的利益。
对于双方任意动作组合,其效用之和永远为一个常数。 ∀ a ∈ A , u 1 ( a ) + u 2 ( a ) = c \forall \space a \in A,u_1(a)+u_2(a)=c ∀ a∈A,u1(a)+u2(a)=c
特殊类型:零和博弈。双方效用之和永远为0。
举例说明:石头剪刀布游戏。
Games of Cooperation 合作博弈
博弈的多方具有相同的利益,利益之间不存在冲突。 ∀ a ∈ A , ∀ i , j , u i ( a ) = u j ( a ) \forall a\in A,\forall i,j,u_i(a)=u_j(a) ∀a∈A,∀i,j,ui(a)=uj(a)
举例说明:过马路问题。马路两头两个人想同时通行,每个人可以选择靠左或者靠右行驶。
Best Response 最优响应
如果知道其他所有人的动作,那么挑选对于自己最有利的动作就变得十分简单。
a i 表 示 第 i 个 决 策 者 所 做 出 的 决 策 a_i表示第i个决策者所做出的决策 ai表示第i个决策者所做出的决策
a − i = { a 1 , . . . , a i − 1 , a i + 1 , . . . , a n } 表 示 除 去 a i 以 外 其 他 人 的 决 策 a_{-i}=\{a_1,…,a_{i-1},a_{i+1},…,a_n\}表示除去a_i以外其他人的决策 a−i={
a1,...,ai−1,ai+1,...,an}表示除去ai以外其他人的决策
a = ( a i , a − i ) a=(a_i,a_{-i}) a=(ai,a−i)
a i ∗ ∈ B R ( a − i ) i f f ∀ a i ∈ A i , u i ( a i ∗ , a − i ) > = u i ( a i , a − i ) a_i^*\in BR(a_{-i})\space iff \forall a_i\in A_i,u_i(a_i^*,a_{-i})>=u_i(a_i,a_{-i}) ai∗∈BR(a−i) iff∀ai∈Ai,ui(ai∗,a−i)>=ui(ai,a−i)
其中 B R ( a − i ) BR(a_{-i}) BR(a−i)表示已知其他决策信息后第i个决策者做出的最优响应,最优响应不一定只有一个。并且最优相应集合中的所有元素 a i ∗ a_i^* ai∗都满足下列要求,当且仅当选择 a i ∗ a_i^* ai∗的效用大于等于选择其他所有响应的效用。
Pure Strategy Nash Equilibrium 纯策略纳什均衡
实际上我们并不知道其他人会做出何种决策,因此根据他人决策制定自己的最优响应是不现实的。
a = { a 1 , . . . , a n } i s a p u r e s t r a t e g y N a s h e q u i l i b r i u m i f f ∀ i , a i ∈ B R ( a − i ) a=\{a_1,…,a_n\}is \space a \space pure \space strategy \space Nash \space equilibrium \space iff \space \forall i,a_i\in BR(a_{-i}) a={
a1,...,an}is a pure strategy Nash equilibrium iff ∀i,ai∈BR(a−i)
1-8 Nash Equilibrium of Example Games
纳什均衡的定义
给定其他决策者的决策,每个决策者都没有单独改变决策的动机。(也就是当前决策是最优决策)
假设一共有A、B、C三个决策者,已知A、B决策下C做出最优决策 c ∗ c^* c∗,已知A、C决策下B做出最优决策 b ∗ b^* b∗,已知B、C决策下A做出最优决策 a ∗ a^* a∗,那么 ( a ∗ , b ∗ , c ∗ ) (a^*,b^*,c^*) (a∗,b∗,c∗)就是一个纳什均衡点。
Strictly\Very Weakly Dominates 决策优势、劣势关系
s i s t r i c t l y d o m i n t a t e s s i ′ i f ∀ s − i ∈ S − i , u i ( s i , s − i ) > u i ( s i ′ , s − i ) s_i \space strictly \space domintates \space s_i^{‘} \space if \forall s_{-i}\in S_{-i},u_i(s_i,s_{-i})>u_i(s_i^{‘},s_{-i}) si strictly domintates si′ if∀s−i∈S−i,ui(si,s−i)>ui(si′,s−i)
s i v e r y w e a k l y d o m i n t a t e s s i ′ i f ∀ s − i ∈ S − i , u i ( s i , s − i ) > = u i ( s i ′ , s − i ) s_i \space very \space weakly \space domintates \space s_i^{‘} \space if \forall s_{-i}\in S_{-i},u_i(s_i,s_{-i})>=u_i(s_i^{‘},s_{-i}) si very weakly domintates si′ if∀s−i∈S−i,ui(si,s−i)>=ui(si′,s−i)
严格压制关系与轻微压制关系的区别就在于取不取等号。以 s i s_i si严格压制决策 s i ′ s_i^{‘} si′为例,是指无论其他决策者制定什么决策,当前决策者选择 s i s_i si的效用一定严格优于选择 s i ′ s_i^{‘} si′。
之前对于决策的选择以及评估都是站在每个决策者的角度,现在我们跳出决策者的身份,以一个外界观察者的角度来评估决策。我们只考虑最直接的一种评估方式,如果决策组合 O O O对于所有决策者的效用都优于决策 O ′ O^{‘} O′,那么我们称 O P a r e t o − d o m i n a t e s O ′ O \space Pareto-dominates \space O^{‘} O Pareto−dominates O′。
比如说 O ( 7 , 8 ) 、 O ′ ( 4 , 5 ) , 那 么 我 们 可 得 O P a r e t o − d o m i n a t e s O ′ O(7,8)、O^{‘}(4,5),那么我们可得O \space Pareto-dominates \space O^{‘} O(7,8)、O′(4,5),那么我们可得O Pareto−dominates O′。
Pareto-Optimal 帕累托最优
一个决策组合 O ∗ O^* O∗,如果没有其他任何一个决策组合帕累托压制 O ∗ O^* O∗,那么称该决策组合是帕累托最优。
帕累托最优定义的并不是压制别人的能力,而是不被其他人压制。
一场游戏中可能有多个帕累托最优决策组合。
一场游戏中最少含有一个帕累托最优决策组合。
区分定义:在纯策略中每个决策者每一步决定的是一个动作 a i a_i ai;在混合策略中每个决策者每一步决定的是一个策略 s i s_i si,策略包含多个动作及对应概率。针对第 i i i个决策者所有策略的组合为 S i = { s 1 , . . . , s n } S_i=\{s_1,…,s_n\} Si={
s1,...,sn},针对所有决策者的策略组合为各个决策者的策略笛卡尔积 S = S 1 × . . . × S n S=S_1\times …\times S_n S=S1×...×Sn。
在纯策略中我们针对每个决策者的不同动作衡量效用,在混合策略中我们针对每个决策者的不同策略概率分布来衡量效用,换句话说计算效用期望。
u i ( s ) = ∑ a ∈ A u i ( a ) P r ( a ∣ s ) , P r ( a ∣ s ) = ∏ j ∈ N s j ( a j ) u_i(s)=\sum_{a\in A}u_i(a)Pr(a|s),Pr(a|s)=\prod_{j\in N}s_j(a_j) ui(s)=∑a∈Aui(a)Pr(a∣s),Pr(a∣s)=∏j∈Nsj(aj)
混合策略中的最优响应以及纳什均衡
只需要将之前的 a i a_i ai全部替换成 s i s_i si即可。
s i ∗ ∈ B R ( s − i ) i f f ∀ s i ∈ S i , u i ( s i ∗ , s − i ) > = u i ( s i , s − i ) s_i^*\in BR(s_{-i})\space iff \forall s_i\in S_i,u_i(s_i^*,s_{-i})>=u_i(s_i,s_{-i}) si∗∈BR(s−i) iff∀si∈Si,ui(si∗,s−i)>=ui(si,s−i)
s = { s 1 , . . . , s n } i s a N a s h e q u i l i b r i u m i f f ∀ i , s i ∈ B R ( s − i ) s=\{s_1,…,s_n\}is \space a \space Nash \space equilibrium \space iff \space \forall i,s_i\in BR(s_{-i}) s={
s1,...,sn}is a Nash equilibrium iff ∀i,si∈BR(s−i)
Strictly Dominated Strategies 严格占优策略A strategy a i ∈ A i a_i\in A_i ai∈Aiis strictly dominated by a i ′ ∈ A i a_i^{‘}\in A_i ai′∈Aiif u i ( a i , a − i ) < u i ( a i ′ , a − i ) ∀ a − i ∈ A − i u_i(a_i,a_{-i})<u_i(a_i^{‘},a_{-i})\forall a_{-i}\in A_{-i} ui(ai,a−i)<ui(ai′,a−i)∀a−i∈A−i.
简单来说,无论其他决策者作何决策,第 i i i个决策者选择 a i a_i ai的收益都要大于选择 a i ′ a_i^{‘} ai′。
弱占优策略
相较于严格占优策略,弱占优策略的条件相对宽松了一些。严格占优策略要求针对所有的其他决策者决策,第 i i i个决策者选择 a i a_i ai的收益都要优于 a i ′ a_i^{‘} ai′的收益。弱占优决策是指,针对所有的其他决策者决策,第 i i i个决策者选择 a i a_i ai的收益都要大于等于 a i ′ a_i^{‘} ai′的收益,并且对于部分其他决策者的决策情况,第 i i i个决策者选择 a i a_i ai的收益都要优于 a i ′ a_i^{‘} ai′的收益。总结来说弱占优策略部分满足严格占优策略的要求。
弱占优策略同样可以用于迭代消除,但是迭代消除的顺序对结果有影响,至少一个纳什均衡点被保留。
Maxmin Strategies 最大最小策略
决策者 i i i的最大最小策略是指,决策者选定一个策略 s i s_i si使得最大化自己的最坏情况下的收益。我们设想当其他决策者的决策对决策者 i i i的收益造成最大损害时,此时的收益我们称之为最坏情况下的收益。因此决策者 i i i的最大最小策略,可以说是在最困难的外界坏境中尽可能地拯救自己。
The maxmin strategy for player i i i is a r g m a x s i m i n s − i u i ( s i , s − i ) arg \space max_{s_i}min_{s_{-i}}u_i(s_i,s_{-i}) arg maxsimins−iui(si,s−i)
The maxmin value for player i i i is m a x s i m i n s − i u i ( s i , s − i ) max_{s_i}min_{s_{-i}}u_i(s_i,s_{-i}) maxsimins−iui(si,s−i)
Minmax Strategies 最小最大策略
决策者 i i i地最小最大策略是指,为了对抗(坑害)其他决策者,决策者 i i i选定一个策略 s i s_i si使得最小化其他决策者的最大收益**。也就是说,我们设想其他决策者已经选定策略最大化自己的收益,而决策者 i i i要尽可能最小化他们的最大收益。可以说是在别人最好的情况下拉他们下水。
In a two-player game,the minmax strategy for player i i i against player − i -i −i is a r g m i n s − i m a x s i u i ( s i , s − i ) arg \space min_{s_{-i}}max_{s_i}u_i(s_i,s_{-i}) arg mins−imaxsiui(si,s−i)
The minmax value for player i i i is m i n s − i m a x s i u i ( s i , s − i ) min_{s_{-i}}max_{s_i}u_i(s_i,s_{-i}) mins−imaxsiui(si,s−i)
Minmax Theorem 最小最大理论
在任意一个有限的、两个玩家对立的、零和博弈的游戏中,在任何一个纳什均衡点中,两个玩家获得的收益都同时等于其maxmin value 和minmax value。
使用LP线性规划的方法求解minmax问题
上一部分中我们了解到,当实现minmax value或者maxmin value时,此时处于纳什均衡。那么就给我们提供了另外一种纳什均衡求解的方法。
这里我们使用minmax思路来求解,以player 2 的角度,我们在满足限制条件下最小化player 1的最优收益。
m i n i m i z e U 1 ∗ ( 1 ) s u b j e c t t o ∑ k ∈ A 2 u 1 ( a 1 j , a 2 k ) × s 2 k < = U 1 ∗ ∀ j ∈ A 1 ( 2 ) ∑ k ∈ A 2 s 2 k = 1 , s 2 k > = 0 ∀ k ∈ A 2 ( 3 ) \begin{aligned} minimize \space U_1^{*}(1) \\ subject \space to \space \sum_{k\in A_2}u_1(a_1^j,a_2^k)\times s_2^k<=U_1^*\space\space\space\space \forall j\in A_1 (2)\\ \sum_{k\in A_2}s_2^k=1,s_2^k>=0\space\space\space \forall k \in A_2(3) \end{aligned} minimize U1∗(1)subject to k∈A2∑u1(a1j,a2k)×s2k<=U1∗ ∀j∈A1(2)k∈A2∑s2k=1,s2k>=0 ∀k∈A2(3)
给定一个博弈和它的一个相关均衡 p p p,由于 p p p 本质上是一个相关系数, p p p给每个参与人推荐行动的过程可以理解成一个不完全信息的生成过程:每个参与人接收到自己的信息(行动推荐),同时产生了对他人信息(行动推荐)的概率估计。从而计算发现服从行动推荐对他自己来说是最优的选择。
4-1 Perfect Information Extensive Form:Taste
以两个传说故事引出完美信息拓展形式。
4-2 Formalizing Perfect Information Extensive Form Games
本节介绍完美信息拓展形式的形式化表述。
之前学习中我们使用的都是一般形式,一般形式并没有体现任何序列信息,比如说时间序列信息,或者是决策者的动作序列信息。拓展形式就可以让时间结构信息表述精确完整,拓展形式分为两种:perfect information extensive-form games 完美信息拓展形式、imperfect-information extensive-form games 不完美信息拓展形式。
一个有限的完美信息博弈游戏(拓展形式)被定义如下元组 ( N , A , H , Z , χ , ρ , σ , u ) (N,A,H,Z,\chi, \rho,\sigma,u) (N,A,H,Z,χ,ρ,σ,u)
Players: N N N。N个决策者(游戏玩家)的集合。
Actions: A A A。动作集合。
Choice nodes: H H H。选择节点,非终结节点的集合。
Action function: χ : H → 2 A \chi :H\rightarrow 2^A χ:H→2A。为每一个选择节点指派可能的动作集合。
Player function: ρ : H → N \rho:H\rightarrow N ρ:H→N。为每一个选择节点 h h h指派一个选择动作的决策者 i i i。
Terminal nodes: Z Z Z。终结节点的集合。
Successor function: σ : H × A → H ∪ Z \sigma:H\times A\rightarrow H\cup Z σ:H×A→H∪Z。后继函数,表示某个选择节点选择某一动作后状态转换到另一个选择节点或者是终结节点。
Utility function: u = ( u 1 , . . . , u n ) ; u i : Z → R u=(u_1,…,u_n);u_i:Z\rightarrow R u=(u1,...,un);ui:Z→R。效用函数,在每个终结节点上放置一个元组,表示每个决策者的最终收益。
4-3 Perfect Information Extensive Form:Strategies,BR,NE
Let G = ( N , A , H , Z , χ , ρ , σ , u ) G=(N,A,H,Z,\chi,\rho,\sigma,u) G=(N,A,H,Z,χ,ρ,σ,u)be a perfect-information extensive-form game.Then the pure strategies pf player i i i consist for the cross product ∏ h ∈ H , ρ ( h ) = i χ ( h ) \prod_{h\in H,\rho(h)=i}\chi^{(h)} ∏h∈H,ρ(h)=iχ(h)
该定义的中文解释:针对于完美信息拓展形式定义下的纯策略,针对决策者 i i i来说, h ∈ H , ρ ( h ) = i h\in H,\rho(h)=i h∈H,ρ(h)=i是其对应的选择节点, χ ( h ) \chi^{(h)} χ(h)是该选择节点对应的选择可能。因此纯策略是一个集合,集合的结果是所有选择节点对应选择分支的笛卡尔积。
上图中,决策者1的纯策略集合为: S 1 = { ( B , G ) ; ( B , H ) ; ( A , G ) ; ( A , H ) } S_1=\{(B,G);(B,H);(A,G);(A,H)\} S1={
(B,G);(B,H);(A,G);(A,H)}、决策者2的纯策略集合为 S 2 = { ( C , E ) ; ( C , F ) ; ( D , E ) ; ( D , F ) } S_2=\{(C,E);(C,F);(D,E);(D,F)\} S2={
(C,E);(C,F);(D,E);(D,F)}。
我们该如何由拓展形式化为一般形式的矩阵表述呢? S 1 、 S 2 S_1、S_2 S1、S2纯策略分别作为矩阵的横轴与纵轴,接下来我们只需要对应寻找收益元组即可。举个例子,AG与CE组合,我们在左图中标出A、G、C、E,然后发现从起点到叶子节点只有一条通路,对应的叶子节点就是该纯策略组合的收益。
完美信息拓展形式中的纯策略纳什均衡(PSNE)
理论:每一个拓展形式表达的完美信息博弈游戏中,都至少有一个纯策略纳什均衡(PSNE)。
上图中有三个纯策略纳什均衡,分别是 ( A , G ) , ( C , E ) ; ( A , H ) , ( C , F ) ; ( B , H ) , ( C , E ) (A,G),(C,E);(A,H),(C,F);(B,H),(C,E) (A,G),(C,E);(A,H),(C,F);(B,H),(C,E)。我们回到收益矩阵中分析,以上三个纯策略纳什均衡点左侧收益是列中的最大值,右侧收益是行中的最大值。
4-4 Subgame Perfection
上一章节中我们得到了三个纯策略纳什均衡,但并不是所有的纳什均衡都是可信的或者说是合理的。比如说纳什均衡 ( B , H ) , ( C , E ) (B,H),(C,E) (B,H),(C,E),虽然满足纳什均衡的定义,任一决策者单独改变决策都不会获得更优的收益。但是我们看决策者1在第二个选择节点,明显选择G这条路是严格压制选择H的,因此如果我们单独考虑该博弈,决策者1绝对会选择G而不是H。
如何判断一个子博弈是否均衡?在选择节点 h h h对应的子博弈中,决策者为 i i i。我们判断决策者 i i i的决策是否是针对自己的最优响应,如果是的话那么就是子博弈均衡。只有所有子博弈层层均衡的才最终判定为一个合理的纳什均衡。
对于均衡 ( A , G ) , ( C , F ) (A,G),(C,F) (A,G),(C,F):符合子博弈完美。
对于均衡 ( B , H ) , ( C , E ) (B,H),(C,E) (B,H),(C,E):决策者1的第二个选择节点就不符合子博弈均衡。
对于均衡 ( A , H ) , ( C , F ) (A,H),(C,F) (A,H),(C,F):决策者1的第二个选择节点就不符合子博弈均衡。
算法输入:某个节点 h h h(选择节点或者是叶子节点)
算法输出:该节点满足子博弈完美的所有决策者收益,递归中每一步的最优决策选择都是针对于选择节点 h h h所对应的决策者 ρ ( h ) \rho(h) ρ(h)而言。
注意:变量 b e s t _ u t i l 、 u t i l _ a t _ c h i l d best\_util、util\_at\_child best_util、util_at_child都是向量,代表了所有决策者的收益
该算法非常简单,其实就是递归思想,自上而下搜索子博弈完美的均衡。
该过程并不返回均衡策略,但是给每个节点用收益向量打上标签。之前只有终结节点有对应的收益向量,该打标签的过程可以看作是将终结节点上的收益向量拓展到选择节点上。
一个不完美信息博弈游戏的拓展形式由以下元组表示 ( N , A , H , Z , χ , ρ , σ , u , I ) (N,A,H,Z,\chi,\rho,\sigma,u,I) (N,A,H,Z,χ,ρ,σ,u,I),该元组是在完美信息拓展形式表示元组 ( N , A , H , Z , χ , ρ , σ , u ) (N,A,H,Z,\chi,\rho,\sigma,u) (N,A,H,Z,χ,ρ,σ,u)的基础上添加了决策等价类的集合 I I I。
其中 I = ( I 1 , . . . , I n ) I=(I_1,…,I_n) I=(I1,...,In),并且 I i = ( I i 1 , . . . , I i k i ) I_i=(I_{i1},…,I_{ik_i}) Ii=(Ii1,...,Iiki)。解释一下含义: I i I_i Ii表示决策者 i i i的等价类的集合; I i 1 I_{i1} Ii1表示决策者 i i i的第一个决策等价类,该等价类可能包含一到多个单一决策,但是等价类内部不可分辨。同一等价类内部的决策要求满足,针对同一决策者,拥有相同的动作选择集合。
我们来举一个属于行为决策的例子:A在第一次决策时有0.5的概率选择A;在第二次决策时有0.3的概率选择G,这样就构成了决策者A的一个行为决策。
我们再来举一个属于混合策略的例子:A的纯策略为 { ( A , G ) , ( A , H ) , ( B , G ) , ( B , H ) } \{(A,G),(A,H),(B,G),(B,H)\} {
(A,G),(A,H),(B,G),(B,H)},A的纯策略分布为 { 0.6 ( A , G ) , 0.4 ( B , H ) } \{0.6(A,G),0.4(B,H)\} {
0.6(A,G),0.4(B,H)}。
并且在这场游戏中,每一个行为策略都可以转化成一个混合策略(只需要根据分步概率分布计算出纯策略的概率分布即可)。
不完美信息博弈中的混合策略和行为策略
由图中虚线得知,决策者1只有一个决策等价类,该等价类包含两个选择节点,两个选择节点隶属于同一决策者并有相同的可选动作集。可以理解为决策者1同时发送了两个代理,一个代理构成一个选择节点,两个代理节点不知彼此谁先到达,拥有相同的可选动作集对于下一步来说是不可分辨的。
决策者1的纯策略为 { L , R } \{L,R\} {
L,R};决策者2的纯策略为 { U , D } \{U,D\} {
U,D}。
那么本博弈游戏中的混合策略均衡是什么呢?针对于决策者2,选择D对于选择U来说是占优的,因此决策者2一定会选择D而不是U。在基于决策者2选择D的前提下,决策者1选择L收益为1,决策者1选择R收益为2,因此最终的均衡点为 ( R , D ) (R,D) (R,D)。
那么本博弈游戏中的行为策略均衡是什么呢?针对决策者2来说,D还是相对于G占优的,因此我们设置决策者2选择 ( U , D ) (U,D) (U,D)的概率分布为 ( 0 , 1 ) (0,1) (0,1)。针对于决策者1,我们设置选择 ( L , R ) (L,R) (L,R)的概率分布为 ( p , 1 − p ) (p,1-p) (p,1−p),那么决策者1的收益为:
p 2 + 100 p ( 1 − p ) + 2 ( 1 − p ) = − 99 p 2 + 98 p + 2 p^2+100p(1-p)+2(1-p)=-99p^2+98p+2 p2+100p(1−p)+2(1−p)=−99p2+98p+2,极大值位于 p = 98 / 198 p=98/198 p=98/198
那么行为策略均衡为 ( L , R ) , ( U , D ) = ( 98 / 198 , 100 / 198 ) , ( 0 , 1 ) (L,R),(U,D)=(98/198,100/198),(0,1) (L,R),(U,D)=(98/198,100/198),(0,1)
可以看出针对于同一场博弈游戏,选择行为策略还是混合策略,所达到的均衡可能是不同的。
4-10 Incomplete Information in the Extensive Form:Beyond Subgame Perfection
Give an infinite sequence of payoffs r 1 , r 2 , . . . r_1,r_2,… r1,r2,...for player i i i,the average reward of i i i is
lim k → ∞ ∑ j = 1 k r j k \lim_{k \to \infty} \sum_{j=1}^k \frac{r_j}{k} limk→∞∑j=1kkrj。
观察上式可得,每次博弈的收益都会除以一个比例 k k k加入到总和中。随着博弈次数 k k k的增加,该次博弈的收益在收益总和中所占的比例越来越小。表明了,无线重复博弈更看重近次博弈,忽视远视博弈。
Future Discounted Reward 未来折扣收益
Give an infinite sequence of payoffs r 1 , r 2 , . . . r_1,r_2,… r1,r2,...for player i i i and discount factor β \beta β with 0 < β < 1 0<\beta <1 0<β<1,the future discounted reward of i i i is
∑ j = 1 ∞ β j r j \sum_{j=1}^\infty \beta^jr_j ∑j=1∞βjrj。
针对该效用定义有两种理解方式。第一种理解,每次博弈所获得的效用都要乘以 β j \beta^j βj衰减,也就表明该游戏更看重近次博弈忽视远次博弈。第二种理解,代理者针对近次、远次博弈同样看重,不分轻重,只不过每次博弈游戏都有 β \beta β的概率延续到下一次,有 1 − β 1-\beta 1−β的概率终结于此。
5-3 Stochastic Games
本章节我们来学习一下Stochastic Games 随机博弈。随机博弈是指多个参与者参与的无线博弈,只不过并不是每次重复博弈,而是每次产生一个新的博弈状态。根据当前决策者状态以及选择的动作,决定下一阶段的博弈状态。
图示理解重复博弈与随机博弈。
重复博弈是重复进行相同的博弈游戏,而随机博弈是在多个博弈游戏之间切换。
随机博弈的形式化定义
A stochastic game is a tuple( Q , N , A , P , R Q,N,A,P,R Q,N,A,P,R),where
Q Q Q is a finite set of states,有限的状态集
N N N is a finite set of n n n players,有限的决策者集合
A = A 1 × . . . × A n A=A_1\times…\times A_n A=A1×...×An,where A i A_i Ai is a finite set of actions available to player i i i,每个决策者的可能行动有限集合
P : Q × A × Q → [ 0 , 1 ] P:Q\times A \times Q \to [0,1] P:Q×A×Q→[0,1]is the transition probability function; P ( q , a , q ′ ) P(q,a,q^{‘} ) P(q,a,q′)is the probability of transitioning from state q q q to state q ′ q^{‘} q′after joint action a a a,and状态迁移概率
R = r 1 , . . . , r n R=r_1,…,r_n R=r1,...,rn,where r i : Q × A → R r_i:Q\times A\to R ri:Q×A→R is a real-valued payoff function for player i i i.决策者决策收益
类比于上一章节的无限重复博弈,我们也可以定义随机博弈中的limit average reward 极限平均收益与future discount reward 未来折扣收益。
5-4 Learning in Repeated Games
本章节会介绍重复博弈中的两种学习形式,一种是Fictitious Play 虚拟博弈,另一种是No-regret Learning 无后悔学习。总体来说,博弈论中的学习是一个涵盖广泛的课题。博弈论中的“学习”与机器学习、深度学习中的“学习”有本质的不同。
Fictitious Play 虚拟博弈
虚拟博弈方法最初提出是为了计算纳什均衡的。虚拟的意思是指我们并不实际进行多次重复博弈的过程,而是根据策略去模拟,通过模拟计算纳什均衡。大体思路如下:每个决策者针对其他对手的策略分布都生成一个信念,虚拟博弈的每次迭代过程都根据当前信念选择自己的最优响应,然后根据其他对手的决策情况,动态更新策略分布,最后该算法会收敛于纳什均衡。
The regret an agent experiences at time t t t for not having played s s s is R t ( s ) = α t ( s ) − α t R^t(s)=\alpha^t(s)-\alpha^t Rt(s)=αt(s)−αt.
某个决策者在时间点 t t t未选择策略 s s s的后悔程度是,在时间点 t t t假设选择策略 s s s的收益减去实际的收益。
A learning rule exhibits no regret if for any pure strategy of the agent s s s it holds that P r ( [ l i m i n f R t ( s ) < = 0 ] ) = 1 Pr([lim \space infR^t(s)<=0])=1 Pr([lim infRt(s)<=0])=1
用中文解释来说就是,在时间点 t t t选择策略 s s s的后悔程度小于等于0的概率上极限为1。
具体的迭代学习方法是:
σ i t + 1 ( s ) = R t ( s ) ∑ s ′ ∈ S i R t ( s ′ ) \sigma_i^{t+1}(s)=\frac{R^t(s)}{\sum_{s^{‘}\in S_i}R^t(s^{‘})} σit+1(s)=∑s′∈SiRt(s′)Rt(s),每次迭代根据本轮不同决策选择后悔程度占总体的比例来调整下一次策略选择的概率分布。
Consider any n-player game G = ( N , A , u ) G=(N,A,u) G=(N,A,u) and any payoff vector r = ( r 1 , r 2 , . . , r n ) r=(r_1,r_2,..,r_n) r=(r1,r2,..,rn)在这里的 r i r_i ri我们采用的是平均收益算法(详情请见上文)
Let v i = m i n s − i ∈ S − i m a x s i ∈ S i u i ( s − i , s i ) v_i=min_{s_{-i}\in S_{-i}}max_{s_i\in S_i}u_i(s_{-i},s_i) vi=mins−i∈S−imaxsi∈Siui(s−i,si)。 v i v_i vi是 i i i的minmax值,具体是指其他决策者都尽可能损害 i i i的利益时, i i i采取决策最大化自己的利益所能获得的利益。
A payoff profile r r r is enforceable if r i > = v i r_i>=v_i ri>=vi。如果每一位决策者的实际收益都大于其minmax值,那么我们称之为enforceable。
A payoff profile r r r is feasible if there exist rational,non-negative values α a \alpha_a αasuch that for all i i i,we can express r i r_i ri as ∑ a ∈ A α a u i ( a ) \sum_{a\in A}\alpha_au_i(a) ∑a∈Aαaui(a),with ∑ a ∈ A α a = 1 \sum_{a\in A}\alpha_a=1 ∑a∈Aαa=1。如果某种收益数值可以表示为所有可能决策收益的加权和,那么我们称之为feasible。
无名氏定理 Folk Theorem
为什么叫Folk Theorem?就像是Folk Song民歌一样,大家广为流传但是不知道具体的出处。Folk Theorem大家都普遍认可但是不知道这条定理的来源。
1.如果收益向量 r r r是某个无限重复博弈 G G G中某个纳什均衡的收益(用平均收益算法表示),那么针对每个决策者 i i i, r i r_i ri都是enforceable的。
2.如果收益向量 r r r既是feasible又是enforceable的,那么 r r r一定是某个无限重复博弈 G G G中某个纳什均衡的收益(用平均收益算法表示)。
Payoff in Nash → \to → enforceable
证明:我们假设某个纳什均衡的收益向量不是enforceable,存在某个决策者 i i i, r i < v i r_i<v_i ri<vi。那么根据minmax策略,决策者 i i i可以选择最佳策略将自己的收益提高到至少 v i v_i vi,这样就违背了纳什均衡的概念,存在了一种决策偏离方式使得决策者可以获得更大收益。
Feasible and enforceable → \to → Nash
证明:总结来说就是如果收益向量 r r r既是feasible的又是enforceable的,那么无限次数重复博弈下,都会发现合作才是最优的决策方式,因此符合了纳什均衡的定义。也就是说,虽然短期来看背叛可能会获得更高的收益,但是考虑到背叛之后的惩罚以及博弈游戏是无限性质的,最终还是选择合作会带来最高的收益。因此对于长远来看,选择合作才是符合纳什均衡的。
Stage game: ( N , A , u ) (N,A,u) (N,A,u)
Discount factors: β 1 , . . . , β n , β i ∈ [ 0 , 1 ] \beta_1,…,\beta_n,\beta_i\in[0,1] β1,...,βn,βi∈[0,1](下标代表的是决策者的编号,我们这里考虑每个决策者的折扣因子都是固定的)
Payoff from a play of actions a 1 , . . . , a t , . . . : ∑ t β i t u i ( a t ) a^1,…,a^t,…:\sum_t \beta_i^tu_i(a^t) a1,...,at,...:∑tβitui(at)(下标代表决策者编号, β i t \beta_i^t βit代表第i个决策者第t个阶段折扣因子为t次方, a t a^t at代表第t个阶段采取的动作)
所谓历史,就是所有决策者在各个博弈阶段所作出的决策记录。
Histories of length t t t: H t = { h t : h t = ( a 1 , . . . , a t ) ∈ A t } H^t=\{h^t:h^t=(a^1,…,a^t)\in A^t\} Ht={
ht:ht=(a1,...,at)∈At}
All finite histories: H = ∪ t H t H=\cup_t H^t H=∪tHt
A strategy: s i : H → Δ ( A i ) s_i:H\to \Delta(A_i) si:H→Δ(Ai)
举个例子说明一下,囚徒博弈背景中。
A i = { C , D } A_i=\{C,D\} Ai={
C,D}两个决策者的候选动作都是 { C , D } \{C,D\} {
C,D}
三个博弈阶段以后的历史: ( C , C ) , ( C , D ) , ( D , D ) (C,C),(C,D),(D,D) (C,C),(C,D),(D,D)
那么第四阶段的决策就根据前三阶段的历史所决定。
A Bayesian game is a tuple ( N , G , P , I ) (N,G,P,I) (N,G,P,I) where
N N N是代理者的集合。
G G G是一系列博弈游戏的集合。每个游戏由元组 G = ( N , A , u ) G=(N,A,u) G=(N,A,u)定义,同一G中的博弈游戏仅仅是 u u u不同。也就是说拥有相同的代理者集合以及可选决策集合。
P P P是针对 G G G中每一个博弈游戏的先验概率。
I = ( I 1 , . . . , I N ) I=(I_1,…,I_N) I=(I1,...,IN)。 I I I是划分的集合。 I 1 I_1 I1代表第一个决策者对于 G G G的等价类划分,划分成多个等价类,等价类内部的游戏不可区分。
让我们看一个贝叶斯博弈的例子:
该游戏共有2个决策者,4个博弈游戏。我们来看一下该贝叶斯博弈的形式化表示:
G = { M P , P D , C o o r d , B o S } G=\{MP,PD,Coord,BoS\} G={
MP,PD,Coord,BoS}
P = { 0.3 , 0.1 , 0.2 , 0.4 } P=\{0.3,0.1,0.2,0.4\} P={
0.3,0.1,0.2,0.4}
I = { I 1 , I 2 } , I 1 = { I 1 , 1 , I 1 , 2 } = { { M P , P D } , { C o o r d , B o S } } I=\{I_1,I_2\},I_1=\{I_{1,1},I_{1,2}\}=\{\{MP,PD\},\{Coord,BoS\}\} I={
I1,I2},I1={
I1,1,I1,2}={
{
MP,PD},{
Coord,BoS}}
6-3 Bayesian Games:Second Definition
贝叶斯博弈的第二种定义(Epistemic Types 认知类型):
A Bayesian game is a tuple ( N , A , Θ , p , u ) (N,A,\Theta,p,u) (N,A,Θ,p,u) where
N N N是代理者的集合。
A = ( A 1 , . . . , A n ) A=(A_1,…,A_n) A=(A1,...,An), A 1 A_1 A1代表第一个决策者的可选动作集合。
Θ = ( Θ 1 , . . . , Θ n ) \Theta=(\Theta_1,…,\Theta_n) Θ=(Θ1,...,Θn),假设决策者1有三个类型 Θ 1 = ( Θ 1 , 1 , Θ 1 , 2 , Θ 1 , 3 ) \Theta_1=(\Theta_{1,1},\Theta_{1,2},\Theta_{1,3}) Θ1=(Θ1,1,Θ1,2,Θ1,3)
p : Θ → [ 0 , 1 ] p:\Theta \to [0,1] p:Θ→[0,1],每个决策者属于每种类别的先验分布
u = ( u 1 , . . . , u n ) , w h e r e u i : A × Θ → R u=(u_1,…,u_n),where \space u_i:A\times \Theta \to R u=(u1,...,un),where ui:A×Θ→R。一组动作组合+一组类别组合才能确定一组效用组合。
我们来看一下上一章节中贝叶斯博弈的认知类型定义形式(一组动作组合( a 1 , a 2 a_1,a_2 a1,a2)+一组类别组合( θ 1 , θ 2 \theta_1,\theta_2 θ1,θ2)才能确定一组效用组合( u 1 , u 2 u_1,u_2 u1,u2)
Given a Bayesian game ( N , A , Θ , p , u ) (N,A,\Theta,p,u) (N,A,Θ,p,u) with finite sets of players,actions,and types,strategies are defined as follows:(采用认知类型定义方式,均为有限集合)
Pure strategy: s i : Θ i → A i s_i:\Theta_i\to A_i si:Θi→Ai
Mixed strategy: s i : Θ i → Π ( A i ) s_i:\Theta_i\to \Pi(A_i) si:Θi→Π(Ai)
s i ( a i ∣ θ i ) s_i(a_i|\theta_i) si(ai∣θi):决策者 i i i类型为 θ i \theta_i θi的条件下,选择动作 a i a_i ai的概率
Interim expected utility Interim方式定义的效用期望
E U i ( s ∣ θ i ) = ∑ θ − i ∈ Θ − i { p ( θ − i ∣ θ i ) × ∑ a ∈ A [ Π j ∈ N s j ( a j ∣ θ j ) × u i ( a , θ i , θ − i ) ] } EU_i(s|\theta_i)=\sum_{\theta_{-i}\in \Theta_{-i}}\{p(\theta_{-i}|\theta_i) \times \sum_{a\in A}[\Pi_{j\in N}s_j(a_j|\theta_j)\times u_i(a,\theta_i,\theta_{-i})]\} EUi(s∣θi)=∑θ−i∈Θ−i{
p(θ−i∣θi)×∑a∈A[Πj∈Nsj(aj∣θj)×ui(a,θi,θ−i)]}
这个式子极其复杂,让我们来详细剖析一下。
首先从外到内一共三层循环:
1. ∑ θ − i ∈ Θ − i \sum_{\theta_{-i}\in \Theta_{-i}} ∑θ−i∈Θ−i:在确定 Θ i = θ i \Theta_i=\theta_i Θi=θi的前提下,遍历其他决策者 − i -i −i的所有认知类型组合情况 θ − i = ( θ 1 , θ 2 , . . . , θ i − 1 , θ i + 1 , . . . , θ n ) \theta_{-i}=(\theta_1,\theta_2,…,\theta_{i-1},\theta_{i+1},…,\theta_n) θ−i=(θ1,θ2,...,θi−1,θi+1,...,θn)。因此在内层循环中相当于所有决策者认知类型都已知。
2. ∑ a ∈ A \sum_{a\in A} ∑a∈A:遍历所有可能的动作组合。 a = ( a 1 , a 2 , . . . , a n ) a=(a_1,a_2,…,a_n) a=(a1,a2,...,an)。因此在内层循环,相当于所有决策者的认知类型以及动作均已知。
3. Π j ∈ N \Pi_{j\in N} Πj∈N:遍历所有的决策者,因为要计算外层循环动作组合 a a a产生的概率。
接下来我们看一看各个步骤分别求的是什么?
1. Π j ∈ N s j ( a j ∣ θ j ) \Pi_{j\in N}s_j(a_j|\theta_j) Πj∈Nsj(aj∣θj):决策者 j j j在已知类型为 θ j \theta_j θj时选择动作 a j a_j aj的概率,乘积就是外层循环策略组合 a a a的生成概率。
2. u i ( a , θ i , θ − i ) u_i(a,\theta_i,\theta_{-i}) ui(a,θi,θ−i):已知所有的认知类型以及所有人的动作选择后的效用值。
3. ∑ a ∈ A [ Π j ∈ N s j ( a j ∣ θ j ) × u i ( a , θ i , θ − i ) ] \sum_{a\in A}[\Pi_{j\in N}s_j(a_j|\theta_j)\times u_i(a,\theta_i,\theta_{-i})] ∑a∈A[Πj∈Nsj(aj∣θj)×ui(a,θi,θ−i)]:在已知所有人认知类型的前提下,所有动作组合的期望效用。
4. p ( θ − i ∣ θ i ) p(\theta_{-i}|\theta_i) p(θ−i∣θi):在已知 Θ i = θ i \Theta_i=\theta_i Θi=θi的前提下,其他决策者类型为 θ − i \theta_{-i} θ−i的概率。
5.总体:在仅仅已知自己认知类型的前提下,遍历所有混合策略组合、遍历所有其他决策者认知类型的效用期望。
ex-ante expected utility ex-ante 方式定义的效用期望
E U i ( s ) = ∑ θ i ∈ Θ i p ( θ i ) E U i ( s ∣ θ i ) EU_i(s)=\sum_{\theta_i\in \Theta_i}p(\theta_i)EU_i(s|\theta_i) EUi(s)=∑θi∈Θip(θi)EUi(s∣θi)
ex-ante方式定义的效用期望利用了上述Interim方式定义。ex-ante不知道自己的认知类型,那就遍历自己的所有认知类型就可以了,然后算总体的期望,也就是从3层循环变成了4层循环。
Bayes-Nash Equilibrium 贝叶斯纳什均衡
s i ∈ a r g m a x s i ′ E U i ( s i ′ , s − i ∣ θ i ) s_i\in argmax_{s_i^{‘}}EU_i(s_i^{‘},s_{-i}|\theta_i) si∈argmaxsi′EUi(si′,s−i∣θi)(Interim方式定义)
决策者 i i i的贝叶斯纳什均衡混合策略 s i s_i si就是,在其他人的混合策略 s − i s_{-i} s−i不改变的情况下,已知自己的认知类型的前提下,最大化自己的效用期望所对应的混合策略。
s i ∈ a r g m a x s i ′ E U i ( s i ′ , s − i ∣ θ i ) = a r g m a x s i ′ ∑ θ i p ( θ i ) E U ( s i ′ , s − i ∣ θ i ) s_i\in argmax_{s_i^{‘}}EU_i(s_i^{‘},s_{-i}|\theta_i)=argmax_{s_i^{‘}}\sum_{\theta_i}p(\theta_i)EU(s_i^{‘},s_{-i}|\theta_i) si∈argmaxsi′EUi(si′,s−i∣θi)=argmaxsi′∑θip(θi)EU(si′,s−i∣θi)(ex-ante方式定义)
我们来了解一下警长困局 Sheriff’s Dilemma故事背景:一位警长正面对一个犯罪嫌疑人,犯罪嫌疑人可能真的是罪犯也可能只是一个无辜的平民。警长和犯罪嫌疑人需要同时决定是否对对方开枪。
情景设定:犯罪嫌疑人有 p p p的概率是一名罪犯,同时有 1 − p 1-p 1−p的概率只是个平民;警长如果对方选择开枪则会选择开枪,如果对方不开枪则倾向于不开枪;罪犯无论对方开枪与否自己都倾向于开枪;平民无论对方开枪与否自己都倾向于不开枪。
收益矩阵:
这个博弈游戏可以说是一个单向的贝叶斯博弈,对于警长来说,犯罪嫌疑人的类型不确定;而对于犯罪嫌疑人来说,警长却只有一个类型。因此我们从警长角度来分析贝叶斯纳什均衡。
因为犯罪嫌疑人类型不确定,导致在警长角度,犯罪嫌疑人选择射击或者不射击的期望收益相等。
对于警长来说,如果对方是平民(上方收益矩阵),选择不射击对于选择射击是严格占优的。对应下方收益矩阵,选择射击对于选择不射击是严格占优的。因此可以得出下式:
− 1 × ( 1 − p ) + 0 × p = 0 × ( 1 − p ) + ( − 2 ) × p , p = 1 / 3 -1\times(1-p)+0\times p=0\times(1-p)+(-2)\times p,p=1/3 −1×(1−p)+0×p=0×(1−p)+(−2)×p,p=1/3。因此当 p > 1 / 3 p>1/3 p>1/3时,警长选择不射击的期望收益更大,相反选择射击的期望收益更大。犯罪嫌疑人的类型概率分布直接影响了警长的均衡策略选择。
A coalitional game with transferable utility is a pair ( N , v ) (N,v) (N,v),where
N N N is a finite set of players,indexed by i i i;决策者的集合
v : 2 N → R v:2^N\to R v:2N→R associates with each colition S ∈ N S\in N S∈N a real-valued payoff v ( S ) v(S) v(S) that the coalition’s members can distribute among themselves.We assume that v ( ∅ ) = 0 v(\emptyset)=0 v(∅)=0。为每个联盟 S S S分配一个效用值 v v v的效用函数 v ( S ) v(S) v(S),每个联盟都属于幂集 2 N 2^N 2N的子集。
合作博弈需要解决的两大问题:
1.合作博弈内部的联盟该如何生成?(谁和谁合作?)
该问题一般直接设置为The Grand Coalition,即所有决策者都在一个联盟里,按SuperAdditive的理念,这样的联盟收益是最大的。
2.联盟内部是如何分配效用的?(如何合作?)
为了保证效用分配的公平性与稳定性。
SuperAdditive Games 超加博弈:
A game G = ( N , v ) G=(N,v) G=(N,v) is superadditive if for all S , T ∈ N S,T\in N S,T∈N,if S ∩ T = ∅ S\cap T=\emptyset S∩T=∅,then v ( S ∪ T ) > = v ( S ) + v ( T ) v(S\cup T)>=v(S)+v(T) v(S∪T)>=v(S)+v(T).
超加性也就是所谓的“ 1 + 1 > 2 1+1>2 1+1>2”,两个互补相交的联盟合并成一个联盟,共同的效用收益要大于两个联盟的效用和,也就是说合作带来了更大的效用。因此按道理说合作博弈中所有决策者全部合作形成一个最大的联盟,可以获得全局最大收益,这也就是所谓的The Grand Coalition。
Sharply最初的设想如下:联盟成员应该根据其边际效用获得相应的效用分配。
但实际上这个设想是十分不合理的,比如说如下情况:
我们假设一个背景,一件事情需要所有的决策者共同参与才可成功获得效用,因此 v ( N ) = 1 v(N)=1 v(N)=1and v ( S ) = 0 , i f N ≠ S v(S)=0,if N\neq S v(S)=0,ifN=S。因此针对每一个决策者 i i i, v ( N ) − v ( N / { i } ) = 1 v(N)-v(N/\{i\})=1 v(N)−v(N/{
i})=1,每个人的边际效用都是1,因此每个人对于总体的贡献都是 100 % 100\% 100%,难道给每个人都分配全部的总体效用?这也不够分啊!
因此,我们需要针对边际效用引入一个加权策略
Shapley’s axioms Shapley定理的三条性质:
1.Symmetry
如果两个决策者 i 、 j i、j i、j加到任意一个联盟中,所带来的边际效用都是相等的,则我们称这两个决策者是Interchangeable的。对于任意两个可互换的决策者其Shapley Value相等,即 ψ i ( N , v ) = ψ j ( N , v ) \psi_i(N,v)=\psi_j(N,v) ψi(N,v)=ψj(N,v)
2.Dummy Players
如果一个决策者 i i i加到任意一个联盟中,所带来的边际效用都为0,则我们称这个决策者是dummy player,并且该决策者的Shapley Value为0,即 ψ i ( N , v ) = 0 \psi_i(N,v)=0 ψi(N,v)=0
3.Additivity
如果我们可以把某个博弈拆分成两个彼此独立的博弈,或者说可以将该博弈的效用函数拆分成两个独立的效用函数,即 ( v 1 + v 2 ) ( S ) = v 1 ( S ) + v 2 ( S ) (v_1+v_2)(S)=v_1(S)+v_2(S) (v1+v2)(S)=v1(S)+v2(S),那么每个决策者的Shapley Value也可以拆分成两部分即 ψ i ( N , v 1 + v 2 ) = ψ i ( N , v 1 ) + ψ i ( N , v 2 ) \psi_i(N,v_1+v_2)=\psi_i(N,v_1)+\psi_i(N,v_2) ψi(N,v1+v2)=ψi(N,v1)+ψi(N,v2)。
Sharpley Value
以上三条性质,就是我们制定的“公平”规则。要想同步满足以上三条公平性质,我们只有一种效用划分方式——那就是Shapley Value。
ϕ i ( N , v ) = 1 N ! ∑ S ⊆ N / { i } ∣ S ∣ ! ( ∣ N ∣ − ∣ S ∣ − 1 ) ! [ v ( S ∪ { i } ) − v ( S ) ] \begin{aligned} \phi_i(N,v)=\frac{1}{N!}\sum_{S\subseteq N/\{i\}}|S|!(|N|-|S|-1)![v(S\cup\{i\})-v(S)] \end{aligned} ϕi(N,v)=N!1S⊆N/{
i}∑∣S∣!(∣N∣−∣S∣−1)![v(S∪{
i})−v(S)]
我们来挨个解释一下上面这个复杂又可怕的公式:
v ( S ∪ { i } ) − v ( S ) v(S\cup\{i\})-v(S) v(S∪{
i})−v(S)
是指在现有联盟 S S S的基础上引入 i i i带来的边际效用。
∑ S ⊆ N / { i } \sum_{S\subseteq N/\{i\}} S⊆N/{
i}∑
是指针对所有不包含 i i i的联盟遍历求和引入 i i i的边际效用。
∣ S ∣ ! ( ∣ N ∣ − ∣ S ∣ − 1 ) ! |S|!(|N|-|S|-1)! ∣S∣!(∣N∣−∣S∣−1)!
是引入 i i i后边际效用为 v ( S ∪ { i } ) − v ( S ) v(S\cup\{i\})-v(S) v(S∪{
i})−v(S)的情况总数(也就是在联盟 S S S中引入 i i i带来的边际效用为 v ( S ∪ { i } ) − v ( S ) v(S\cup\{i\})-v(S) v(S∪{
i})−v(S)的情况总数)。 ∣ S ∣ ! |S|! ∣S∣!是指在引入 i i i之前形成 S S S的所有可能序列总数, ( ∣ N ∣ − ∣ S ∣ − 1 ) ! (|N|-|S|-1)! (∣N∣−∣S∣−1)!是指引入 i i i后补全到 N N N的所有可能序列总数。统计所有边际效用的出现次数的目的是为了增加权重,出现次数越多的权重越大。
1 N ! \frac{1}{N!} N!1
是指所有决策者形成The Grand Coalition的所有序列可能性。
7-4 The Core
Shapley Value定义了一种相对公平的联盟内部效用分配方法,然而这种分配方法却忽略了另外一个很重要的性质——稳定性。Shapley Value是在所有决策者一起形成The Grand Coalition的前提下制定的,但实际情况是并不是所有的合作博弈中,所有决策者都会一起构成一个大联盟,反而会出现一些“局部合作”更能体现个人的利益。
投票博弈游戏背景:有 A 、 B 、 C 、 D A、B、C、D A、B、C、D四个政党一起参与某项议会议题,分别有 45 、 25 、 15 、 15 45、25、15、15 45、25、15、15的投票权。议题是是否批准$100百万的财务账单。如果最终投票结果大于 51 51 51票则投赞成票的人按对应比例瓜分财政拨款,否则所有人都无法获得财政拨款。
Shapley Value:如果假设四个人一起合作形成一个大联盟,那么由Shapley Value计算得权重: ( 50 , 16.67 , 16.67 , 16.67 ) (50,16.67,16.67,16.67) (50,16.67,16.67,16.67)。 B B B与 C , D C,D C,D票权不同,但最终分得得效用却相同,因此B不会愿意再维持这个大联盟。并且 A A A分别与 B 或 C 或 D B或C或D B或C或D形成小联盟都可以达到51票得赞成条件,这样分得的效用可比大联盟高多了。因此实际情况中,很难形成大联盟,因而无法达到应用Shapley Value的条件。
The Core
在哪种分配方案的支持下,代理者们愿意形成The Grand Coalition?答案是,当且仅当分配方案属于该合作博弈的The Core中。The Core内的分配向量符合以下两个条件:
1.首先我们设定每种分配方案所有分配值的总和等于所有代理者一起合作形成联盟的效用值,也就是说形成The Grand Coalition时获得的收益,按之前的假设这个收益也是整个合作博弈能达成的最大收益。
∑ i = 1 n ψ i = v ( { 1 , . . . , n } ) \sum_{i=1}^n\psi_i=v(\{1,…,n\}) i=1∑nψi=v({
1,...,n})
2.将最大收益具体划分到每个代理者身上获得一个分配向量。我们要保证任意一个联盟,其内部成员被分配收益(The Grand Coalition合作下)的总和都要大于该小联盟合作的收益。也就是说,我们构想出一种针对于最大收益的分配方案,使得没有任何一个小联盟单独拆除去可以获得更大的联盟收益。(十分类似于纳什均衡的定义方式——无更大获利的偏移方案)
∑ i ∈ S ψ i > = v ( S ) \sum_{i\in S}\psi_i>=v(S) i∈S∑ψi>=v(S)
任意一个合作博弈的The Core集,不一定非空,也不一定只有一种符合条件的分配方案。
Simple GamesSimple Games定义:
A game G = ( N , v ) G=(N,v) G=(N,v) is simple if for all S ⊂ N , v ( S ) ∈ { 0 , 1 } S\subset N,v(S)\in \{0,1\} S⊂N,v(S)∈{
0,1}
简单博弈是指所有联盟的收益要么是0要么是1。
Veto Player定义:
A player i i i is a veto player if v ( N / { i } ) = 0 v(N/\{i\})=0 v(N/{
i})=0
拥有一票否决的代理者是指只要缺少了他,形成的任何联盟的收益都是0。
A game G = ( N , v ) G=(N,v) G=(N,v) is convex if for all S , T ⊂ N , v ( S ∪ T ) > = v ( S ) + v ( T ) − v ( S ∩ T ) S,T\subset N,v(S\cup T)>=v(S)+v(T)-v(S\cap T) S,T⊂N,v(S∪T)>=v(S)+v(T)−v(S∩T)
凸博弈与我们之前学习到的凸函数等定义都比较相似。并且凸博弈的定义是之前介绍的超加性的增强定义,超加性中规定 S , T S,T S,T互不相交,凸博弈中并不要求互不相交只需要减去一遍公共部分即可。
每一个凸博弈都至少还有一个非空的核。
在每一个凸博弈中,Shapley Value在核中。
7-5 Comparng the Core and Shapley Value in an Example
The Core计算过程:
v ( S ) = 1 i f 1 ∈ S a n d # S > = 2 , v ( S ) = 0 o t h e r w i s e x 1 + x 2 > = 1 , x 1 + x 3 > = 1 , x 1 + x 2 + x 3 = 1 , x i > = 0 x 1 = 1 , x 2 = 0 , x 3 = 0 \begin{aligned} v(S)=1 \space if \space 1\in S \space and \space \#S>=2,v(S)=0\space otherwise\\ x_1+x_2>=1,x_1+x_3>=1,x_1+x_2+x_3=1,x_i>=0\\ x_1=1,x_2=0,x_3=0 \end{aligned} v(S)=1 if 1∈S and #S>=2,v(S)=0 otherwisex1+x2>=1,x1+x3>=1,x1+x2+x3=1,xi>=0x1=1,x2=0,x3=0