第七章-合作博弈-《博弈论与经济》-课件

第7章合作博弈7.1纳什讨价还价（谈判）问题7.1.1纳什讨价还价(谈判)问题的解纳什讨价还价（谈判）问题在应用合作博弈分析研究讨价还价或谈判问题时，首先要假设双方有一个谈判的基点或无协议点，即双方不能达成协议时，A可得支付，B可得支付。用S表示A,B经谈判或讨价还价可能得到的全部支付向量的集合，，并且需要以下两个假设。假设1.S的帕累托有效边界h是一条凹曲线，其定义域为闭区间，且存在，使，。易知h是一条严格递减曲线。假设1表明通过谈判可以使参与人效用增加。假设2弱帕累托有效的支付对所构成的集合是闭的。满足以上假设的称为一个纳什讨价还价（谈判）问题。讨价还价或谈判问题的解双方从基点出发，经过谈判或讨价还价，最后所得到的双方都能接受的支付对称为讨价还价或谈判问题的解。纳什公理双方经由谈判最后得到解的过程可以被理解为一个映射：。如何求解呢？纳什首先从所应满足的条件入手加以分析。要求满足下述公理。N1.个体合理性。N2.可行性。N3.Pareto最优性若使，则。N4.无关方案的独立性若，且,则。N5.正仿射变换无关性设区域是经过如下正仿射变换得到的，如果，则必有

N6.对称性如果满足（1），则有（2），，则.纳什公理的解释在上述公理中，N1，N2，N3都易于理解。N4表明如把谈判集扩大到一个新的谈判集，且新问题的映射值在原谈判集中，那么也是原问题的映射值，即。换言之，扩大的谈判集中新增加的方案与谈判无关。N5表明谈判的结局对于谈判问题的正仿射变换保持不变。N6主要体现公平原则，即若双方地位、实力相同，策略相同，且谈判基点也一致，则最后所得到的谈判结果也相同。纳什定理在以上公理条件下，纳什给出了以下定理定理7.1纳什定理满足条件N1-N6的充要条件是是下述最大化问题的解。满足定理7.1中的优化问题的解为纳什讨价还价（谈判）解。由纳什定理可以看到，参与人最大化的并不是自己的支付函数，而是包括两个人的效用在内的一种公共福利函数。该函数体现了参与人效用增量均等的价值取向。命题7.1

对于任一满足可导且，。纳什讨价还价（谈判）解是下列方程组的惟一解。，。实际，将代入定理7.1中优化问题的目标函数，再利用1阶条件立知命题7.1成立。在某些应用中，纳什讨价还价问题中，的帕累托边界是直线，其中，此时我们可得到以下结论。命题7.2折中规则对任一满足，且，的纳什讨价还价（谈判）问题，纳什讨价还价解满足：。对于命题7.1中两式可解释如下：参与人对于分割单位利益进行讨价还价。他们所达成的协议是，首先分给支付，分给支付，然后再平分剩余利益。7.1.2不对称纳什讨价还价（谈判）解一般的纳什讨价还价（谈判）解的概念纳什讨价还价解取决于可能的支付向量集合与无协议点。此外，还可能受到讨价还价的策略、谈判实施的程序、信息结构、参与人的地位、贴现因子等影响。为了刻画这种讨价还价或谈判问题，我们给出了不对称或一般的纳什讨价还价（谈判）解的概念。定义7.1对每个，一个不对称或一般化的纳什讨价还价解是一个函数。是以下最大化问题的惟一解对，满足公理N1-N5。反之，任何满足N1-N5的相对于某个为非对称的纳什讨价还价解。特别时，一般的纳什讨价还价解为对称的讨价还价解。关于一般的讨价还价解，我们有命题7.3对任一，以及满足可微且，的讨价还价问题，不对称的纳什讨价还价（谈判）解是下列方程组的惟一解。，。命题7.4折中规则对和任一满足，其中且的纳什讨价还价（谈判）问题，不对称的纳什讨价还价（谈判）解为由命题2.4可知，当两个参与人分割利益时，越大，分得的利益越大，分得的利益越小。他们可以这样协议，首先分给，分给，然后分得剩余支付的份额，分得剩余支付的份额。7.1.3纳什谈判（讨价还价）解的应用1贿赂与控制犯罪参与人可以通过某种非法行为获取资金。这种行为被参与人发现的概率为。可以向贿赂金额为，与就金额进行讨价还价。作为回报，不揭发。参与人可从货币额中获效用。谈判可行支付集合。如果无法达成协议，揭发，将付出一笔罚金，罚金率为。利用前面所得的结果，谈判问题的基点。纳什讨价还价解为因而贿赂额为。

