logo资料库

博弈论算法讲义.docx

第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
资料共9页,剩余部分请下载后查看
博弈论算法
1.1博弈的战略式表述
1.2纳什均衡的定义
1.3囚徒困境
2.1纯零和对策
定义1鞍点
定义2赢得矩阵的鞍点
定理1极大极小原理
定理2零和对策解的判定
2.2零和对策的混合策略
定义3混合策略
定义4混合策略对策问题的鞍点
定理3鞍点的判定
定理4鞍点的存在性
定理5加法律
定理6乘法律
定理7对称律
2.3零和对策的线性规划解法
3.1纯策略问题
定义5双矩阵对策的Nash平衡点
3.2混合对策问题
混合对策问题的基本概念
定义6 非合作平衡点
定理8双矩阵对策非合作平衡点的存在性
定理9双矩阵对策非合作平衡点的判定
混合对策问题的求解方法
举例:对抗赛
四、N人合作博弈
5.1博弈论的扩展式表述
5.2博弈树的构造
结(nodes)
枝(branches)
信息集(information sets)
六、主要参考资料
博弈论算法 一、博弈的战略式表述及纳什均衡的定义 在博弈论里,一个博弈可以用两种不同的方式来表述:一种是战略式表述(strategic form representation),另一种是扩展式表述(或译为“展开式表述”)(extensive form representation)。 从分析的角度看,战略式表述更适合于静态博弈,而扩展式表述更适合于讨论动态博弈。 1.1 博弈的战略式表述 战略式表述又称为标准式表述(normal form representation)。在这种表述中,所参与人同时选择各自 的战略,所有参与人选择的战略一起决定每个参与人的支付。 i 战略式表述给出:   1,2, ,     。 1.博弈的参与人集合: 1,2, 2.每个参与人的战略空间: , iS i   。 , , ( n i u s s   3.每个参与人的支付函数: 1 2 i  , u  代表战略式表述博弈。 我们用 例如在两个寡头产量博弈里,企业是参与人,产量是战略空间,利润是支付;战略式表述博弈为:  G S   1  。 n n ), , , s n ; S u 1 n 1,2, , , , , , n  0;  1 ( , q q 1 2 ),  2 ( , q q 1 2  ) (1.1) ,  ,战略组合   s s 1 i   , u     n  s 1  s 1 i  s , , , , i   ,  s i  1 , s    是一个纳  ,  s  的情况下第 个参与人 n  s n  , , 0, q 2 这里 iq 、 i别表示第 i 个企业的产量和利润。 1.2 纳什均衡的定义  G q 1   有 n 个参与人的战略式表述博弈 ; S u 1 n 什均衡。如果对于每一个i 、 is 是给定其他参与人选择 的最优战略,即  G S   1 , , , u s s i i 或者用另一种表述方式, is 是下述最大化问题的解: (  u s i i  s     ) ( , i i ),    S , s i i i 1, 2,..., 我们用这个定义来检查一个特定的战略组合是否是一个纳什均衡。 argmax ,  s s 1 i i  (  u s 1 i ,..., ,...,  s 1 i   s i  ),  s  n i , (1.2) (1.3) ; n s i  S i 1.3 囚徒困境 两个嫌疑犯作案后补警察抓住,被分别关在不同的房间里审讯。警察知道两人有罪,但缺乏足够的证 据定罪,除非两人当中至少有一个人坦白。警察告诉每个人:如果两个都不承认,每个人都以轻微的犯罪 判刑 1 年;如果两人都坦白,各判刑 8 年;如果两人中一个人坦白另一个人抵赖,坦白的释放出去,抵赖 的判刑 10 年。这样,每一个嫌疑犯面临四个可能的后果:获释(自己坦白同伙抵赖);被判刑 1 年(自己 抵赖同伙也抵赖);被判刑 8 年(自己坦白同伙也坦白);被判刑 10 年(自己抵赖但同伙坦白)。 囚徒困境 囚犯 B 表 1 坦白 抵赖 囚犯 A 坦白 (-8,-8) (0,-10) 抵赖 (-10,0) (-1,-1)
在这个博弈中,每个囚徒都有两种可选择的战略:坦白或抵赖。显然,不论同伙选择什么战略,每个 囚徒的最优战略是“坦白”,比如说,如果 B 选择坦白,A 选择坦白时支付为-8,选择抵赖时的支付为-10, 因而坦白比抵赖好;如果 B 选择抵赖,A 坦白时的支付为 0,抵赖时的支付为-1,因而坦白还是比抵赖好。 就是说,“坦白”是囚徒 A 的占优战略。类似的,“坦白”也是 B 的占优战略。 在囚徒困境里,(坦白,坦白)是一个纳什均衡,而(抵赖,抵赖)不是一个纳什么均衡,因为给定 同伙选择抵赖,自己选择抵赖时得到-1,选择坦白时得到 0,因而抵赖不是自己的最优战略,类似的,(坦 白,抵赖)和(抵赖,坦白)也不是纳什均衡。 二、矩阵对策 2.1 纯零和对策 矩阵对策也叫零和对策,是一类特殊的对策问题。在这类对策中,只有两名局中人,每个局中人都只 有有限个策略可供选择。在任一纯局势下,两个局中人的赢得之和总是等于零,即双方和利益是激烈对抗 的。 设局中人 I 、 II 的策略集分别为:  S 1    m , ,  1  , S 2     1 n , ,   (2.1) 当局中人 I 选定策略 i和局中人 II 选定策略 j 后,就形成了一个局势 ( j  ,可见这样的局势共有 i ) , mn 个,对任一局势 ( i , ) j  ,记局中人 I 的赢得值为 ija ,并称 a a 1 12 a a 22 2    a a a 11 a 21  a   A         1 m m 2 n n mn       为局中人 I 赢得矩阵(或为局中人 II 的支付矩阵)。由于假定对策为零和的,故局中人 II 的赢得矩阵就是 A 。 当局中人 I 、 II 和策略集 1S 、 2S 及局中人 I 的赢得矩阵 A 确定后,一个零和对策就给定了,零和对 策又可称为矩阵对策,并可简记成:  1 双方都应考虑到对方有使自己损失最大的动机。  G S S A  ; , 2 定义 1 鞍点 ) 设 ( , y B ,有 f x y 为一个定义在 A y B 及 x  上的实值函数,如果存在  x   , A y  使得一切 x A 和 B ( , f x y  )   ( , f x y  )   ( , f x y ) (2.2) , x y  为函数 f 的一个鞍点。 ) 则称 ( Mathematica 画图说明鞍点 定义 2 赢得矩阵的鞍点 设  G S S A   ; , 1 2 a   i j )  相对应的元素 i V  成立,记 G 阵中与 ( , j  定理 1 极大极小原理 ,记  G S S A   设  ; , i 1 2 , , S 1  , 1  为矩阵对策,其中  max min j      2 m min max a a ij ij  S     1 2 n a    i j , ,则称 GV 为对策G 的值,使式成立的纯局势 ( j  (2.3) )  为对策G 鞍点或稳定解,赢得矩 ja   称为赢得矩阵的鞍点, i 和 j 分别称为局中人 I 与 II 的最优纯策略。  , A  ( ) a ij n m  。若等式  , , , , 2 j i i i max min ij a   , min max ij a i j j i ,则必有    0 定理 2 零和对策解的判定 零和对策G 具有稳定解的充要条件是    0
2.2 零和对策的混合策略 定义 3 混合策略 设局中人 I 用概率 ix 选用策略 ia ,局中人 II 用概率 jy 选用策略 j ,   1( x , x 那么 , x m )T , y   1( y , , y n )T ,则局中人 I 的期望赢得为 ( , E x y )  y j  1 ,记 n m  x i   1 i  T x Ay 。 1  j 1 :S  策略 概率 , m 1,   1, x , m x :S  策略 2 概率 1,   n , 1, y , y n 分别称 1S  与 2S  为局中人 I 和 II 的混合策略。一般的记法如下: , m 0, ) | T {( 1,    i , ,    S 1 x m x 1 x i ; S  2  {( y 1 ,  , y n ) | T y j  0, j  1,  , ; n m  i 1  n  j 1  x i  1} y j  1} 定义 4 混合策略对策问题的鞍点 若存在 m 维概率向量 x 和 n 维向量 y ,使得对一切 m 维向量 x 和 n 维向量 y 有 T x Ay x y 为混合策略对策问题的鞍点。 ) 则称 ( , 定理 3 鞍点的判定 设 x S  , 1 y S  ,则( , 2  max x T x Ay  min y T x Ay 的解的充要条件是: 2 1 , ;    ) x y 为 G S S A  n      T x Ay T x Ay a x ij i a y ij  1  m   1  j j i , i , j  1,2,  , m  1,2,  , n 定理 4 鞍点的存在性 任意混合策略对策问题必存在鞍点,即必存在概率向量 x 和 y ,使得: T x Ay 下面是三个关于零和对策解集的定理,设零和对策G 的解集为 ( T G T x Ay min y T x Ay max   x ) 定理 5 加法律 设两个零和对策 G 1   S S A G 1 2 ; , , 2 1  (2.4) (2.5) 定理 6 乘法律 设两个零和对策 G 1   S S A G 1 2 ; , , 2   { }, a ij A 2  { a ij  }, L L 为任一常数。则  2 ;   , S S A 2 1 (i) V V  G G 2 1 ) (ii) ( T G  1 A ,其中 1 L  ( T G 2 ) 0 为任一常数。则   , S S 1 2 (i) V G 2 (ii) ( T G 1  ; A ,其中 V  G 1 ) T G  2 ( ) 定理 7 对称律  G S S A 设   ; , 1 2 为一零和对策,且 A A  为反对称矩阵(亦称这种对策为对称对策)。则 T
GV ( T G T G 1 T G 为局中人 I 和 II 的最优策略集。 (i) (ii) 0 )   ) ( 2 ) ) T G 和 2( 其中 1( 2.3 零和对策的线性规划解法 2m  且 2n  时,通常采用线性规划方法求解零和对策问题 当 局中人 I 选择混合策略 x 的目的是使得  T x Ay T x Ay  max min y x max min y x ( T x A n  j 1  y e j j ) max min  y x n  j 1  E y j j 其中 je 为只有第 j 个分量为 1 而其余分量均为零的单位向量, y  E y j  0( jy , 在 1  j n n j j min Y j 1  于 j  时达到最小值u ,故 x 应为线性规划问题。 k ) E j  T x Ae j 。记 u E k   min j E j ,由 a x ij i  , u j  1,2,  , n  E 即 j  E k  1 u m  ky  , max        1 i    x i   . . s t 1  m x i i  1 0, i  1,2,  , m (2.6) (2.7) (2.8) 解。 同理, y 应为线性规划 max          . . s t v n  j 1  n  1 j  y j a y ij j  , u i  1,2,  , m y j  1  0, j  1,2,  , n 由线性规划知识,和两个互为对偶线性规划,它们具有相同的最优目标函数值。 不妨设 0u  ,对变换 则线性规划问题化为 x ' i  x i u , i 1,2,   , m m  i 1  m  1 i  ' x i min . . s t      x ' i a x ij ' i  1, j  1,2,  , n  0, i  1,2,  , m 同理,对作变换 则线性规划问题化为 y ' j  y j v , j 1,2,   , n
max y ' i m  1  i n . . s t       1 j  ' y j a y ij ' j  1, i  1,2,  , m  0, j  1,2,  , n (2.9) 三、双矩阵对策 双矩阵对策又叫二人非常数和对策。 所谓常数和对策是指局中人 I 和局中人 II 所赢得的值之和为一常数。显然,二人零和对策是二人常数 和对策的特例,即常数为零。 对于二人常数和对策,有纯策略对策和混合策略对策,其求解方法与二人零和对策是相同的。二人非 常数和对策也称为双矩阵对策。也有纯策略对策和混合策略对策两种策略。 3.1 纯策略问题 囚徒困境是一个典型的二人非常数和对策,每人的赢得矩阵是不相同的。 对于一般纯策略问题,局中人 I 、 II 的赢得矩阵如表 2 所示。其中局中人 I 有 m 个策略 1  , , , m 局中人 II 有 n 个策略 1 1 ( C  { , 1 n  G S S C C  1 )ij c m 1 , , 2 n  , , ,分别记为 { , S    = 1 1 m 为局中人 I 的赢得矩阵, 2 2 )ij ( C c  2 } , = 2 , } { ,   1 n }, S 为局中人 II 的赢得矩阵。因此,双矩阵对策记为  m  n 表2 ) ) ( 1 c 22 2 , c 22  2 , c m 1 2 , c 11 1 c 11 ( ) ( 2 1 2 , c c 12 12 ( 1 c 21 ) 2 , c 21  2 , c 1 m ( 1 c 1 m ) ( 1 c m 2 ) 2 策略 1 2  m      min max j i n 2 , c 1 n 1 c 1 n ( ) ( 1 c 2 n 1 c mn 2 , c 2 n  2 , c mn ) ) ( 2 c ij 定义 5 双矩阵对策的 Nash 平衡点 设 G S S C C { , 1  , , 2 1 2 } 是一双矩阵对策,若等式 1 c   j i  min max 1 c ij 2 , c   j i  j i (3.1) )  为 成立,则记 v 1  1 c   i j ,并称 1v 为局中人 I 的赢得值,记,并称 2v 为局中人 II 的赢得值,称 ( j  , i G 在纯策略下的解(或 Nash 平衡点),称 i 和 j 分别为局中人 I , II 的最优纯策略。 实际上,定义 5 也同时给出了纯策略问题的求解方法。 因此,对于囚徒困境的例子, ((1,0),(1,0)) 是 Nash 平衡点,这里 (1,0) 表示以概率 1 取第一个策略, 也就是说,坦白是他们的最佳策略。 3.2 混合对策问题 如果不存在使式成立的对策,则需要求混合对策。类似于二人零和对策情况,需要给出混合对策的最 优解。 混合对策问题的基本概念 定义 6 非合作平衡点 G S S C C 在对策  } { , 1 , , 1 2 2 中若存在策略对 x  ,  S y 1  使得 S  2
1 T x C y  2 T x C y  , v x y 为 G 的一个非合作平衡点。记 1     ) 1 T , x C y x   2 T , y x C y   1 2, T x C y v    S 1  S 2 2 T x C y (3.2) ,则称 1 2,v v 分别为局中人 I ,II 的 对称 ( 赢得值。 对于混合对策问题有以下三个定理。 定理 8 双矩阵对策非合作平衡点的存在性 每个双矩阵对策至少存在一个非合作平衡点。 定理 9 双矩阵对策非合作平衡点的判定 G S S C C  , , 1 2 } 的平衡点的充分必要条件是 1 c y ij j  1 T x C y , i  1,2, m …, 2 c x ij i  2 T x C y , j  1,2, n …, (3.3) 2 ) 混合策略 ( , x y 为对策 { , 1  n      混合对策问题的求解方法  1  n 1  j i 由定义 6 可知,求解混合对策就是求非合作对策的平衡点,进一步由定理 8 得到,求解非合作对策的 平衡点,就是求解满足不等式约束的可行点。因此,混合对策问题的求解问题就转化为求不等式约束的可 行点,而 LINGO 软件可很容易做到这一点。 举例:对抗赛 有甲、乙两支游泳队举行包括三个项目的对抗赛。这两支游泳队各有一名健将级运动员(甲队为李, 乙队为王),在三个项目中成绩都很突出,但规则准许他们每人只能参加两项比赛,每队的其他两名运动 员可参加全部三项比赛。已知各运动员平时成绩(秒)见表 3。 100 米蝶泳 100 米仰泳 100 米蛙泳 赵 59.7 67.2 74.1 甲队 钱 63.2 68.4 75.5 王 58.6 61.5 72.6 乙队 张 61.4 64.7 73.4 孙 64.8 66.5 76.9 假定各运动员在比赛中都发挥正常水平,又比赛第一名得 5 分,第二名得 3 分,第三名得 1 分,问教 练员应决定让自己队健将参加哪两项比赛,使本队得分最多?(各队参加比赛名单互相保密,定下来后不 准变动) 解 分别用 1 、 2 和 3 表示甲队中李姓健将不参加蝶泳、仰泳、蛙泳比赛的策略, 分别用 1、 2 和 3 表示乙队中王姓健将不参加蝶泳、仰泳、蛙泳比赛的策略。 当甲队采用策略 1,乙队采用策略 1时, 在 100 米蝶泳中,甲队中赵获第一、钱获第三得 6 分,乙队中张获第二,得 3 分; 在 100 米仰泳中,甲队中李获第二,得 3 分,乙队中王获第一、张获第三,得 6 分; 在 100 米蛙泳中,甲队中李获第一,得 5 分,乙队中王获第二、张获第三,得 4 分。 也就是说,对应于策略 1 表 4 给出了在全部策略下各队的得分。 ( )  甲、乙两队各自的得分为 (14,13) 。 , 2 表3 李 57.7 63.2 70.3 表4 策略 1 2 3 1 (14,13) (13,14) (12,15) 计算支付矩阵的 Matlab 程序,运行 2 (13,14) (12,15) (12,15) 3 (12,15) (12,15) (13,14)
按照定理 8,求最优混合策略,就是求不等式约束的可行解, 求解最优混合策略的 LINGO 程序。 求得甲队采用的策略是 1 、 3 方案各占 50%,乙队采用的策略是 2 、 3 方案各占 50%,甲队的平均得分为 12.5 分,乙队的平均得分为 14.5 分。如表 5 所示。 策略 1 0.5 2 0.0 3 0.5 四、N 人合作博弈 1 0.0 (14,13) (13,14) (12,15) 表5 2 0.5 (13,14) (12,15) (12,15) 3 0.5 (12,15) (12,15) (13,14) 五、博弈的扩展式表述和动态博弈 5.1 博弈论的扩展式表述 , n i   ,此外,我们将用 N 来表示虚拟参与人“自然”; 具体来讲,博弈的扩展式表述包括以下要素: 1. 参与人集合: 1, 2. 参与人的行动顺序:谁在什么时候行动; 3. 参与人的行动空间:在每次行动时,参与人有些什么选择; 4. 参与人的信息集:每次行动时,参与人知道些什么; 5. 参与人的支付函数:在行动结束之后,每个参与人得到些什么(支付是所有行动的函数); 6. 外生事件(即自然的选择)的概率分布。 5.2 博弈树的构造 设想你是一家房地产开发商(为了讨论方便,我们称你为“开发商 A”,正在考虑是否要在北京的某一 地段开发一栋新的写字楼。你面临的选择是开发或不开发。如果决定开发,你必须投入 1 亿资金;当然, 如果决定不开发,你的资金投入为 0。在做这个决定时,你关心的当然是开发是否有利可图。 像房地产这样的市场充满了风险。风险首先来自市场需求的不确定性。需求可能大,也可能小。风险 的另一个来源是你的竞争对手,房地产开发商 B。让我们假定开发商 B 也面临与你同样的决策问题:是否 投入 1 亿资金开发一栋同样的写字楼。 假定,如果市场上有两栋楼出售,需求大时,每栋售价可达 1.4 亿,需求小时,售价为 7 千万;如果 市场上只有一栋楼出售,需求大时售价为 1.8 亿,需求小时为 1.1 亿。这样,有以下 8 种可能的结果: 1. 需求大,你开发,他不开发;你的利润为 8 千万,他的利润为 0。 2. 需求大,你不开发,他开发;你的利润为 0,他的利润为 8 千万。 3. 需求大,你开发,他也开发;你的利润为 4 千万,他的利润为 4 千万。 4. 需求大,你不开发,他也不开发;你和他的利润为都为 0。 5. 需求小,你开发,他不开发;你的利润为 1 千万,他的利润为 0。 6. 需求小,你不开发,他开发;你的利润为 0,他的利润为 1 千万。 7. 需求小,你开发,他也开发;你的利润为-3 千万,他的利润为-3 千万。 8. 需求小,你不开发,他也不开发;你和他的利润为都为 0。 在这个例子中,无论开发商 A 还是开发商 B,在决定是否开发时,不仅要考虑市场需求的大小,而且 要考虑对方的行动。 我们假定该博弈的行动顺序如下: (1) 开发商 A 首先行动,选择开发或不开发; (2) 在 A 决策后,自然选择市场需求的大小; (3) 开发商 B 在观测到 A 的决策和市场需求后,决定开发或不开发。
博弈树的基本建筑材料包括结(nodes)、枝(branches)和信息集(information sets)。 结(nodes) 图1 房地产开发博弈I '' , , x x x x 意味着 x 在 ''x 之前。 结包括决策结(decision nodes)和终点结(terminal nodes)两类;决策结是参与人采取行动的时点, 终点结是博弈行动路径的终点。 一般地,我们用 X 来表示所有结的集合, x X 表示某个选定的结。用 表示定义在 X 上的顺序关 系(precedence relation): 定义 ( )P x 为 x 之前的所有结的集合,简称为 x 的前列集(the set of precedene); 定义 ( )T x 为 x 之后的所有结点的集合,简称为 x 的后续集(the set of successors)。 如果 ( ) P x 如果 ( ) T x 除终点结之外的所有结都是决策结。 每一个终点结完全决定了博弈树的路径,我们可以用函数 ,( ) 与人的支付函数。 枝(branches)   称为初始结(initial nodes)   称为终点结(terminal nodes)。 u z 表示对应的博弈路径所导致的第 i 个参 在博弈树上,枝是从一个决策结到它的直接后续结的连线(有时用箭头表述),每一个枝代表参与人 的一个行动选择。 一般地,对于一个给定的决策结, x X ,存在一个有限的行动集合 ( )A x 和一个一一对应的函数 : ( ) a t x t x 是 x 直接后续结的集合。 ,这里 ( ) ( ) A x 信息集(information sets) 博弈树上的所有决策结分割成不同的信息集。每一个信息集是决策结集合的一个子集。该子集包括所 有满足下列条件的决策结: (1) 每一个决策结都是同一参与人的决策结; (2) 该参与人知道博弈进入该集合的某个决策结,但不知道自己究竟处于哪一个决策结,引入信息 集的目的是描述下列情况:当一个参与人要作出决策时他可能并不知道“之前”发生的所有事 情。 为了给出信息集的直观解释: 在图 1 中,假定开发商 B 是在知道 A 的选择和自然的选择之后决策的,此时,博弈树的 7 个决策结分 割成 7 个信息集,其中一个(初始结)属于 A,两个属于 N,四个属于 B;每个信息集只包含一个决策结, 意味着所有参与人在决策时准确地知道自己处于哪一个决策结。 如果对上述假设作一个小小的改动,假定行动顺序不变,但 B 在决策时并不确切地知道自然的选择。 此时,B 的信息集由原来的四个变成两个,每个信息集包含两个决策结。两个信息集分别对应着 B 必须作 出的两个不同的决策:如果 A 开发,自己开发;如果 A 不开发,自己是否开发。在图 2 中,我们用虚线将 属于同一信息集的两个决策结连接起来(或用虚线圈起来)。
分享到:
收藏