Microsoft PowerPoint - ç¬¬å–�ç«€â•ﬂâ•ﬂ å’‹ä½œå“ıå¼‹.ppt [å–¼å®¹æ¨¡å¼‘]

Size: px

Start display at page:

Download "Microsoft PowerPoint - ç¬¬å–�ç«€â•ﬂâ•ﬂ å’‹ä½œå“ıå¼‹.ppt [å–¼å®¹æ¨¡å¼‘]"

但柳
7 years ago
Views:

1 第六章合作博弈三占优方法 ( 合作博弈的一类解概念 ): 核心核仁四估值方法 ( 合作博弈的一类解概念 ): hapley 值合作博弈与非合作博弈相对称是一种参与者能够联合达成一个具有约束力且可强制执行的协议的博弈类型合作博弈强调的是集体理性强调效率公正公平合作博弈最重要的两个概念是联盟和分配每个参与者从联盟中分配的收益正好是各种联盟形式的最大总收益每个参与者从联盟中分配到的收益不小于单独经营所得收益合作博弈的基本形式是联盟博弈它隐含的假设是存在一个在参与者之间可以自由流动的交换媒介 ( 如货币 ) 每个参与者的效用与它是线性相关的这些博弈被称为单边支付博弈或可转移效用 (Trasferable Utlty TU) 博弈合作博弈的结果必须是一个帕累托改进合作双方的利益都有所增加或者至少是一方的利益增加而另一方的利益不受损害合作博弈研究人们达成合作时如何分配合作得到的收益即收益分配问题合作博弈采取的是一种合作的方式合作之所以能够增进双方的利益就是因为合作博弈能够产生一种合作剩余至于合作剩余在博弈各方之间如何分配取决于博弈各方的力量对比和制度设计因此合作剩余的分配既是合作的结果又是达成合作的条件合作博弈的核心问题是参与人如何联盟以及如何重新分配联盟的支付下面首先分析联盟的概念与联盟相关联的特征函数特征函数的性质决定了合作博弈的特征定义 6.. 在人博弈中参与人集用 N { } 表示 N 的任意子集称为一个联盟 (coalto)空集和全集 N也可以看成是一个联盟当然单点集 {} 也是一个联盟定义 6.. 给定一个人博弈是一个联盟 v() 是指和 N { N } 的两组博弈中的最大效用 v() 称为联盟的特征函数 (characterstc fucto) 规定 v( ) 0根据定义 v() 表示参与人与全体其他人博弈时的最大效用值表示为 v({}) 用 ( N v) 表示参与人集为 N 特征函数为 v的合作博弈其中 v 是定义在 N 上的实值映射在很多情况下一个联盟能获得的支付依赖于其他参与人所采取的行动 v() 有时被解释为联盟独立于联盟 N 的行动可保证的最大支付合作博弈的分类主要是根据特征函数的性质下面根据特征函数的性质介绍几类特殊的合作对策如果 v() ( N v) 仅与中元素的个数有关则称作对称博弈如果 v( ) v( N ) v( N ) 则 ( N v) 称作常和博弈如果 0 v( ) 则 ( N v) 称作简单博弈 N 例如在投票博弈中每个参与人的权重 w ( w Q) 0 w Q v( ) w Q 如果 v( ) v( T ) v( T ) v( T ) 则 ( N v) 称作凸博弈凸性表示联盟越大新成员的贡献率就越大因为设 { m} N 对于任意 K 有某一个成员 m N为加入的新成员记 T=K {m+} 则由凸性可知 ({ m}) ( K {m+}) ( { m+})+ ({ K}) 则有 ( { m+})- ({ m}) ( K {m+})-({ K }) 即新成员 m+ 加入联盟后边际贡献不小于新成员与联盟的任何子联盟 K所组合产生的边际贡献即新成员的边际贡献随联盟的增大而越来越大

