信息与博弈

Size: px

Start display at page:

Download "信息与博弈"

由钮卞
5 years ago
Views:

1 信息与博弈校通识课 GEN14251L 天津师范大学计算机与信息工程学院张少强

2 静态和动态博弈如果说运筹帷幄的一半是料事如神, 那另一半是知己知彼了静态博弈, 参与人大都假设为同时行动动态博弈中, 参与人依次行动, 第二个参与人在决策之前就已经获得第一个参与人如何行动的信息在动态博弈中, 信息成核心问题

3 第三讲信息 (Information) 与动态博弈在前一讲中, 大多数博弈都假定参与人同时行动, 因此没有机会观察其他参与人的行动来获取对方的私人信息, 但是一旦参与人依次行动, 信息成核心问题因为后行动的能获得前行动者的如何行动的信息本讲主要考虑序贯行动博弈 (sequential-move games)

4 3.1 博弈建模方式 : 策略式和扩展式策略式博弈顺序扩展式博弈树

5 策略式 : 跟随领头羊 I ( 张三, 李四 ) 李四押大押小张三押大 2,2-1,-1 押小 -1,-1 1,1 现在我们假设张三先行动 ( 张三的策略就是行动 ), 那李四的策略就不是单一的行动了这个例子我们称为跟随领头羊 I 李四的策略集 ={A:( 若张三押大则押大 ; 若张三押小则押大 ), B:( 若张三押大则押大 ; 若张三押小则押小 ), C:( 若张三押大则押小 ; 若张三押小则押大 ), D:( 若张三押大则押小 ; 若张三押小则押小 )}

6 策略式 : 跟随领头羊 I 策略 X 策略张三 A ( 大大, 大小 ) 李四 B ( 大大, 小小 ) C ( 小大, 大小 ) 大 2,2 ( 均衡 ) 2,2 ( 均衡 ) -1,-1-1,-1 D ( 小大, 小小 ) 小 -1,-1 1,1-1,-1 1,1 ( 均衡 ) 策略式 ( 标准式 ): 由全部可能的策略组合, 分别映射到支付向量上支付函数 ( 张三, 李四 ) 行动 X 行动李四押大押小张三押大 2,2-1,-1 押小 -1,-1 1,1 结果矩阵 (outcome matrix): 所有可能的行动组合, 分别映射到结果向量上的结果函数

7 博弈顺序 : 跟随领头羊 I 对序贯博弈建模更简便的方式 : 依据博弈顺序 : 对于跟随领头羊 I : 博弈顺序为 1, 张三选择大或者小 ; 2, 李四选择大或者小策略式描述序贯动态博弈比较复杂, 很少用于复杂的建模尽量少用

8 另外建模方法 : 扩展式 ( 博弈树 ) 构成要素 : 结点 (node): 某参与人或自然采取行动的时点或者博弈结束的时点后续结点 (successor) 前续结点 (predecessor) 起点 (starting node) 终点 (end node) 枝 (branch): 就是边 (edge) 代表一个连接两结点的行动路径 (path): 起点到终点结点 1 枝结点 2

9 扩展式 ( 博弈树 ) 跟随领头羊 I 博弈 : 小 (1,1) 张三 Z 小大 L1 L2 李四大小大 (-1,-1) (-1,-1) (2,2) 终点标注每个参与人的支付就是扩展式, 终点标注博弈的结果就是博弈树

10 信息集协调博弈 ( 张三和李四同时行动 ): 小 (1,1) 张三 Z 小大 L1 L2 李四大小大 (-1,-1) (-1,-1) (2,2) 因为同时行动, 李四的 L1 和 L2 节点, 李四的信息集就是 {L1, L2}, 把同一信息集的节点用虚线连接

11 信息集 ( 虚线表示 ) 协调博弈树的虚线表明李四的知识在张三行动后仍保持不变李四所知道的仅仅是博弈已经达到了由虚线围成的信息集内的某个结点, 但至于到了哪个结点, 他则不知道所以是同时的 : 通过张三先行动, 但不让李四知道他采取了何种行动来实现这一点

12 3.2 信息集与信息分割参与人在特定时点的信息集就是在博弈树上参与人认为博弈可能已经到达的结点的集合信息集就是要搞清楚参与人在什么时候知道什么 ( 知道多少 ) A B C D A, B,C,D 是在一个时点的 4 个结点,C 和 D 组成一个信息集 {C,D},A 自己一个信息集,B 自己一个信息集 ; 信息分割 {A},{B},{C,D}