是否会去违法呢？从违法行为中得到的预期效用为，当且仅当时，才不会违法。由于，当且仅当时，不会违法。由于且，这说明。因而会去违法。这说明如果通过贿赂就能逃避罚款，那么这样的罚款对阻止犯罪不会起任何作用。在上述分析中，参与人在以下意义下具有有限责任，即所能得到的最大贿赂为，。当局所能处以最大的罚款也为，即罚款率。若去掉这个有限责任假设，当罚款率足够大，即时，的违法行为不会发生。2.团队中的道德风险设与组成团队共同生产某种产品。产出量取决于他们的努力水平与。生产函数为，努力成本为。由于努力水平是不可验证的，因而不能写入契约。契约是依据可验证的产量设立的。在他们同时选择各自的努力水平之前，先对产出的分配规则进行讨价还价。设表示所取得的产出份额，为能取得的产出份额，如果与达成了协议，则分别以努力水平，投入生产，,的利润函数分别为容易计算出纳什均衡努力水平的均衡利润为。其中。由于在上严格递增，在处最大，在上严格递减。在上严格递增，在处达到最大，在上严格递减。因而，可行支付向量集合的帕累托有效边界为。纳什讨价还价解中所得的协议是下述最大化问题的解其解为。而纳什讨价还价解为。7.2具有可转移支付的联盟博弈7.2.1具有可转移支付的联盟博弈及分类具有可转移支付的人合作博弈在非合作的人博弈中，局中人之间不允许事先协商如何选择策略，不允许他们把策略结合起来，不允许局中人对得到的支付重新分配，一个局中人不能分享另一个局中人的支付，或支付是不可能转移的。本章所讨论的人合作博弈对上述问题都不加限制。局中人在选择策略时可以协商，并且局中人的支付可以相互转让，或支付是可以转移的。在具有可转移支付的人合作博弈中，局中人如何选择自己的策略已不是主要讨论的问题，我们主要讨论的问题是局中人如何分配通过合作所获得的收益或效用。联盟与特征函数设局中人集合，称的任一子集为一个联盟。为方便，把的空子集也视为一个联盟。记所有联盟构成的集类为。对，用表示联盟中的局中人通过合作所能获得的最大支付。且可认为这个值与中的局中人的行为是独立的，因而是定义于上的函数，即。定义7.2对于局中人集合的任一子集，给定集合的支付，如果满足，则称为特征函数，称为具有可转移支付的联盟博弈。若满足对，，有，则说满足超可加性。下面讨论的联盟博弈都是指具有可转移支付的联盟博弈。特征函数满足超可加性。例7.1局中人1（卖主）要把一件物品卖掉，局中人2和3（买主）分别出价9元和10元。如果局中人1将物品卖给局中人2的要价是元，则局中人2赢利元。联盟的总收益为9元。类似，联盟的总赢利为10元。于是有。另一方面，单个局中人或者两个买主在一起都不可能赢利，即，。当三个局中人在一起交易时，局中人1显然要把物品卖给局中人3，从而，显然满足超可加性，于是我们建立了联盟博弈。特征函数是研究联盟博弈的基础，确定特征函数过程实际就是一个建立合作博弈模型的过程。有的问题，特征函数可以容易地得到，有的问题需要仔细分析，甚至需要一些专业知识。若对，，都有,则称满足可加性。我们可以给出满足可加性的特征函数的例子。例7.2在某项工作中，不熟练工人可获报酬元，熟练工人可得报酬元，于是可以定义特征函数

。这里表示集合中的局中人个数，以后也用这种记法。7.3具有可转移支付的联盟博弈的转归转归或分配的定义在联盟博弈中参与人通过合作，获得一定的联盟支付，联盟还要将这笔支付转归于每个参与人，联盟博弈中每个局中人从联盟中所获的支付或转归可用维向量表示，这里为局中人所得到的支付。定义7.3