2 定义 6.. 如果特征函数 v 满足 : 对于联盟和有 v( ) v( T ) v( T ) 则称特征函数具有超可加性超可加性表示两个不相交的联盟分别行动其分别单干的结果不如组成一个联盟的联合而共同行动这是大联盟形成的动因特征函数只有满足超加性才有形成新联盟的必要性否则如果一个合作博弈的特征函数不满足超可加性那么其成员没有动机形成联盟已经形成的联盟将面临解散的威胁显然凸博弈的特征函数一定满足超可加性例 6. 设有一个人合作对策每个参与人各有两个纯策略 A 和 B 当三人不合作时其支付见下表假设采用最稳妥策略即最坏情况下选择最好求合作博弈的支付函数解 : 用表示一个联盟表示联盟中参与人的个数当 =0 自然有 v( ) 0 当 = 有个以为例当则 N 的策略集合 A B N 策略组合 ( A A) ( A B)( B A) ( B B) 与 N 进行如下矩阵对策 : 上述矩阵对策没有纯策略的混合策略是 N 的混合策略是 0 0 的均衡值是故 v ( ) 同理可以求出 v( ) v( ) 当 = 有个以为例当则 N 的策略集合 ( A A)( AB )( B A)( BB ) 策略组合与进行如下矩阵对策 : 上述矩阵对策有纯策略的均衡值是故 v( ) 同理可以求出 v ( ) v ( ) 当 = 有个 N 最大的联盟. 各策略组合对于的支付总和如下 : v( N ) max 0 至此特征函数的值已全部求出对于合作博弈 ( N v) N 特征函数 v 满足超加性自然有 : v( N) v( ) v( ) v( ) v( ) v( ) v( ) 根据上述不等式特征函数 v 分成两种类型 : 类型 : v 满足 v( N) v ( ) 即大联盟的效用是每个参与人的效用之和这说明通过联盟并没有创造新的合作剩余联盟没有价值这种联盟也不可能维持这种对策称为非实质性对策没有研究价值

3 类型 : v 满足 v( N) v( ) 即大联盟的效用大于每个参与人的效用之和这说明通过联盟创造了新的合作剩余联盟有意义这种联盟能否维持取决于如何分配合作剩余使每个参与人的支付都有改善这种对策称为实质性对策是本部分研究的范畴所谓分配就是博弈的一个维向量集合之所以是维向量是由于每个参与人都要得到相应的分配维的分配向量称为博弈的解各种方法即各种解概念代表着分配的不同观点定义 6.. 对于合作博弈 ( N v) N 对每个参与人 N 给予一个实值参数 x 形成维向量 x ( x x ) 且其满足 : x v( ) x v( N) 则称 x 是联盟的一个分配方案分配的定义中 x v( ) 是基于个人理性合作中的收益不能小于非合作中的收益反映了参与人的参与约束如果 x v() 那么参与人是不可能参加联盟的 x v ( ) x v ( N ) x v( N ) 是基于集体理性每个参与人的分配之和不能超过集体剩余 v( N ) 另外若 v( N) 没有全部被分配显然 x 不是一个帕类托最优的分配方案不会参与人所接受在例 6. 中存在一种分配方案 : x { x x x } 满足 : x v({}) x v({}) x v({}) x x x 分配显然不是一个而是无限个无限个分配形成一个分配集合对于实质博弈其分配总是有无限个例如对于实质博弈 ( N v) 由于 u v( N) v( ) 0 存在无限个正向量 u ( u u u ) 满足 u u u u 显然如下的 x ( x x ) 都是分配其中 x v u 用 E (v) 表示一个博弈 ( N v ) 的所有分配方案组成的集合定义 6.. 设 E(v) 的两个分配 x 和 y 是一个联盟如果分配方案 x 和 y 满足 () x y () x v( ) 则称分配方案 x 在上优超于 y 或称分配方案 y在上劣于 x 记为 x y 如果分配方案 x 在上优超于 y 则联盟会拒绝分配方案 y y 方案得不到切实执行因为从 y 到 x 中的每个参与人的收益都得到改善创造的剩余 v( ) 又足以满足他们在 x 中的分配在优超关系中联盟的特征 :. 单人联盟不可能有优超关系否则 x { y y x v({ }) 则有 y v({ }) 与 y是分配方案矛盾 }. 全联盟 N 上也不可能有优超关系因此如果在上有优超关系则. 优超关系是集合 E(v) 上的序关系这种序关系一般情况下不具有传递性和反身性. 对于相同的联盟优超关系具有传递性即 x 则有 y y z x z. 对于不同的联盟优超关系不具有传递性

