基于τ值的图博弈有效权重分配规则

薛涛 董艳侠

摘 要：首先，本文提出基于τ值的权重图博弈有效解，这个单值解既是图博弈下τ值的推广，又是基于τ值的剩余平均分配解的扩展。其次，利用分支有效性、S均衡下的相对不变性、剩余有效权重分配和线性限制权重成比例对权重图博弈有效解进行公理刻画。最后， 介绍基于权重图博弈有效解的特殊分配规则。

关键词：图结构;有效解;τ值;分支有效性

本文索引：薛涛，董艳侠.<变量 2>[J].中国商论，2021（22）：-141.

中图分类号：F279.23 文献标识码：A 文章编号：2096-0298（2021）11（b）--05

在博弈中， 所有局中人通过合作获得总收益， 再经过合理的分配模式得到各自的收益， 他们相互关联形成各自的联盟。 但是，在很多情况下，受到技术、人际关系等方面的限制，因此只有相互联系的局中人才能形成联盟。 建立在这一假设前提下，Myerson[1]提出了图限制博弈，并建立在值的基础上给出一个在图博弈上的分配规则，即值，并对其进行了公理刻画。（1981）提出另外一种分配规则等（2011）值，并由王文文[3]将这一经典合作博弈下的单值解推广到图博弈中并给出公理刻画。

随着合作博弈的不断发展， 对于分支间进行合作形成大联盟后得到的收益大于各分支收益之和的情况， 学者也提出了许多扩展解。（2019）提出了两步值，（2011）基于τ值提出了两个有效解， 分别是剩余公平分配解与两步τ值。（2012）建立在相邻公平性的基础上，提出分支公平解、分支公平剩余解以及两步分支公平剩余解;（2016）提出度公平性、具有度值的公平性以及具有度剩余值的度公平性扩展了提出的一类逐分支公平解，从而得到了新的分配规则， 分别为：逐分支比例解、逐分支比例剩余解以及两步逐分支比例剩余解;  （2020）提出分支权重解、分支权重剩余解以及两步分支权重剩余解，作为在这一领域的进一步推广。 为了从值的角度进行扩展，（2012）建立在剩余公平分配的基础上提出基于值的剩余公平分配解; （2018）提出基于值的两步剩余公平分配解; 提出了一类有效权重（2019）值作为这一领域的进一步推广。 本文研究了在图博弈下基于值的有效权重解同时研究了有效权重解满足的性质，并给出有效权重解公理刻画。 最后提出了基于这一有效权重解的特殊分配规则并给出了公理化方法。

本文第1节介绍了图博弈、拟均衡博弈、 τ值等概念; 第2节提出权重图博弈有效解的精确表达式，给出权重图博弈有效解的性质并对权重图博弈有效解进行公理刻画。 第3节提出基于权重图博弈有效解的特殊分配规则并提出公理化方法。

1 基本定义

在合作博弈中，可以为任意一个由个局中人组成的联盟分配一个由实数表示的收益， 这一博弈被称为可转移效用博弈， 即博弈。该博弈可以由有序对偶表示，其中表示有限局中人集合， 特征函数，。 用表示由个局中人组成的联盟的收益，其中。

对任意图结构， 其中表示有限局中人集合，无序集合。 其中任意的表示局中人的双边关系。通过代替，简化表示一条边。 用表示与局中人相邻的局中人个数，表示为局中人的强度， 即;强度反映了该局中人在联盟中与其他局中人合作的紧密程度，强度越大该局中人合作能力越强;反之，合作能力越弱。

對于任何一个联盟，表示为的子图，其中，。 由一系列局中人形成的序列称为在图上的路，如果成立，对于。 图结构是连通图，如果在个局中人中，任意两个局中人之间都存在一条路。 在连通图中，所有连通联盟的集合用表示，个局中人中的最大连通子集被称为图结构的连通分支，该分支用表示。 所有连通分支的集合表示为，用表示的所有连通分支。 用表示中除去局中人后局中人的集合。 表示中包括的连通分支，任意一个连通分支的强度可以表示为。

表示博弈，表示包含v个局中人的图结构，故任意图博弈可以表示为，为简化，表示所有图博弈。 图博弈的解可以分为两类，一类是满足分支有效性的分支有效解，另一类是满足有效性的解即图博弈有效解。 其中，分支有效解有满足分支有效性的值，本文则是建立在值的基础上通过引入权重进而做出有关有效解的推广。 通过映射为每一个图博弈分配一个支付向量，且。 分支联盟收益之和表示为，分支联盟合作而形成大联盟的收益表示为。

根据参考文献[3]可知，在图博弈中， 对于任意的局中人，其上向量的元素可以表示为， 故表示为局中人加入其所在的分支联盟后可以得到的最大收益。 对于连通联盟集合， 联盟S的间隙函数表示。局中人关于联盟S的剩余收益表示为。因此，对于连通联盟，如果能够使除局中人以外的每一位局中人都得到各自的上向量，则表示局中人应该损失的收益。 故这一让步值对于单个局中人来说，越小越好。 对于任意有让步向量。拟均衡博弈可以表示为：

