《合作博弈》PPT课件.ppt

《《合作博弈》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章多人合作博弈模型一、问题引入二、多人结盟博弈的基本概念三、多人结盟博弈的解四、常用解法一、问题引入例1：（爵士乐队博弈，AJazzBandGounce）一位歌手（S），一位钢琴家（P）和一位鼓手（D）组成一个小乐队在俱乐部同台演出能得到演出费1000元，若歌手和钢琴家一起演出能得800元。而只有钢琴家和鼓手一起演出能得到650元，钢琴独奏表演能得300元，钢琴家没有其它收入。然而，歌手和鼓手在地铁中表演能挣500元，歌手独奏可以从TheTerasses挣200元，而鼓手单独什么也挣不到。问题：如何在

2、这三人爵士乐队中合理分配共同演出费1000元？例2：成本分摊问题（ACostGame）三个城镇A，B，C欲与附近的一座电站连接起来，其可能的线路及其成本如下网络图表示：这三个镇可相互联合建设，试问如何在这三个小镇合理分摊这笔建设费？ABC二、多人结盟博弈的基本概念多人结盟博弈：局中人多于二人时的博弈称为多人博弈。这种博弈中如果局中人可以和其它局中人联合成一体统一行动与其它局中人对抗，这种博弈称为多人结盟博弈。这种博弈有三个基本要素:局中人N＝{1,2,…,n}；结盟S；特征函数V（S）。一般可用

3、表示一个多人结盟博弈。1、局中人与结盟（1）N＝{1,2,…,n}表示局中人集合。（2）结盟S，表示一个联盟，即一局多人对策中，一部份局中人联合成一体像一个“局中人”一样选择策略，这种联合称为结盟。显然结盟S是局中人集合N的子集，SN。（3）2n是局中人可能形成结盟的个数。2、特征函数V(S)（1）V(S)表示当若干局中人联合成一个结盟S时,在这局博弈中能获得的最大收益值,即当形成结盟S,只要S内每一个局中人共同策略,选择相应策略结盟S能保证获得,而与联盟外局人采用什么策略无关。若S=,V()=0。

4、（2）超可加性若一个多人博弈的特征函数具有下列性质,即对任意结盟S,TN,S∩T=,满足V(S∪T)≥V(S)+V(T).称这个多人博弈具有超可加性。如果特征函数不满足超可加性，博弈中的结盟是不稳定的。例1：（爵士乐队博弈，AJazzBandGounce）一位歌手（S），一位钢琴家（P）和一位鼓手（D）组成一个小乐队在俱乐部同台演出能得到演出费1000元，若歌手和钢琴家一起演出能得800元。而只有钢琴家和鼓手一起演出能得到650元，钢琴独奏表演能得300元，钢琴家没有其它收入。然而，歌手和鼓手在地铁中

5、表演能挣500元，歌手独奏可以从TheTerasses挣200元，而鼓手单独什么也挣不到。问题：如何在这三人爵士乐队中合理分配共同演出费1000元？这个问题可归为一个三人合作博弈，它的特征函数V（S）为：很容易验证此博弈是具有超可加性的。结盟S{S,P,D}{S,P}{S,D}{P,D}{S}{P}{D}V(S)10008005006502003000例2:（产品博弈AProductionGame）从M1、M2、M3、M4四种原材料中各取一个单位能生产1个单位的某种产品，这个产品的价格要比它的原材料成本高

6、出1000元，现有三个人，他们拥有这四种材料情况如下表:问：若这三人联合起来生产这种产品，他们之间该如何分配所得利润？原材料人M1M2M3M411/21/20021/2010301/201将此问题转化为三人博弈，其特征函数如下：局中人2，3，通过合作生产，但由于他们共有四种原材料只能生产1/2个单位产品，所以能挣500元。S{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}V(S)0000005001000例3：成本分摊问题（ACostGame）三个城镇A，B，C欲与附近的一座电站连接起来，

7、其可能的线路及其成本如下网络图表示：这三个镇可相互联合建设，试问如何在这三个小镇合理分摊这笔建设费？ABC这个问题的合作博弈对，N={A,B,C}，成本分摊博弈的特征函数V(S)为成本节省，如下表：博弈的特征函数值V(S)，由下式得出S{A}{B}{C}{A,B}{A,C}{B,C}{A,B,C}C(S)0100140130150130160150V(S)00009010011022022090110100Ａ0Ｂ0Ｃ0150150130160Ａ100Ｂ140Ｃ130三、多人结盟博弈的

8、解多人结盟博弈的解的概念多人结盟博弈中，每个局中人都希望通过结盟的形式去得到更多，而博弈解的问题是如何合理确定这局博弈中每个局中人的分配收益，博弈解一般用X＝(x1,x2,…xn)表示n个局中人的得失向量，xi表示第i个局中人之所得。1、合理分配（Imputation）作为一个博弈的解X，即在博弈中对N个局中人得失的合理分配，至少应满足两个条件：（1）（个人合理性）（2）（集体合理性）条件（1）称为：“个人合理性”（Indiv