4 尽管可行分配集合 E(v) 中有无限个分配但实际上有许多分配是不会被执行的或者不可能被参与人所接受的很显然联盟的每一个成员都不偏好于劣分配方案因此真实可行的分配方案应该剔除劣分配方案定义 6.. 在一个人合作博弈 ( N v) 中全体最优分配方案形成的集合称为博弈的核心 (core) 记为 C (v)显然有 C E 说明 :. 核心 C(v) 是 E 中的一个闭凸集. 若 ( ) 则将 C(v) 中的向量作为分配既满足个人理性又满足集体理性 C v x x. 用核心作为博弈的解其最大缺陷是 C(v) 可能是空集也可能不唯一寻找核心的方法对于 x E 存在联盟有 x v( ) 则定义 v( ) x 0 定理 6.. 分配方案 x ( x x ) 在核心 C(v) 中的充要条件定义 v( N ) v( ) v( ) 0 使得在中平均分是 : N \ 配 x v() () N 在 N 中平均分配从而得到一个新的分配 y ( y y ) 如下 : ( 个体理性 ) () x v( N) ( 集体里性 ) x y 证明 ( 充分性 ) 如果 x E x 满足 () () 则 x 不可能被优 v ( ) 超即 x C 反证法设存在使 y x 根据优超的定义有 : 显然如此定义得向量 y ( y y 是个分配且有 x y y v ( ) ) y x 则有 v( ) x y v( ) 矛盾下证必要性 ( 逆否命题 ): 如果 x E x 不满足 ()() 则 x 一定被优超即 x C 例 6. 假想的联合国安全理事会投票超过两票算通过该博弈的特征函数为 v( ) v() v() v() v() v() v() 而对所有其他的 v ( ) 0应用定理 6.. 有 x 对各个联盟有 0 x x x x x x x x x x 由 x x x x 0 x 0 推得 x 而用 x x 0 x x x 0 又得到和 x x 所以核心是 C ( a a000) :0 a 例 6. 设人合作博弈 v 的特征函数如下 : v( ) 0 v({ }) ({ }) v({ }) v ({ }) v 求其核心 C(v) 解由核心定义若 x ( x x x ) C( v) x x x x x x x x x x 0 解此不等式组得则它必满足 0 x 0 x 0 x x x x

5 例 6. 考虑如下的合作博弈 ( N v) N 特征函数如下 : v( ) 0 v ( ) x 0 x x 解线形不等式组 : x x x x x x x 该不等式组无解 C 上面三个例子说明了求解核心的方法 x x x 解得 x x x 在合作博弈中用核心代替分配具有明显得优点即 C 的稳定性对于 C 中的每一个分配每个联盟都没有反对意见都没有更好的分配每个分配都可以得到执行当然用 C( v ) 代替 E 也有致命的缺陷即 C 可能是空集而 E 定理 6.. 对于人的联盟博弈核心 C 非空的充分必要条件是线性规划 ( P) 有解 ( P ) m x v( N ) s. t x v( ) x v( N) N 定理的直观意义很明显线性规划 (P) 若有解则最优解一定属于 C (v) 若 C 则 C 中的每个向量都是可行解自然线性规划 (P) 有最优解对于原线性规划 (P) 写出它的对偶规划 (DP): ( DP) max y v( ) v( N ) N y s. t N y 0 N 定理 6... 博弈 ( N v) 有 C 的充分必要条件是 : y 对于满足 s. t N 的向量 y 有 yv( ) v( N ) y 0 N 定义 6.. 设 ( N v) 是个 0- 简单对策若存在一个参与人满足 v( N ) 0 则称作一个否决人定理 6.. 简单对策 ( N v) 中 C 充分必要条件是 N 中存在一个否决人证明设是 N 中一个否决人定义 e 处于第的位置根据定理 6.. e 是一个分配 e C 且 C 下证必要性用反证法设 x C 且不存在否决人即 v( N ) 则 x( N ) x( N ) v( N )= N 故有 x( N) x( N ) x( ) x N 从而 x 0 N 也即 v ( N ) x 0 矛盾 N 为评估对 x 满意性定义如下的被称作超出值的指标 : e( x) v( ) x e( x ) 的大小反映了对 x满意性 e( x) 越大对 x 越不满意因为中所有参与人的分配之和远没有达到其所创造的合作剩余 v( ) e( x ) 越小对 x 越满意当 e( x) 为负值时中所有参与人不但分配了其所创造的合作剩余 v( ) 还分配了其他联盟所创造的价值