，，且，

定义1.1 对于任意的拟均衡图博弈，值可以表示为：

，

如果， 则.

引理1.1 在拟均衡博弈中，值满足以下性质：

（1）分支有效性：对于任意的，使得。

（2）个体理性：对任意的，有。

（3）S均衡下的相对不变性：对于任意，，使得，则下式成立：

。

（4）哑元性：若为哑元，即对于任意的，，使得，那么对任意，使得成立。

（5）可替代性：若是可替代的局中人，即，，则。

（6）如果，对于任意的，存在，使得下式成立：。

2 权重图博弈有效解及其公理化

本节建立在τ值的基础上，通过引入权重，向图博弈有效解做出推广。 这里我们分为两个部分介绍：2.1节提出了权重图博弈有效解;2.2节对权重图博弈有效解进行了公理性刻画。

2.1 权重图博弈有效解的提出

在本小节中，我们考虑各分支联盟进行合作而形成大聯盟的收益大于各分支联盟收益之和的情况， 即对于任意的，有成立。建立在此基础上，我们提出基于值的权重图博弈有效解。

定义2.1  对于任意的拟均衡图博弈， 存在一个测度函数， 并且该测度函数给予每一个局中人 一个正值， 对于任意给定的测度函数， 其权重图博弈有效解， 记作：

，.

根据权重图博弈有效解的定义，我们可以发现这一分配规则对于每一位局中人， 首先分配给其τ值，再根据占的权重分配大联盟收益与各个分支联盟收益之和的剩余值，即。 如果取 且，则权重图博弈有效解与剩余平等分配解等价; 因为权重图博弈满足有效性，特别是如果，则权重图博弈有效解与图博弈的τ值等价。 因此，权重图博弈有效解不仅是剩余平等解的扩展，还是图博弈τ值的一个推广。

2.2 权重图博弈有效解的公理化

在本小节中，对2.1节提出的权重图博弈有效解做进一步研究，主要涉及有效权重解满足的性质以及其公理化过程。

引理2.1 令且，对于图博弈其上向量、间隙函数与让步向量分别为：

，

，

，

由于，故有.

定理2.1  对于任意拟均衡博弈，权重图博弈解满足：

（1）有效性;（2）个体理性;（3）均衡下的相对不变性;

（4）线性限制权重成比例：对于任意且对于任意的和;满足;对于任意， 存在实数，使得任意局中人，有

成立;

（5）剩余比例分配：任意两个局中人，如果脱离大联盟而形成各自的分支联盟，其收益的变化与各自的测度函数成比例。具体对于拟均衡博弈，任意的局中人， 有以下公式成立：

.

证明 （1）有效性。由于

.

因此，权重图博弈有效解满足有效性。

（2）个体理性。由定义2.1可知

，.

由于，有，进而有 。根据已知，易得对于任意的，有，故

.

因此，权重图博弈有效解满足个人理性。

（3）均衡下的相对不变性。 由引理2.1可知权重图博弈有效解满足均衡下的相对不变性。 对于任意的，，

，.

（4）对于线性限制权重成比例。且对 ， ， 假设成立，如果 ，则令;如果，则令。因此， 根据定义2.1可知，权重图博弈有效解满足线性限制权重成比例性。

（5）剩余有效权重分配。对于任意，我们有：

因此，权重图博弈有效解满足剩余有效权重分配。

引理2.2   令，由于， ，并根据，得到下式，.

定理2.2 对于任意拟均衡博弈，权重图博弈有效解是满足有效性，均衡下的相对不变性，线性限制权重成比例以及剩余有效权重分配的唯一解。

证明  假设是在拟均衡博弈上满足有效性、均衡下的相对不变性、线性限制权重成比例，以及剩余有效权重分配的一个分配规则。 接下来我们证明，对于，有成立。 对于任意的，满足剩余有效权重分配，即存在一个常数，使得                        .

又由于满足有效性，则有.

因此，对于任意局中人，有下式成立，

.

进而有下式成立，

.

对于的子博弈，也满足有效性，则下式成立，

.

因此，可得

.

同理，根据定义2.1可知，有下式成立，

.

综上所述，对于任意的，有下式成立，

.

令并且.因为，则. 由于与 均满足S均衡下的相对不变性，因此有

，

.

那么，想要证明，证明即可。

由得

根据引理2.2，再由线性限制权重成比例性，对于任意，都存在两个实数分别为使得下式成立

，

.

由于，

.

又因为 ， 因此. 由此可得对于任意的， 有成立， 进而有成立，即成立。 定理得证！

3 基于权重图博弈有效解的特殊分配规则

权重图博弈有效解是剩余平等分配解的推广，相比于剩余平等分配解，权重图博弈有效解包含了更为一般的情况， 建立在权重图博弈有效解的基础上，本节提出了以下几种分配规则， 虽然他们是权重图博弈有效解的特殊情况，但是在使用他们研究分配问题时却有着不同的倾向和侧重点。

