9.合作博弈.ppt

第7章 合作博弈COOPERATIVE GAMES 熊、狼、狐狸一起抓了一只兔子，民主协商如何分配。狐狸对熊说：平均分只能各得1/3，这样吧，我们俩联合起来，平分如何？熊要答应，狼急了，于是狐狸对狼说：怎么样，我和熊联合起来可以让你什么也得不到，我可以和你合作，不过我要3/4。狼感激的点头，熊琢磨过味来，对狼说：别听那个两面三刀的，和我合作，我给你1/3。狐狸见势不妙，对狼说：别，我给你2/3，我只要1/3。狼成了抢手货，正得意，没留神狐狸和熊又开始嘀咕起来，有再次把自己晾在一边的不妙趋势，连忙钻去继续讨价还价。结果呢？ 青山原不动，白云自去来 如果在实际博弈问题中，具有有力的保障使局中人能够进行协商、谈判，联合选择行动，共同分享利益，我们就面对一个合作博弈问题。本章通过合作博弈模型的介绍，讨论在合作博弈中，局中人如何进行协商谈判、结成联盟及分享利益。 1、纳什讨价还价问题 略） 2、联盟博弈 3、联盟博弈的分配 4、核和稳定集 5、沙普利值 合作博弈的意义与构成 合作博弈的意义表现在它与非合作博弈的差别上。如果协议有外在力量保证强制执行，则为合作博弈，否则为非合作博弈。 非合作博弈的重点是在个体，是每个局中人该采用什么策略；强调个体理性（individual rationality） 合作博弈的重点则在群体，讨论何种联盟将会形成，联盟中的成员将如何分配他们可以得到的支付；强调群体理性 group rationality 合作：为共同的目的而一起行动 需要一个描述集体理性的效用函数。 描述n人合作博弈，通常假设合作博弈具有可传递效用。简单地说，该效用就像货币一样，可以在各局中人之间自由转让。 （合作，人类进化之舟。） 7.2 具有可转移支付的联盟博弈 7.2.1 具有可转移支付的联盟博弈及分类 具有可转移支付的 人合作博弈 在非合作的 人博弈中，局中人之间不允许事先协商如何选择策略，不允许他们把策略结合起来，不允许局中人对得到的支付重新分配，一个局中人不能分享另一个局中人的支付，或支付是不可能转移的。 本章所讨论的 人合作博弈对上述问题都不加限制。局中人在选择策略时可以协商，并且局中人的支付可以相互转让，或支付是可以转移的。在具有可转移支付的 人合作博弈中，局中人如何选择自己的策略已不是主要讨论的问题，我们主要讨论的问题是局中人如何分配通过合作所获得的收益或效用。 联盟与特征函数 设局中人集合 ，称 的任一子集为一个联盟。为方便，把 的空子集 也视为一个联盟。记所有联盟构成的集类为 。对 ，用 表示联盟 中的局中人通过合作所能获得的最大支付。且可认为这个值与 中的局中人的行为是独立的，因而 是定义于 上的函数，即 。 定义7.2 对于局中人集合 的任一子集 ，给定集合 的支付 ，如果 满足 ,则称 为特征函数，称 为具有可转移支付的联盟博弈。 若 满足对 ， ，有 ，则说 满足超可加性。 下面讨论的联盟博弈都是指具有可转移支付的联盟博弈。特征函数满足超可加性。 例7.1 局中人1（卖主）要把一件物品卖掉，局中人2和3（买主）分别出价9元和10元。如果局中人1将物品卖给局中人2的要价是 x 元，则局中人2赢利 9-x 元。联盟 的总收益为9元。类似，联盟 的总赢利为10元。于是有 。 另一方面，单个局中人或者两个买主在一起都不可能赢利，即 ， 。 当三个局中人在一起交易时，局中人1显然要把物品卖给局中人3，从而 v 1,2,3 10， 显然满足超可加性，于是我们建立了联盟博弈 。 特征函数是研究联盟博弈的基础，确定特征函数过程实际就是一个建立合作博弈模型的过程。有的问题，特征函数可以容易地得到，有的问题需要仔细分析，甚至需要一些专业知识。 若对 ， ，都有 ,则称 满足可加性。 我们可以给出满足可加性的特征函数的例子。 例7.2 在某项工作中，不熟练工人 可获报酬 元，熟练工人可得报酬 元，于是可以定义特征函数 。 这里 表示集合 中的局中人个数，以后也用这种记法。 小知识：中国参与环保组织的志愿者约30万人，美国有60%，欧洲有50%的人参与。参与环保，保护共同家园，需要我们合作，如二氧化碳排放，如如何保护森林。当前，最大的善，不是施舍，而是节约资源！ 7.3 联盟博弈的分配 转归或分配的定义 在联盟博弈中局中人通过合作，获得一定的联盟支付，联盟还要将这笔支付转归于每个局中人，联盟博弈中每个局中人 从联盟中所获的支付或转归可用 维向量 表示，这里 为局中人 所得到的支付。 定义7.3 称向量 是联盟博弈 的一个转归或分配，如果 满足 （1） ， （2） 。 （1）式表明n个局中人的支付总和应与他们全体构成一个联盟所获的支付相等。这说明如果要使