合作博弈(四川大学)

第5章合作博弈§5.1根本概念§5.2占优方法：合作博弈一类解概念§5.3估值方法：合作博弈的一类解概念§5.4合作博弈的应用范例2021-3-312021-3-3?博弈论及其应用?〔汪贤裕〕2§5.3估值方法：合作博弈的一类解概念

§5.3.1Shapley值

§5.3.2势指标2021-3-322021-3-3?博弈论及其应用?〔汪贤裕〕3§5.3.1Shapley值

□Shapley值□定义5.3.1哑元和支柱□定义5.3.2置换的定义□Shapley值的三条公理□几个引理□求解Shapley值2021-3-332021-3-3?博弈论及其应用?〔汪贤裕〕4Shapley值上一节我们讨论了n人合作博弈中占优方法下的各种解概念。每一个解概念都有相适应的经济意义。但是当中有一些问题：一些解概念出现了空集的情况，如核心的C(v)。在局中人的人数较大的时候，对这些解概念的求解非常困难。在不少情况下的解概念常常不唯一。Shapley〔1953〕用公理化方法提出了Shapley值，构成了一种新的解概念。能够对合作博弈中的局中人参与博弈的价值能给出具体表述，并且有很直接的计算方法。由于Shapley值具有很好的经济意义。以极为简单的求解方法，因此得到非常广泛的应用。2021-3-342021-3-3?博弈论及其应用?〔汪贤裕〕5Shapley值〔续〕设有一个人合作博弈，具有弱超可加性，我们可以对合作后的总收益给出如下的分配方案。假设中个局中人的排序为，考虑分配方案为其中即按局中人编号的自然序排序，依先后顺序逐步形成联盟，每一个局中得到的是对联盟形成的边际奉献。显然2021-3-352021-3-3?博弈论及其应用?〔汪贤裕〕6Shapley值〔续〕假设中个局中人的按照编号逆向排序。考虑分配方案为，其中即确定一个排序，局中人按逆向排序先后逐步形成联盟，每个局中人分配到对联盟形成的边际奉献。显然也有因为中的个局中人给定一个自然数编号，并且互不相同，那么个局中人的排序方法有种。因而有种不同的分配方案2021-3-362021-3-3?博弈论及其应用?〔汪贤裕〕7Shapley值〔续〕作为一个局中人在中分配方案下的平均边际奉献那么为：表示的是联盟S中具有的局中人的个数。在形成联盟S以后，表示不包含局中人的联盟排列个数。表示联盟的排列个数，表示个局中人可形成的排列的个数。表示联盟S出现的概率，表示局中人对联盟S的边际奉献，假设，那么该式为0。也就是局中人对联盟S无关。〔〕式给定一个维向量：就是合作博弈的Shapley值。.2021-3-372021-3-3?博弈论及其应用?〔汪贤裕〕8哑元和支柱定义在人合作博弈中，设是一个联盟。如果对任意联盟都有：〔〕那么称D为博弈的一个支柱〔carrier〕或称D为G的一个载体。假设D是博弈的一个支柱，，称局中人i为哑元〔dummy〕或称虚拟局中人。引理1假设D是博弈的一个支柱。满足：那么也是的支柱。2021-3-382021-3-3?博弈论及其应用?〔汪贤裕〕9哑元和支柱〔续〕——例子例有一个三人合作博弈，特征函数取值为：可以看出联盟是一个支柱，局中人2为哑元。由于大联盟，那么大联盟也是一个支柱。，，，2021-3-392021-3-3?博弈论及其应用?〔汪贤裕〕10置换的定义定义设有人合作博弈。其中，为的一个排列，也称为的一个置换〔Pemutation〕。假设，记i在置换下的位置记为。假设，。那么规定。同时记为一个特征函数：〔〕2021-3-3102021-3-3?博弈论及其应用?〔汪贤裕〕11Shapley值的三条公理定义

在人合作博弈中，的Shapley值是n维向量：，满足下面三条公理：公理1

对称性公理。对于置换,有：公理2

有效性公理。对于的每一个支柱。有:公理3