13 信息分割 : 信息分割成信息集显然信息集分割的越细越好, 只有一个结点的信息集称为单结点的 (singleton) 显然若都是单结点的, 信息集分割的最细, 在对应时点参与人掌握的信息最全例如 :A,B,C,D 四个结点, 信息分割 {A, B,C,D} 是最粗的, 而 {A},{B},{C},{D} 是最细的

14 共同知识 (common knowledge) 我们一般假定参与人知道博弈树是什么样子, 我们同样也假定参与人知道其它参与人知道博弈树的样子, 这就是共同知识共同知识 : 如果某个信息是所有参与人都知道的, 每个参与人都知道所有参与人知道这一信息, 每个参与人都知道所有参与人知道所有参与人知道这一信息如此这般无穷下去, 这个信息便是共同知识信息分割应该在建模时称为共同知识

15 共同知识举例 : 脏脸博弈一个屋子有三个人, 脸都很脏, 但不知道自己脏, 屋外进来一个人对他们说你们中至少一个人脏, 他们没有反应, 那人又说你们知道吗? 过了一会儿, 三个人脸都红了, 意识到自己脸脏共同知识在变化, 开始至少一个人脸脏是共同知识,( 若只有一个人脸脏, 那脸脏的人看到两个干净脸的人, 自己马上脸红, 但没人脸红, 所以 ) 共同知识变为至少有两个人脸脏, 此时仍没人脸红,( 若自己脸干净, 那另外两个人看到的一定是一脏一干净, 他们会脸红, 但他们没有脸红 ), 说明共同知识变为三个人脸都脏

16 3.3 信息的分类完美 (perfect) 信息 : 每个信息集都是单结点的否则就是不完美的确定 (certainty) 信息 : 自然不在任一参与人行动之后行动否则为不确定信息对称 (symmetric) 信息 : 没有参与人在行动时或在终点有与其他参与人不同的信息, 没有信息上的优势否则就是不对称不完全 (incomplete) 信息 : 自然首先行动且它的行动对某参与人是不可观测的否则为完全信息

17 完美信息跟随领头羊 I 博弈 : 小 (1,1) 张三 Z 小大 L1 L2 李四大小大 (-1,-1) (-1,-1) (2,2) 完美信息意味着没有任何两个参与人同时行动, 并且所有后行动者能确切知道先行动者选择什么行动, 所有参与人能观测到自然的行动, 在博弈树上, 没有被虚线围成的信息集

18 完全信息完全信息意味着, 博弈中的每个参与人对所有其他参与人的支付函数有完全的了解, 并且所有参与人知道所有参与人的支付函数, 支付函数是所有参与人的共同知识 ( 所有人都知道博弈规则 ) 但是现实许多博弈并不满足完全信息的要求比如 : 当你与一个陌生人打交道, 你并不知他的偏好 ; 当一个企业进入某个市场, 它不知道已进入市场的企业的成本函数就是说, 在不完全信息博弈中, 至少有一个参与人不知道其他参与人的支付函数

19 不完全信息博弈转化为完全信息博弈 : 海萨尼转换第一讲举过的例子干洗店博弈, 新干洗店要开业, 并不知道现在市场行情是不是景气 ( 但老店知道行情 ), 也不知道老店是不是会打价格战 ( 新店, 老店 ) 老店降价老店原价新店开业 (-10,-5) (10,10) 新店不开 (0,5) (0,30) 经济景气 ( 单位 : 万元 ) ( 新店, 老店 ) 老店降价老店原价新店开业 (-16,-11) (4,4) 新店不开 (0,-1) (0,24) 经济不景气 ( 单位 : 万元 )

20 干洗店博弈 II 在这个新的博弈中, 新店关于老店的信息是不完全的, 但老店知道新店是在景气还是不景气时开张的这是新店好像是在跟两个不同的老店在竞争, 一个景气老店, 一个不景气老店在 1967 年以前, 博弈专家认为这样的不完全信息博弈是没法分析的, 因为新店也不知道在跟哪个状态下的老店博弈因此, 海萨尼 (Harsanyi) 提出了处理不完全信息博弈的方法, 引入虚拟参与人自然 (Nature)

21 开老 1 原价 (10,10) 自然景气 p 新 1 不开老 2 低价原价低价 (-10,-5) (0,30) (0,5) 不景气 1-p 新 2 开不开老 1 老 2 原价低价原价低价 (4,4) (-16,-11) (0,24) (0,-1)