3.1 剩余平等分配解

当每个局中人的权重均相同时，即 ，可以得到剩余平等分配，该分配的具体表达为：

定义3.1 （个人剩余公平性）对于任意拟均衡博弈，任意的，有变量满足如下关系：

定理3.1  剩余平等分配解是满足有效性、均衡下的相对不变性、剩余公平性与限制成比例性的唯一解。

这一分配方式公理化的具体证明过程省略，该证明方式以定义2.1与定理2.2为依据与定理2.1证明过程类似。

3.2 剩余度分配解

当每个局中人的权重与其相连通的人数成比例时，，可以得到剩余度分配，该分配的具体表达：

定義3.2  （剩余度公平性）对于任意拟均衡博弈，任意的，有变量满足如下关系：

定义3.3 （线性限制度值成比例）对于任意且对于任意的和;满足;对于任意，存在实数，使得任意局中人， 有 成立。

定理3.2   剩余度分配解是满足有效性、S均衡下的相对不变性、剩余度公平性以及限行限制度值成比例的唯一解。

具体证明过程省略，与定理3.1证明过程类似。

3.3 举例

考虑拟均衡图博弈，局中人的集合为; 特征函数为 其中表示其他联盟。 ;通讯图，用 表示两大分支，分别为。 根据分配规则，τ值、剩余平等分配解、剩余度分配解的结果如表1所示。

根据分配结果我们可以发现，三大分配规则均满足局中人联系越广泛收益越高的原则。将剩余度分配解与剩余平等分配解相比较发现，剩余度分配解对剩余的分配更有利于个人能力强的局中人，即合作密度越大，则收益所得越高;剩余平等分配对于剩余的分配更有利于弱势群体，个人能力小的局中人所获得的剩余比在剩余度分配解中能力小的局中人获得收益更多。 因此，对于合作密度更大的局中人，剩余度分配解分配给他们的更多;对于合作密度更小的局中人，剩余平等分配解分配给他们的更少。

4 结语

本文提出了一种基于τ值的分配规则，并根据新的公理完成两个具体分配规则的公理化。作为对经典τ值的推广，第一，提出线性限制成比例、剩余比例分配，建立在这一基础上公理化权重图博弈有效解。 第二，提出个人剩余公平性、剩余度公平性，进而可公理化剩余平等分配解以及剩余度公平分配解这两个特殊分配规则，并对比这两种特殊分配规则在具体情境下的分配情况。我们发现对于剩余度分配解更有利于机理能力强的局中人，而剩余平等分配解更关注弱势群体。

参考文献

Myerson R B. Graphs and cooperation in games[J]. Mathematics of Operations Research， 1977（2）：225-229.

Tijs H.Bounds for the core and the T-value.Moeschlin O.and Pallaschke D.（eds.），Game Theory and Mathematical Economics， North-Holland，1981.

王文文，孙浩，韩卫彬.图限制下合作对策的τ值[J].运筹学学报，2011，15（4）：75-84.

Kamijo Y.A two-step Shapley value for cooperative games with coalition structures [J]. International Game Theory Review， 2009， 11

Guang Zhang， Erfang Shan， Liying Kang， Yanxia Dong， Two efficient values of cooperative games with graph structure based on τ-value[J]. Journal of Combinatorial Optimization， 2017， 34（2）： 462-482.

Sylvain Béal， Eric Rémila， Philippe Solal. Fairness and fairness for neighbors：The difference between the Myerson value and component-wise egalitarian solutions[J]. Economics Letters， 2012，117（1）：263-267.

Erfang Shan，Guang Zhang，Yanxia Dong.Component-wise proportional solutions for communication graph games[J].Mathematical Social Sciences，2016（81）：22-28.

Jilei Shi，Erfang Shan.Weighted component-wise solutions for graph games[J].Economics Letters，2020.

van den Brink R， Khmelnitskaya A， van der Laan G. An efficient and fair solution for communication graph games [J]. Economics Letters， 2012， 117 （3）： 786–789.

Hu X F，Li D F， Xu G J.Fair distribution of surplus and efficient extensions of the Myerson value[J]. Economics Letters，2018，165：1-5.

Erfang Shan， Jiayu Han，Jilei Shi.The efficient proportional Myerson values[J].Operations Research Letters，2019，47（6）： 574-578.

Efficient Weight Allocation Rules for Graph Game Based on τValue

School of Statistics and Information， Shanghai University of International Business and Economics

XUE Tao  DONG Yanxia

Abstract： Firstly， the effective solution of the weight graph game based on τvalue is proposed， and this single-valued solution is both a generalization of τvalue of under the graph game and an extension of the solution based on the remaining average distribution of τ. Secondly， the effective solution of the weight graph game is axiomatic described by using branch validity， relative invariance under S-equilibrium， residual effective weight distribution and linear limited weight proportion. Finally， a special allocation rule based on the effective solution of weight graph game is introduced.

Keywords： graph structure; efficient solution; τvalue; component efficiency