可加性公理。对任意两个合作博弈对任意的有其中。2021-3-3112021-3-3?博弈论及其应用?〔汪贤裕〕12Shapley值的三条公理〔续〕公理1表示任何局中人i分配所得，不依赖于它在某个排列中的位置。换言之，不同位置的局中人，只要他们对联盟的奉献是相同的，即他们在合作中的作用是相同的，他们所得的分配额也就相同。公理2表示在采用Shapley值确立的分配方案中，仅需对支柱D中的局中人考虑就可以了。公理3将同样的局中人在两次博弈所得可以看成特征函数合并后的一次所得。可见，上述公理体系对Shapley值的要求条件是很低的。三个公理所代表的三个根本要求一般都认为是合理的。2021-3-3122021-3-3?博弈论及其应用?〔汪贤裕〕13引理2在合作博弈中，假设是支柱，局中人是哑元。即，在公理2的条件下，有。证明：因为是博弈的支柱。。那么由定义由于是支柱。由引理1，也是支柱。由公理2有引理2说明哑元参加到联盟中来，未有新的奉献，因此他能得到保存的收益。2021-3-3132021-3-3?博弈论及其应用?〔汪贤裕〕14引理3

设合作博弈是一个简单的博弈。其中特征函数的取值为

当满足公理1和公理2时，是博弈的支柱，且

2021-3-3142021-3-3?博弈论及其应用?〔汪贤裕〕15引理3(续)——证明证明：由定义，可以验证，对任意有那么R是博弈G的支柱。由于R是支柱，有也是支柱，由公理2有那么，有。由公理1，对任意选取置换，仅对和的位置发生置换，，于是有。再由公理2有：因此：

。2021-3-3152021-3-3?博弈论及其应用?〔汪贤裕〕16推论推论：在引理3的条件下，对正常数，规定。那么是合作博弈的支柱，且

2021-3-3162021-3-3?博弈论及其应用?〔汪贤裕〕17引理4引理4.任何人合作博弈满足公理1和公理2其特征函数可以表示成的线性组合。〔〕其中由引理3规定，参数由下面公式确立：〔〕2021-3-3172021-3-3?博弈论及其应用?〔汪贤裕〕18引理4〔续〕证明：将〔〕代入〔〕，对任意都有在上式中，只有时才不为0.并且当时,由〔〕有。所以其中第二个等式来自交换求和的次序。第三个等式中是从从个元素中找个元素的组合数。第四个等式来自二次式定理。最后一个等式来自：这就证明了〔〕式成立。2021-3-3182021-3-3?博弈论及其应用?〔汪贤裕〕19求解Shapley值〔一〕——定理定理人合作博弈。假设满足定义给出的三条公理：对称性，有效性和可加性，那么存在唯一的Shapley值

此定理的证明就是验证三条公理的过程，相比照较复杂，我们证明如下：2021-3-3192021-3-3?博弈论及其应用?〔汪贤裕〕20定理5.3.1证明证明：该定理的证明分为两个局部。第一个证明由三条公理可以推导出唯一的〔〕表示的Shapley值，第二局部证明〔〕满足三条公理：首先由引理4的〔〕由公理三和引理三推论〔〕式我们有：将〔〕式代入到上式中，其中将联盟T用联盟S取代，有〔〕2021-3-3202021-3-3?博弈论及其应用?〔汪贤裕〕21定理5.3.1证明〔二〕将上式〔〕分开讨论，前以局部有：