22 海萨尼转换有了海萨尼转换, 当我们再说不完全信息时, 指的就是经过转换后的完全但不完美博弈了不完全 (incomplete) 信息 : 自然首先行动且它的行动对某参与人是不可观测的否则为完全信息

23 信息分类 : 扑克牌例子在下面的扑克牌游戏中, 参与人堵谁你能摸到最好的牌 ( 例如 : 德州扑克 ), 摸牌的次序事先定好的所有的牌都被洗成面朝上完美 / 确定所有的牌都被洗成面朝下且参与人在下注前甚至不能看自己的牌不完全 / 对称 / 确定所有的牌都被洗成面朝下且参与人只能看他自己的牌不完全 / 不对称 / 确定

24 信息分类 : 扑克牌例子所有的牌都洗成面朝上, 但每个参与人随后都用手挡住牌并悄悄丢掉一张牌完全 / 不对称 / 确定所有牌都洗成面朝上, 接着参与人下注, 然后每个参与人再得到一张面朝上的牌完美 / 不确定所有的牌都洗成面朝下, 随后每个人都抓起牌但不看牌, 将牌亮给其他人看 ( 印第安扑克 ) 不完全 / 不对称 / 确定

25 一个完全信息动态博弈的例子海盗分金币博弈问题有 5 个亡命之徒在海上抢到 100 枚金币, 他们决定通过一种民主的方式分配这笔财富投票规则如下 :5 个海盗通过抽签决定每个人提出分配方案的次序, 先由排序最靠前的海盗提出一个分配方案, 如果有半数或半数以上的人赞成, 那就按这个海盗提出的分配方案分配 ; 否则提出该方案的海盗就被扔进大海再由下一个海盗提出分配方案, 若半数赞成就按照方案分配, 否则也被扔进大海, 依次进行

26 海盗分金币博弈问题每个海盗都想在保全自己生命安全的前提下获取自己最大利益试问在这种前提下最后的分配结果是什么? 从直觉上看, 最先提出分配方案的海盗所处的位置最不利, 因为其他的海盗可能通过将其扔进大海里减少分配金币的人数, 从而使自己获得更多的金币但从完全信息动态博弈来分析, 所得的结论将与我们的直觉完全不同

27 方法 : 逆向归纳法 S i =(x 1 i, x 2 i, x 3 i, x 4 i, x 5 i ) 第 i 个海盗的分配方案首先考察最后一个海盗 5 提出的分配方案时的情况前 4 个海盗肯定已经被扔进大海海盗 5 会选择 S 5 =(0,0,0,0,100) 向前递推一次分析, 当轮到海盗 4 提出方案时, 前 3 个海盗肯定已经被丢到大海喂鱼了, 这时无论海盗 5 赞成与否, 集体投票赞成的票会达到半数, 海盗 4 提出的分配方案最终将被实施 S 4 =(0,0,0,100,0)

28 逆向归纳法继续前推, 若轮到海盗 3 做决定, 前 2 个海盗肯定丢大海里了这时候只有海盗 3,4, 5 在船上海盗 3 知道如果他的方案被否决, 海盗 4 肯定会提出他的分配方案 S 4 =(0,0,0,100,0) 那么海盗 5 将什么也得不到现在只要他给海盗 5 一个金币, 海盗 5 将赞成这个方案这样赞成的票将会大于半数, 海盗 3 的分配方案 S3=(0,0,99, 0,1)

29 逆向归纳法继续前推, 轮到海盗 2 做决定, 海盗 1 被丢到大海, 船上有海盗 2,3,4,5. 海盗 2 知道, 如果自己的方案被否则, 海盗 3 会提出 S 3 =(0,0,99,0,1) 方案这时海盗 4 得不到该方案于是只有他提出的方案使海盗 4 的收益增加, 海盗 4 就赞成该方案, 且投票会达到半数同意海盗 2 的方案 S 2 =(0, 99, 0, 1, 0)

30 最终方案最后, 考察海盗 1 如何决定一旦海盗 1 的方案被否决, 就是执行海盗 2 的方案 S 2 =(0, 99, 0, 1, 0) 于是海盗 1 只要海盗 3 和海盗 5 的收益大于海盗 2 的方案, 海盗 3 和 5 就会赞成该方案于是海盗 1 的方案为 S1=(98,0,1,0,1)

31 博弈树

32 问题剖析海盗 1 看似最危险, 但具有先发制人的优势海盗 5 看似最安全, 坐收渔人之利, 但其威胁不可置信, 不得不看人脸色行事海盗分金币的例子可以解释很多社会现象例如 : 企业的一号人物总会抛开二号人物, 而跟小人物关系好, 小人物好收买, 而二号人物总会野心勃勃想取而代之

