第11讲合作博弈.ppt

方案1： a：70％，b：0，c：30％。这个方案能被a、c接受，因为对a、c来说这是一个比按票力分配方案有明显改进的方案，尽管b被排除出去，但是a、c的票力构成大多数(60％)。 方案2： 在这样的情况下，b会向a提出这样一个方案，a：80％，b：20％，C：0 。此时a和b所得均比刚才C提出的方案要好，但C成了一无所有，但a、b票力总和构成大多数(90％) 方案N 在这个过程中，理性的人会形成联盟ab，ac或abc,但哪个联盟能够形成呢？最终的分配结果应该是怎样的呢？ 夏普里值是先验实力的一种度量，我们可以根据夏普里值来划分财产。按照夏普里值我们可以将财产分给 　 a：4／6 ， b：1／6， ? c：1／6， 根据夏普里值定义，所有排列的顺序是等可能的。而在每一个排列下，每个参与者对这个排列的联盟有一个边际贡献。 这样，夏普里值所反映的是参与考在各种可能下的影响程序”。在投票博弈中，这个值反映的是参与者与其他参与者结成联盟的可能性．因此夏普里反映的是参与者的“权力”。 优点：公正、合理，有公理化基础。 如n个单位治理污染, 通常知道第i方单独治理的投资yi 和n方共同治理的投资Y, 及第i方不参加时其余n-1方的投资zi (i=1,2, …n). 确定共同治理时各方分担的费用。 其它v(s)均不知道, 无法用Shapley合作对策求解 Shapley合作对策小结 若定义特征函数为合作的获利(节约的投资)，则有 缺点：需要知道所有合作的获利，即要定义I={1,2,…n}的所有子集(共2n-1个)的特征函数，实际上常做不到。 * 蔡树彬 shubin@szu.edu.cn66162） 科技楼1406 * 为什么现实生活中并不总是出现“囚徒困境”？ * 合作博弈 二人合作博弈 讨价还价 多人合作博弈 联盟 二人合作博弈 给两个人100元，他们应该如何分配？ 静态博弈 (1,99)(2,98)…(99,1)都是Nash均衡 动态博弈 多阶段讨价还价 可行分配的集合 S={(s1,s2)|s1+s2=100,s1=0,s2=0} 破裂点d、效用函数u Nash的公理化方法，不去问如何求得最后的(s1,s2)，而是问(s1,s2)有什么性质（满足什么公理）？ 联盟博弈 3个人分300块 Nash解: (100,100,100) 垃圾博弈 海盗分金 5个海盗100块金币，如果海盗之间可以结盟，那么最终结果是什么？ 怎样找出一个合理的分摊原则，以保证合作的实现呢？ N人合作对策模型 设有一个n人的集合I={1,2,…,n}，其元素是某一合作的可能参加者。 (1)对于每一子集S I，对应地可以确定一个实数V(S)，此数的实际意义为如果S中的人参加此项合作，则此合作的总获利数为V(S)，十分明显，V(S)是定义于I的一切子集上的一个集合函数。根据本问题的实际背景，还应要求V(S)满足以下性质: =0（没有人参加合作则合作获利不能实现） 对一切满足 的S1、S2成立 具有这种性质的集合函数V（S）称为I的特征函数。 (2)定义合作结果V（S）的分配为 ，其中 表示第i人在这种合作下分配到的获利。显然，不同的合作应有不同的分配，问题归结为找出一个合理的分配原则 来， 被称为合作对策 是否存在合理分配原则 夏普里值 夏普里提出一种计算权力的度量方法，用于衡量博弈方的先验实力。根据该理论求得的联盟先验实力被称之为夏普里值。 在各种可能的联盟次序下，参与者对联盟的边际贡献之和除以各种可能的联盟组合（边际贡献就是谁是联盟的关键加入者）。 夏普里值是合作博弈(或联盟博弈)中最重要的概念。 Shapley提出了以下公理： 设V是I上的特征函数， 是合作对策，则有 公理1 合作获利对每人的分配与此人的标号无关。 公理2 ，即每人分配数的总和等于总获利数。 公理3 若对所有包含的i的子集S有： V(S-{i})=V(S)， =0。 即若第i人在他参加的任一合作中均不 作出任何贡献，则他不应从合作中获利 公理4 若此n个人同时进行两项互不影响的合作，则两项合作的分配也应互不影响，每人的分配额即两项合作单独进行时应分配数的和。 公平的收益分配 I. 对称性. 一个分配方案应与成员的编号无关. II. 有效性. 对于每次合作中均无贡献者,不应从合作的效益中得