称向量是联盟博弈的一个转归或分配，如果满足（1），（2）。（1）式表明n个局中人的支付总和应与他们全体构成一个联盟所获的支付相等。这说明如果要使某个局中人的支付增加，必需减少其它局中人的支付。这描写了帕累托最优性，因而，称（1）为整体合理性。（2）式表明每个局中人在合作博弈中所获得的支付不应低于他“单干”所获的支付。称（2）为个体合理性。转归的优超关系为了比较哪个转归好些，给出以下定义。定义7.4设有分配，及联盟,如果(1)对，(2)则称联盟为分配优于分配，记作。如果对于，存在一个联盟，使，则称优于，记为。定义中条件（1）表明，联盟中每个成员都认为分配比好。条件（2）表明分配对中成员的支付能够由联盟付出。单人联盟不可能存在转归之间的占优关系实际，如果，由定义，且，于是有，这与为转归相矛盾。全联盟也不可能存在转归之间的占优关系如果，则，，。于是，这与为转归矛盾。关于某个联盟转归之间的占优关系满足下述的传递性：设，如果，，则。但由，一般不能得到的结论。7.4稳定集与核心稳定集的定义定义7.5对于联盟博弈，集合称为联盟博弈的稳定集，如果以下条件成立。（1）中任意分配都不优于中的其余分配。（2）不属于中的任何分配，总可以在中找到优于的分配。稳定集定义中第1条表明在稳定集内部的任何两个分配之间不存在优超关系，称为稳定集的内稳定性，它可以防止由于联盟内部成员因利益冲突而导致联盟解体；第2条表明稳定集外的任一分配，至少被稳定集内的某个分配优超，称为稳定集的外稳定性。稳定集的概念由冯.诺依曼（V.Neumann）和摩根斯坦（Morgenstern）提出，也称为合作博弈的解。例7.3

设有三个局中人，拟合伙开商店，每月可赢利2000元。要使商店正常营业，起码需要两人。试问，应采用怎样的方式经营，以及怎样分配利润才是合理的。这是一个联盟博弈问题。特征函数为三人利润分配是向量，满足如果联盟形成，即局中人1、2合伙，则分配是合理的。否则，局中人1要求采取分配，其中，那么局中人2将与局中人3合伙。如果局中人3也采取类似的要求，则局中人2不与任何人结盟，余下1与3各持己见。不构成分配。同样，如果结盟，是合理的分配；结盟，是合理的分配。易知是稳定集（1）之间没有优超关系；（2）对于之外的任何一个分配满足，且，定必被中某个分配优超。人们花费了近20年的时间来证明联盟博弈的存在性。但卢卡斯（Lucas，１９６９）举出了反例说明联盟博弈的稳定集可以是空的。另外，寻求稳定集至今还没有通用的方法。核心的定义定义7.6人联盟博弈的所有不被优超的分配构成的集合称为核心，记为。对于核心中的分配，局中人不能通过重组联盟而增加支付。核心的充要条件定理7.2是人联盟博弈的核心中的分配的充要条件是（1）（2）对，。证明设满足（1）、（2）两个条件，要证明在中。取，知是分配。设有联盟和分配，使对由条件(2)知，因而由定义7.5知不能被优超，即。其次证明中元素均满足（1）、（2）两个条件。设，因是分配，所以（1）成立。用反证法可证（2）也成立。若（2）不满足，即存在和，使，并设中有个局中人，定义分配如下：其中，。这个不等式由及得到。容易验证是个分配且。这与不被优超矛盾。例7.4设有三人联盟对策，其特征函数，由定理7.2易知,该博弈的核心由下面不等式组确定：易知，，，。故该博弈的核心其图形为单纯形内以为顶点的四边形，如图7-1所示。(5,0,0)（0,5,0）（0,0,5）(2,2,1)（3,2,0）(4,1,0)图7-1(4,0,1)例7.5污染问题沙普利（Shaplay）和舒比克（Shubik）在参考文献[25]中描述了一个湖的污染模型。设有个工厂分布在某湖的沿岸，为简便起见，设问题是对称的。即每个工厂的污染程度相同。假设每个工厂每天必须在湖里抽取相同数量的清洁水，用完后将污水排入湖中。所涉及的方案和费用如下:(1)每个工厂每天必须因每个直接向湖中排放污水的工厂（包括自身）花费美元净化它所用的水。（2）每个工厂可以安装一个过滤器，在污水排回湖中之前就将水净化。每个工厂每天的净水费用为美元。为使问题有意义，假设。（3）个参与人可以组成一个联盟，共同决定是否采用过滤器。注意，如果决定采用过滤器，联盟之外的工厂仍会向湖中排放污水。因而联盟的特征函数值为即当时，联盟决定采用过滤器，时决定不采用过滤器。设，有由定理7.2，的充要条件是满足下述不等式组由知即。由问题的对称性知，。故该联盟博弈的核为，。例7.6产品经济问题一个企业家拥有一家工厂，并且个工人仅拥有自己的劳动力。工人不加入工厂，则不能进行生产。若加入工厂，个工人与企业家一道的产出为。这里为满足的凹生产函数。可将这个问题模型化为联盟博弈。此处。其中0代表企业家，是工人的集合。特征函数可如下定义：表示集合中的人数。据定理7.2，的充要条件是满足下述不等式组当时，有，所以，，于是。由问题的对称性，应有，。利用是凹函数以及，可以证明当，成立时，不等式组中，成立。由于凹，故有，即成立，于是于是我们可得的核心。例7.7具有否决人的0-1规范简单联盟博弈设是一个0-1规范简单的联盟博弈，即取0与1两个值，且，，。如果参与人满足，称为具有否决权的局中人或否决人。对于，的充要条件是存在否决人。证明必要性若，但没有否决人，即对成立。对有，。于是，。这与相矛盾。因而存在否决人。充分性设的全体否决人集合为，设满足，当时，。当时，。可以证明。若联盟满足，称为一个获胜联盟，我们说明。对于但，则有。又因，由是简单的0-1规范联盟博弈，故，这与矛盾，因而。此时。于是对于获胜联盟都有。对于任何非获胜联盟，有，从而我们证明了对于的任何子集，都有故。例7.8多数博弈联盟博弈满足（1）局中人集合中元素个数且为奇数。（2）则。