33 动态博弈参与人的行动有先后次序, 后行动者在行动前能观测到先行动者的行动信息, 这是动态博弈与静态博弈的根本区别表述一个动态博弈? 扩展式 ( 博弈树 ) 怎样推测动态博弈中参与人的博弈行为? 用什么方法确定动态博弈的纳什均衡? 逆向归纳法

34 扩展式的主要要素参与人集合 ( 包括自然 Nature) 参与人的行动顺序参与人的行动空间 : 每次行动参与人可选择的行动策略参与人的信息集参与人的支付函数自然选择的概率分布

35 博弈树由结点枝信息集三个基本要素组成的动态博弈的扩展式表述常常用博弈树表示终点结点支付函数枝行动起点到终点的一条路径 : 参与人行动次序决策结点 : 信息集我们本讲主要用扩展式的博弈树来分析参与人的行动有先后顺序的动态博弈

36 均衡路径如果动态博弈的扩展式表示成博弈树, 那求解动态博弈的纳什均衡就是在博弈树上寻找从起点到终点的均衡路径均衡路径就是在博弈树上均衡所实现的路径跟随领头羊 I 博弈 : 张三 Z 小大 L1 L2 李四小大小大 (1,1) (-1,-1) (-1,-1) (2,2)

37 逆向归纳法先行动的参与人无法观测到后行动参与人的行动和结果, 所以先行动在选择自己的行动时, 会考虑我选择他会选, 我若选他又会选.. 分析动态博弈, 后续阶段的博弈需首先考虑站在未来的立场来选择现在的行动

38 举例 : 军事政治博弈 A 国对 B 国采取敌视政策, 一直试图对 B 国实施打击面对 A 国的态势,B 国采取的应对行动是反击或不反击行动顺序 :A 国先行动 ;B 国观察 A 的行动再选择自己的行动支付 : 1 A 先打击 B 后反击, 双方恶战,A,B 各支付 -2 2 A 先打击 B 不反击,B 丧权,A 支付 2,B 支付 -4 3 A 不打击 B 反击,B 挑事,A 依此借口纠集国际社会打击 B, A 支付 3,B 支付 -5 4 A 不打击 B 不反击, 和平共处, 各自发展经济, 各支付 1 问题 :A,B 两国各会采取怎样的决策?

39 军事政治博弈 : 博弈树反击 (-2,-2) A 国打击不打击 B 国 B 国不反击反击 (2,-4) (3,-5) 不反击 (1,1)

40 军事政治博弈 : 逆向归纳第一步从最后阶段行动的参与人决策开始考虑 ( 首先考虑 B 国的策略 ) A 国打击不打击 B 国 B 国反击不反击反击不反击 (-2,-2) (2,-4) (3,-5) (1,1) 站在 B 的立场考虑, 若 A 打击,B 最优策略是反击 ; 若 A 不打击,B 的最优策略是不反击用标出

41 军事政治博弈 : 逆向归纳第二步考虑次后阶段 ( 前一阶段 ) 行动人的决策打击 A 国不打击 B 国 B 国反击不反击反击不反击 (-2,-2) (2,-4) (3,-5) (1,1) A 选择打击的话,B 一定反击,A 的收益是 -2; A 选择不打击,B 一定不反击,A 的收益是 1. 打击支付是 -2, 不打击支付 1,A 最优策略是选择不打击

42 军事政治博弈 : 逆向归纳第三步 : 找出均衡路径 B 国打击 A 国不打击 B 国反击不反击反击不反击 (-2,-2) (2,-4) (3,-5) (1,1) 均衡路径 : 博弈树上每条枝均标记了的路径 : 参与人最大化各自支付时所选取的策略后的路径均衡路径 :A 国不打击 B 国,B 国也不反击

43 算法步骤总结第一步画出动态博弈的博弈树第二步从最后阶段行动的参与人决策开始考虑第三步考虑次后阶段行动人的决策, 直至确定第一阶段行动人的决策第四步找出均衡路径

信息与博弈

信息与博弈校通识课 GEN14251L 天津师范大学计算机与信息工程学院张少强 http://www.escience.cn/people/sqzhang 课程介绍与考核方式主讲人 : 张少强每周 3 课时 ; 共 11 讲 ;33+1 课时课件下载地址 http://www.escience.cn/people/sqzhang 问题答疑 zhangshaoqiang@tjnu.edu.cn