6 对于同一个 x 共有个可以表示为故可以计算出个 e( ) 联盟对的满意性 x x 取决于 e( x) 中的最大的故可以对个 e( x) 由大到小排列得到一个的向量 : ( x) ( x) ( x) ( x) 其中 ( x) e( x) ( x) ( x) ( x) 联盟对 x 的满意性取决于 ( x ) 的大小 ( x) 越小联盟对 x 越满意对于两个不同的分配 x y 分别计算出 ( x) ( y) 如果是 ( x) 小则联盟对 x 的满意性大于联盟对 y 的满意性自然 x 优于 y 当然这种向量大小的比较不同于数字的比较是采用字典序的比较方法字典序的比较方法如下 : 对于向量 ( x) ( x) ( x) ( x) 和 ( y) ( y) ( y) ( y) 存在一个下标 k 使得 ( ) ( ) k k ( x) k ( y) 则称 ( x) 字典序小于 ( y) 用符号表示 ( x) ( y) L 有了上述的定义就可以给出核仁的定义了定义 6.. 对于合作博弈 ( N v) 核仁 N 是一些分配的集合即 N E 使得任取一个 x N ( x) 都是字典序最小的即 N x E : y E y x ( x) L ( y) 定理 6.. 对于合作博弈 ( N v) 其核仁 N 且 N 只包含一个元素 x 定理 6..6 对于合作博弈 ( N v) 如果核心 C(v) 则有 N C ( v ) 证明用反证法设存在一个分配 x N x C 根据核心的性质由 x C 可知 : 必存在一个联盟满足 x v( ) 由此可知 e( x) v( ) x 0 设 ( x ) 是所有 ( x ) ( x ) ( x ) ( x) e x 中最大的故有 ( ) ( ) ( ) 0 x e x v x ( ) 由 C 可知存在分配 y C 根据核心的性质任取一个 e( y) v( ) y 0 有 ( y) ( y) ( y) ( y) 由此可知 ( ) 0 y 满足 x N ( x) ( x) ( x) ( x) ( x) 0 y C ( y) ( y) ( y) ( y) 这与 ( x) L ( y) 矛盾定理得证例 6. 考虑如下的合作博弈 ( N v) N 特征函数如下 : v( ) v( ) v( ) 0 v( ) v( ) v( ) 6 v( ) 0 求该博弈的核仁解先求出该博弈的核心再求核仁 x ( x x x ) C 根据核心的充分必要条件 : x x 0 x x x x x x 6 x x x 0 解此不等式组得到 C (6 x x) : x C 故有 N C 下面开始求 N 对于核心 C ( 6 x x ) : x 求 e( x) v( ) x xc 有 e( x) =-=0 有 e( =0- = x ) (6 x) x 6 有 e( x) =0-( x) = x 有 e( x) =- (6 x) = x 有 e( x) =- x = x 6 有 e( 6 x) =6- (6 x) x=0 有 e( x) =0-0=0 当 x ( m max m max 上式在 x x 达到故有 N = ( 6 x x) : x ( ) 该结果验证了 N N 6

7 四估值方法 :hapley 值 C 故有 N C 下面开始求 N 对于核心 C ( 6 x x ) : x 求 e( x) v( ) x xc 有 e( x) =-=0 有 e( =0- = x ) (6 x) x 6 有 e( x) =0-( x) = x 有 e( x) =- (6 x) = x 有 e( x) =- x = x 6 有 e( 6 x) =6- (6 x) x =0 有 e( x) =0-0=0 当 x ( m max m max 上式在 x 达到故有 N = ( 6 x x) : x ( ) 该结果验证了 N N 分配是合作博弈最重要的概念但遗憾的是在一个博弈中分配有无限个且许多根本就得不到执行利用优超的概念对分配进行了分类形成了核心的概念但遗憾的是许多博弈中核心可能是空集为此引入了超出这一指标寻求最大超出最小化的分配即核仁核仁这一解的优势体现在核仁总存在且是唯一的这一解的缺陷就是计算太复杂因为共有个本部分引入了一个很直观的解的概念即 hapley 值参与人按照 hapley 值进行分配四估值方法 :hapley 值四估值方法 :hapley 值定理 6.. 对每个博弈 ( N v) 存在唯一的 hapley 值其中!( )! ( v( ) v( ))! N / 下面对这一计算公式给出非数学化的解释 : x 就是按照参与人的平均贡献来安排的分配设计在一个博弈中每个人的所得应该与其贡献成正比对于联盟其合作剩余 v( ) 如加入则新联盟的合作剩余是 v( )因此的贡献是 v( ) v( ) 在博弈 ( N v) 中不包含的有个对每个都有一个贡献值 v( ) v( ) 因此 hapley 值的计算公式中有项即使对于一个固定的 v( ) v( ) 与中参与人的排列顺序无关与 N 中参与人的顺序无关因此 hapley 值系数中存在!( )! 以及! 这主要是为了计算对联盟贡献 v( ) v( ) 的平均值四估值方法 :hapley 值!( )! 对于也可以作出这样解释 :! 加入其贡献是 v( ) v ( ) 加入的概率是多少? 如果个局中人参加依次博弈当加入该博弈时其前面已有一些参与人加入后后继的参与人集合 N 和 N 中参与人的顺序与 v( ) v( ) 无关加入的概率是!( )!! v( ) v( ) 的数学期望 ( 或者平均值 ) 就是 hapley 值 6hapley 值不一定是个分配即理性约束 v 可能不满足四估值方法 :hapley 值例 6..6 假设联合国安理会进行投票部分国家可以形成联盟该博弈的特征函数为 : v( ) v() v() v() v() v() v() 而对所有其他 ( ) v ( ) 0 为了求对所有包含参与人的联盟按 hapley 值求和 v( ) 与 v( ) 无差异的联盟有 { } { } { } { } { } { } 和 { } 对于其他的 v( ) v( ) = 所以有!!!!!0! 9 ( v) ( 0) ( 0) ( 0)!!! 0!! 类似地 ( 0)! 0 于是这样参与人比参与人重要得多

8 四估值方法 :hapley 值定理 6.. 若博弈 ( N v ) 满足超可加性即 v( ) v( ) v( ) 则 hapley 向量 E 即 hapley 值是分配证明 ( N v) 满足超加性则 v( ) v( ) v( )!( )! ( v( ) v( )) N /!!( )! v( ) v( )! N / 8

1 线性空间基维数和坐标 3 子空间 4 线性空间的同构 5 线性映射 6 线性映射的像与核 7 线性变换 8 不变子空间厦门大学数学科学学院网址 :gdjpkc.xmu.edu.c; IP://

1 线性空间基维数和坐标 3 子空间 4 线性空间的同构 5 线性映射 6 线性映射的像与核 7 线性变换 8 不变子空间厦门大学数学科学学院网址 :gdjpkc.xmu.edu.c; IP:// 线性空间与线性映射知识回顾 1 线性空间基维数和坐标 3 子空间 4 线性空间的同构 5 线性映射 6 线性映射的像与核 7 线性变换 8 不变子空间厦门大学数学科学学院网址 :gdjpkc.xmu.edu.c; IP://11.19.180.133 1 线性空间厦门大学数学科学学院网址 :gdjpkc.xmu.edu.c; IP://11.19.180.133 定义称 V 是数域 F 上的线性空间,