显然，为一0-1规范简单博弈且不存在否决人，由例7.7知。7.5联盟博弈的沙普利值

联盟博弈的沙普利值本节介绍由沙普利（Shapley，L.S.）（1953）给出的人合作博弈的另一个解的概念——沙普利值，它不仅可以解决经济活动中效益分配问题，而且能够估计社会活动中各团体或派别的权利。为使沙普利值为联盟博弈的分配，需假设特征函数满足对成立。设为一联盟博弈，对于给定的特征函数可以确定出特定的分配，这里

,。称为联盟博弈的沙普利值。的表达式的右端表示对于对联盟的贡献的加权平均。权数表示在个参与人的任意排列中，仅属于联盟的概率。沙普利值所满足的公理可以证明沙普利值是满足下述公理的唯一向量。A1.对称性公理。每个局中人所得的收益与的序号无关。A2.

有效性公理。。有效性公理反映了作为分配的整体合理性。A3.虚设人公理。对于虚设人，有，所谓虚设人指满足的局中人。该公理表明，若虚设人加入联盟后，并没有给带来额外的收益，则对的分配与他单干时的收益相等。A4.聚合公理。对于两个联盟博弈和有。聚合公理表明局中人参加两个博弈，其收益为在两个博弈中的分别收益之和。我们用两个例子说明沙普利值的应用。例7.9污水处理费用的合理负担沿河有三城镇1、2和3，位置如图5-3所示。污水需处理后排入河中。三城镇既可单独建立污水处理厂，也可以联合建厂，用管道将污水集中处理，向河流下游城镇输送。用表示污水量（吨/秒），表示管道长度（千米）。按照经验公式，建立污水厂的费用，铺设管道费用为.已知三城镇污水量为，的数值如图7-2所示。试从节约总投资的角度为三城镇制定污水处理方案。如果联合建厂，各城镇如何分担费用。20千米河流138千米图7-232三城镇污水处理共有以下5种方案,计算出费用以作比较。(1)分别建厂，投资分别为总投资（2）1,2合作,在城2建厂，投资为总投资（3）2,3合作,在城3建厂，投资为总投资（4）1,3合作,在城3建厂，投资为这个费用超过了1，3分别建厂的费用，合作没有效益，不可能实现。（5）三城合作，在城3建厂，总投资为比较结果以（千元）最小，所以应选择联合建厂方案。下面的问题是如何分担费用。总费用中有3部分：联合建厂费城1至城2的管道费城2至城3的管道费城3提出，由三城按污水比例5：3：5分担，是为城1，2铺设的管道费，应由他们担负。城2同意，并提出由城1，2按污水量之比5：3分担，则应由城1自己担负。城1提不出反对意见，但他们计算了一下按上述方法各城应分担的费用：城3分担费用为城2分担费用为城1分担费用为结果表明2，3分担的费用均比他们单独建厂费用小，而城1分担费用却比大。显然，城1不能同意这种分担总费用的办法。为了促成三城联合建厂以节约总投资，应该寻求合理分担总费用的方案。三城的合作节约了投资，产生了效益，是一个人合作对策问题，可以用Shapley值方法圆满地分配这个效益。把分担费用转化为分配效益，就不会出现联合建厂城1分担的费用反比单独建厂费用高的情况。将三城镇记为，联合建厂比单建厂节约的投资定义为特征函数，于是有三城联合建厂的效益为64（千元），用Shapley值方法计算这个效益的分配。城1应分得的份额的计算结果列入表7.1，得到（千元）。类似地算出。可以验证：。看来城2从总效益64（千元）中分配的份额最大。表7.1污水处理问题中的计算

0600400002504003912231/31/61/61/306.7013在联合建厂方案总投资额556（千元）中各城的分担费用为城1是城2是城3是。例7.10联合国安理会有15个成员国,其中有5个常任理事国，它们有否决权,一项议案被通过,必须不被任何常任理事国否决而且还要求有9国赞成，我们来考察每个成员国在否决提案时所具有的实力。