〔〕2021-3-3212021-3-3?博弈论及其应用?〔汪贤裕〕22定理5.3.1证明〔二〕上面的第二个等式来自。第三个等式是积分求和次序的交换，并拼凑出二项式式子，第四个等式是二项式定理。最后一个等式来自于的函数性质。〔〕式的后一项中，因为，令，那么，，于是后一项为：2021-3-3222021-3-3?博弈论及其应用?〔汪贤裕〕23定理5.3.1证明〔二〕2021-3-3232021-3-3?博弈论及其应用?〔汪贤裕〕24定理5.3.1证明〔三〕由〔〕代入到〔〕式，再将〔〕式代入有：在的时候，〔〕中那么〔〕与〔〕没有区别，一般我们使用〔〕式，这样，我们就完成了定理证明的第一局部。下面我们进行定理第二局部的证明，即验证〔〕式满足三条公理。〔1〕验证公理1对于任意一个置换，都是对N中的n个元素的一种排列。令也是一种置换，其逆变换也是如此。因此对于任意的，我们有。令。2021-3-3242021-3-3?博弈论及其应用?〔汪贤裕〕25定理5.3.1证明〔四〕其中的第一个等式任意取，和任意取等价，第二个等式任意取和任意取等价。第三个等式采取了的逆置换。因而公理1得到了验证。〔2〕验证公理2假设i不属于每个支柱D，对于联盟有：2021-3-3252021-3-3?博弈论及其应用?〔汪贤裕〕26定理5.3.1证明〔五〕接下来我们证：由〔〕式，有2021-3-3262021-3-3?博弈论及其应用?〔汪贤裕〕27定理5.3.1证明〔六〕对S取一个固定的进行考察，由于对所有的，且满足的次数为次，那么v〔R〕的双重和的系数为：再考察〔〕式中的第二项的系数。任意给一个，,都会有一个S使得，这种S的选取一共有个。因为i可以是N\R中的任何一个元素。于是〔〕和式中使得第二项为的双重系数为：上式中的是指的S的选取为。并且对于任意的都成立。2021-3-3272021-3-3?博弈论及其应用?〔汪贤裕〕28定理5.3.1证明〔七〕〔〕式对于一切的都成立，〔〕式对于一切的都成立，相互之间只相差一个符号。而在〔〕中，当R=N时为1，因此：设D是一个支柱，由〔〕和〔〕以及支柱的定义，有：因而公理2得证。2021-3-3282021-3-3?博弈论及其应用?〔汪贤裕〕29定理5.3.1证明〔八〕〔3〕验证公理3由于Shapley值是v的线性函数，因而公理3自然满足。Shapley值是满足三条公理的唯一的维向量。这一个事实可以由公式的推导直接可以得到。2021-3-3292021-3-3?博弈论及其应用?〔汪贤裕〕30求解Shapley值〔二〕——

例有三个人准备合作办一企业，局中人1仅有核心技术，假设他将技术转让可得20万元；局中人2有资金，假设他将投入企业的资金用于其他工程投资，可获得共30万元；局中人3有很强的组织管理和营销能力，假设他参与其他企业效劳，可获得15万元收益。假设局中人1和2合作，将企业承包给第三方，可获得60万元；假设局中人1和局中人3合作，由于融资的不畅，但仍可获得40万元；假设局中人2和局中人3合作，进行其他工程开发，考虑到技术原因造成的工程风险，因而年均可获得65万元。假设三人合作，可获得100万元。现三人合作后应该对所得如何分配？2021-3-3302021-3-3?博弈论及其应用?〔汪贤裕〕31将三人合作博弈的特征函数值重复如下。由〔〕有：该博弈的Shapley值为：求解Shapley值〔二〕——例〔续〕，2021-3-3312021-3-3?博弈论及其应用?〔汪贤裕〕32§5.3.2势指标

例5.3.1投票的例子定义5.3.4摆盟的定义定义5.3.5Banzhaf-Coleman势指标例5.3.2Banzhaf势指标的求解定义5.3.6获胜联盟集和最小获胜联盟集定义5.3.7D-P势指标例5.3.3D-P势指标的求解定义5.3.8最小制止联盟集定义5.3.9反联盟2021-3-3322021-3-3?博弈论及其应用?〔汪贤裕〕33例5.3.1投票的例子例设有一个投票博弈，投票人的集合为其中局中人1有3票，其余的局中人各一票。投票规那么为得票数超过一半，即到达四票或者四票以上，被投票的决议才能通过。即特征函数的取值为：

因此可以计算Shapley-Shubik势指标为：

可以考虑，假设投票规那么改为所得投票超过总票数的，即要到达5票时,被投票的决议才能通过。这时的Shapley-Shubik势指标为多少？2021-3-3332021-3-3?博弈论及其应用?〔汪贤裕〕34当人合作博弈是一个简单博弈时，那么任意联盟，的取值为1或0。这时Shapley值的分量为：〔〕在〔〕式中的联盟为取胜联盟，且为失败盟约〔见前面的定义〕。由〔〕式组成的维向量称为Shapley-Shubik势指标〔Shapley-Shubikindexofpower〕。摆盟的定义2021-3-3342021-3-3?博弈论及其应用?〔汪贤裕〕35摆盟的定义定义设人合作博弈是一个简单博弈。是一个联盟，即，且满足：〔1〕〔2〕是一个取胜联盟，是一个失败联盟，即，。那么称为局中人在中的一个摆盟。2021-3-3352021-3-3?博弈论及其应用?〔汪贤裕〕36Banzhaf-Coleman势指标定义设人合作博弈是一个简单博弈。是局中人的摆盟总数。称维向量

