专题二合作博弈

1、专题二： 合作博弈 在非合作的n人博弈中，局中人之间不允许事先协商和选择策略，不允许他们把策略结合起来，不允许局中人对得到的支付重新分配。一个局中人不能分享另一个局中人得到的支付。 讨论的n人合作博弈，对上述问题都不加限制。局中人在选择策略时可以协商，并且局中人的支付可以相互转让。在n人合作博弈中，如何选择自己的策略已不是主要讨论的问题，n人合作博弈模型主要讨论下述问题。1（1）n个局中人之间是如何构成联盟的。（2）各个联盟的支付或收益有多大。（3）局中人最终在联盟中分配到多少。 1.稳定集 1、联 盟 设局中人集合N=1,2,.,n，N的任意子集称为联盟。注 1：空子集 也称为一个联盟。 记

2、所有的联盟构成的集类为B。 对于 S B，用v(S)表示联盟S中的局中人通过合作所得到的支付。因而v(S)可认为定义在R上，取值于实数的一个函数。22、联盟博弈 称为一个联盟博弈3、特征函数 称v为该联盟博弈的特征函数，它满足v( )=0例1：局中人1（卖主）要把物品卖掉，局中人2和3（买主）分别出价9元和10元。如果局中人1将物品卖给局中人2的要价是x元，则局中人2赢利9-x元。 V(1,2)=9, v(1,3)=10, v(i)=v(2,3)=0. i=1,2,3, v(1,2,3)=10 于是建立了联盟博弈3特征函数是研究联盟博弈的基础，确定特征函数的过程实际就是一个建立合作博弈的过程定

3、义1：称向量x=(x1,x2,xm)是联盟S=1,2,.m的一个分配，如果它满足: (1) (整体合理性) (2) vi, i=1,2,.,m （个体合理性）注2： 的全部分配所构成的集合记为I(v)注3：满足（1）（2）的分配不唯一。4定义2：设有分配x,y I(v) ，及联盟S B ，如果:(1) 对 i S, (说明分配x比y好) (2) （说明分配中给联盟成员的支付可由联盟付出） 则称对联盟S，分配x优于y，记作 。如果对于 ，能找到一个联盟T，使 ，则称 优于 ，记作 。定义3：对于联盟博弈，集合s(V) I(v) 称为联盟博弈 的稳定集，如果以下条件成立：5（1）S (V) 中任意

4、分配x都不优于 S (V)中的其余分配 。 (说明稳定集内部任何两个分配无优超关系即内稳定性)（2）不属于S (V)中的任何分配y，总可以在 S (V)中找到优于y的分配x。（ 外稳定性）注4：稳定集的概念由冯.诺依曼(V.Neumann)和摩根斯坦(Morgenstern)提出，也成为合作博弈的V-N-M解。6例2 设有三个局中人，拟合伙开商店，每月可赢利200元。要使商店正常营业，起码需要两人。试问，应采用怎样的方式经营，以及怎样分配利润才是合理的。解：特征函数为 v(i)=0, i=1,2,3.v1,2= v2,3= v1,3= v1,2,3=2三人利润分配是向量x=(x1,x2,x3)

5、，满足x1+x2+x3= v1,2,3=2, (x1,x2,x3)=0 如果联盟1，2形成，即局中人1、2合伙，则分配x=（1，1，0）是合理的。7 否则，局中人1要求采取分配（1+ ，1- ，0），其中 （0，1），那么局中人2与局中人3合伙。如果局中人3也采取类似的要求，则局中人2不与任何人结盟，余下1与3各持己见。（1+ ，1- ,）不构成分配。同样，如果2，3结盟，y=（0，1，1）是合理的分配；1，3结盟，z=（1，0，1）是合理的分配，易知 w=x,y,z是稳定集（1 ） x,y,z之间没有优超关系8(2)对于w之外的任何一个分配a=(a1,a2,a3)满足a1+a2+a3=2 且

6、ai=0，必被w中某个分配优超。 2.核心定义1： n人联盟博弈的所有不被优超的分配构成的集合称为核心，记为c(v)定理1：分配方案x=(x1,x2,xn)在核心c(v)中的充要条件：(1)(2)对9例3：设有三人联盟对策，其特征函数v1= v2= v3=0,v1,2=4, v2,3=1, v1,3=3,v1,2,3=5由定理1知：这个博弈的核心由下面不等式组确定: x1+x2=4 x1+x3=3 x2+x3=1 x1+x2+x3=5 xi=010其解为A=x=(x1,x2,x3)| x1+x2+x3=5, xi=0内以(4,0,1,),(4,1,0),(3,2,0),(2,2,1)为顶点的四边形，如图：（0,0,5）0,5,03,2,0(4,1,0)(5,0,0)(4,1,0)(2,2,1)核11有些联盟博弈的核可能是空的。满足非空的条件:定理：对于n人的联盟博弈，核心非空的充要条件是线性规划有解：12 4 联盟博弈的Shapley值 n人合作博弈的另一个解设为一联盟博弈，对于给定的特征函数v可以确定出特定的分配 这里,13称 为联盟博弈的Shapley值 可以证明Shapley值是满足下述公理的唯一向量。 A1：对