为的标准化Banzhaf-Coleman势指标〔normalizedBanzhaf-Colemanindexofpower〕。其中:〔〕2021-3-3362021-3-3?博弈论及其应用?〔汪贤裕〕37Banzhaf势指标的求解例有一个投票博弈，投票人的集合为。其中局中人1有3票，局中人2有2票，局中人3和局中人4各有1票，投票规那么为:〔1〕在得票数超过总票数一半的情况下，决议通过。〔2〕在票数超过总票数的2/3情况下，决议通过。试分析每一个局中人的Banzhaf-Coleman势指标。2021-3-3372021-3-3?博弈论及其应用?〔汪贤裕〕38Banzhaf势指标的求解〔续〕〔1〕在得票数超过总票数一半的情况下，该博弈的特征函数的取值为：

在其余联盟下，。或者记为:

假设以赋权多数博弈表示,设每个人拥有票数，那么阈值常数。特征函数也可记为2021-3-3382021-3-3?博弈论及其应用?〔汪贤裕〕39Banzhaf势指标的求解〔续〕局中人1的摆盟有：{1,2},{1,3},{1,4},{1,2,3},{1,2,4},{1,3,4}，=6。局中人2的摆盟有:{1,2},{2,3,4}，=2。局中人3的摆盟有:{1,3},{2,3,4}，=2。局中人4的摆盟有:{1,4},{2,3,4}，=2。那么Banzhaf-Coleman势指标为：2021-3-3392021-3-3?博弈论及其应用?〔汪贤裕〕40Banzhaf势指标的求解〔续〕〔2〕在票数超过总票数2/3的情况下，该博弈的特征函数为

其余联盟为。或者记为：或者记为：2021-3-3402021-3-3?博弈论及其应用?〔汪贤裕〕41Banzhaf势指标的求解〔续〕通过类似〔1〕的计算，，，那么Banzhaf-Coleman势指标为：我们再考察例。例中，通过简单的计算Banzhaf-Coleman势指标为2021-3-3412021-3-3?博弈论及其应用?〔汪贤裕〕42Banzhaf势指标的求解〔续〕例中将与相比较，可以看到，Banzhaf-Coleman势指标与Shapley-Shubik势指标是不相同的。其不同的根据在于所依赖的公理化体系的不同。Shapley-Shubik势指标依赖于Shapley制定的三条公理体系。Owen〔1985〕提出了5条公理组成公理体系，在其公理体系下，Banzhaf-Coleman势指标可以被推导出来，并且是唯一的。2021-3-3422021-3-3?博弈论及其应用?〔汪贤裕〕43获胜联盟集和最小获胜联盟集定义人合作博弈是一个简单博弈。记为的全体取胜联盟集。为取胜联盟M的子集，并满足以下的条件:1．。空集不可能是取胜联盟。2．。指一定有中的联盟获胜。3．对于任意的，有。指任何两个取胜联盟都是相关的，并隐含博弈中有专制者或小团体，对取胜联盟有重要作用。4．假设；假设，那么，指只考虑取胜联盟中的核心联盟，不考虑“哑元〞。那么称为简单博弈的最小获胜联盟集〔minimawinningcoalitionset〕。同时记局中人i的最小获胜联盟集为：2021-3-3432021-3-3?博弈论及其应用?〔汪贤裕〕44D-P势指标定义设人合作博弈是一个简单博弈。的D-P势指标〔Deegan-Packelindexofpower〕是一个维向量。。其中：

〔〕2021-3-3442021-3-3?博弈论及其应用?〔汪贤裕〕45D-P势指标的求解例有一个投票博弈，投票人的集合为其中局中人有4票，局中人有2票，其余三人各有1票，投票规那么为在票数超过总票数一半的情况下，决议通过。假设记为各个局中人拥有的票数。其特征函数为：经过简单的计算，该博弈的最小获胜联盟集如下：

局中人i的最小获胜联盟集为：经过计算，其D-P势指标为

2021-3-3452021-3-3?博弈论及其应用?〔汪贤裕〕46D-P势指标的求解〔续〕例有一个投票博弈。其中局中人有2票，记为，局中人b和c各有一票，即。投票规那么为在得票数超过总票数一半的情况下，决议通过。该博弈的特征函数为：

该博弈的最小获胜联盟，那么其D-P势指标为：Shapley-Shubik势指标为：Banzhaf-Coleman势指标分别为：可见三个势指标并不一样。2021-3-3462021-3-3?博弈论及其应用?〔汪贤裕〕47最小制止联盟集定义人合作博弈是一个简单博弈。为简单博弈的最小获胜联盟集。设

〔〕那么为简单博弈的最小制止联盟集，即〔Minimalblockingcoalitionset〕。同时记：〔〕2021-3-3472021-3-3?博弈论及其应用?〔汪贤裕〕48反联盟D-P势指标定义设人合作博弈是一个简单博弈。的反联盟〔Blockingcoalition〕D-P势指标是一个n维向量：

其中：前面三个势指标大多用于投票博弈的分析，并都是根据取胜联盟的角度反映出局中人的“势力〞大小。D-P势指标从另一个角度，即从局中人或局中人联盟能阻止取胜联盟的能力，来计算势指标。2021-3-3482021-3-3?博弈论及其应用?〔汪贤裕〕49反联盟D-P势指标——例子再看例子。假设，那么。含有最小取胜联盟。那么。假设取。即含有取胜联盟。假设取不含有任何取胜联盟。即联盟具有破坏取胜联盟的作用，那么。2021-3-3492021-3-3?博弈论及其应用?〔汪贤裕〕50反联盟D-P势指标——例子〔续〕类似的分析后有：利用公式〔〕有那么的反联盟D-P势指标为得到G的D-P势指标和反联盟的D-P势指标后，还可以按决策的主观偏好进行加权平均：〔〕其中，是对成功获胜能力给予的权重，是对阻止获胜能力给予的权重。显然具有很强的主观色彩。2021-3-3502021-3-3?博弈论及其应用?〔汪贤裕〕51反联盟D-P势指标——例子〔续〕在此例中，假设取，有：

另外，在例中，可以得到利用博弈中局中人或局中人联盟具有破坏和阻止取胜联盟形成的这种能力。我们构造了反联盟D-P势指标。这种思想也可以用于对Shapley-Shubik势指标，Banzhaf-Coleman势指标的讨论。我们可以看到，D-P势指标和反联盟D-P势指标，与占优集中的-核心和谈判集具有相似的思想。2021-3-3512021-3-3?博弈论及其应用?〔汪贤裕〕52§5.4合作博弈的应用§5.4.1本钱分摊博弈§5.4.2石油市场博弈2021-3-3522021-3-3?博弈论及其应用?〔汪贤裕〕53§5.4.1本钱分摊的博弈

例5.4.1信号传输的费用分摊问题例5.4.2多用途水坝问题2021-3-3532021-3-3?博弈论及其应用?〔汪贤裕〕54费用分摊问题例有三个村庄合作在一个附近山峰上修建了一座电视接收塔，并用通讯电缆将信号传送到三个村庄。设电视接收塔所在地为0，三个村庄的所在地分别为1，2，3。任意两地之间架设通讯电缆的本钱费用标注在右图中，单位为万元。2021-3-3542021-3-3?博弈论及其应用?〔汪贤裕〕55例5.4.1〔续〕假设暂不考虑电视接收塔和信号中转站的本钱费用。只考虑通讯电缆的架设本钱，我们可以清楚的看到，只须在〔0，1〕之间，〔1，2〕之间和〔1，3〕之间假设电缆，就可以满足传输信号的要求，总本钱是25万元。现在问题是，这25万元的总本钱应该在三个村庄之间中如何分摊？例求解过程2021-3-3552021-3-3?博弈论及其应用?〔汪贤裕〕56例求解过程这仍然是一个合作博弈的问题，记该博弈为表示本钱分摊的局中人集合，特征函数表示分摊本钱的局中人组成联盟后应分摊的本钱，即使得中每一个成员都能接受到电视信号所需的最小本钱费用。那么有：

这里我们不难看出，在特征函数解定义中，应将〔〕式的不等号反向，即：这是本钱分摊博弈对特征函数的特定要求对本钱分摊博弈，我们先就其转归集和核心进行讨论。设是一个转归，即一个分摊方案，那么应满足:记全体转归为转归集2021-3-3562021-3-3?博弈论及其应用?〔汪贤裕〕57例求解过程〔续〕其中〔〕仍是个体合理条件，〔〕仍是集体合理性条件。与前面定义的转归集定义的差异：〔〕式和〔〕式不等号方向发生了变化，这表达本钱分摊的特点。在本钱分摊博弈中，其核心的定义为：〔〕与前面核心的定义相比较。〔〕与〔〕式中的不等好方向发生了变化，这也表达了本钱分摊的特征。在该例子中，一个转归的具体表示为：2021-3-3572021-3-3?博弈论及其应用?〔汪贤裕〕58例求解过程〔续〕

对此可作一个高为25的重心三角形。并在此重心三角形内画出转归集为五边形AEFGH，核心为四边形ABCD。192021-3-3582021-3-3?博弈论及其应用?〔汪贤裕〕59例求解过程〔续〕同样可以定义强核心为〔〕并记为最小强核心，即，其中是使的最小值。在此例中，该博弈的Shapley值为：

2021-3-3592021-3-3?博弈论及其应用?〔汪贤裕〕60多用途水坝问题例假设在某河段上修水坝满足该地区的各种利益，比方洪水控制，导航，灌溉发电以及城市用水。水坝修建的本钱将在所有获利部门中进行分摊，应该如何分摊呢？这是典型的本钱分摊博弈。2021-3-3602021-3-3?博弈论及其应用?〔汪贤裕〕61多用途水坝问题〔续〕设某水坝其修建的目标有3个，导航，控制洪水和发电。效劳这些目标的水坝修建本钱如下表所示列〔单位：亿元〕例求解过程2021-3-3612021-3-3?博弈论及其应用?〔汪贤裕〕62求解过程类似于例，该例中本钱分摊博弈中，特征函数的取值即上表中对应的第二行值。可以求出该博弈的核心和最小核心。2021-3-3622021-3-3?博弈论及其应用?〔汪贤裕〕63求解过程〔续〕上面重心三角形中〔其高为〕其核心为六边形，各点的坐标分别为：

其最小核心为：该博弈的Shapley值为：2021-3-3632021-3-3?博弈论及其应用?〔汪贤裕〕64§5.4.2石油市场博弈

例5.4.3国家1生产石油，其石油可在国内消费，如改善交通运输条件，每桶油可获利元。国家2不生产石油，但它可以将石油由于制造业生产。每桶油可获利元。国家3也不生产石油，但它可以将石油用于食品业生产，每桶油获利元。其中。这里，特征函数可规定如下：

2021-3-3642021-3-3?博弈论及其应用?〔汪贤裕〕65§5.4.2石油市场博弈〔续〕〔1〕博弈的转归集。在下面高度的重心三角形中，转归集是三角形。其中A和B为的直线分别与直线12和直线13相交的交点。2021-3-3652021-3-3?博弈论及其应用?〔汪贤裕〕66§5.4.2石油市场博弈〔续〕〔2〕博弈的核心。假设，那么的充分条件为：由立即有。将代入上面方程组，有核心为上图中的线段1E,E点为直线与直线13的交点。，并且。即核心就为最小核心。2021-3-3662021-3-3?博弈论及其应用?〔汪贤裕〕67§5.4.2石油市场博弈〔续〕〔3〕稳定集设的稳定集为。首先从定理，考虑，取即线段，显然上的任何转归不相互优超，满足内切稳定性。且内任意转归都可以被上某个转归优超。因而是一个稳定集。2021-3-3672021-3-3?博弈论及其应用?〔汪贤裕〕68§5.4.2石油市场博弈〔续〕〔4〕谈判集:由在上对的异议存在异议的充分必要条件是，而核心中的任何转归有。因此，对于核心中的转归，不可能有对的异议。因而核心是一个谈判集。即。假设有转归，那么局中人1在上对局中人2可以提出异