图上合作博弈和图的边密度

1977年, Myerson建立了以图作为合作结构的可转移效用博弈模型(也称图博弈), 并提出了一个分配规则, 也即"Myerson 值", 它推广了著名的Shapley值. 该模型假定每个连通集合(通过边直接或间接内部相连的参与者集合)才能形成可行的合作联盟而取得相应的收益, 而不考虑连通集合的具体结构. 引入图的局部边密度来度量每个连通集合中各成员之间联系的紧密程度, 即以该连通集合的导出子图的边密度来作为他们的收益系数, 并由此定义了具有边密度的Myerson值, 证明了具有边密度的Myerson值可以由"边密度分支有效性"和"公平性"来唯一确定.     

超图结构上合作博弈的赋权Position值

在合作博弈的一般模型中总是假设所有联盟都能形成。不过,在实际中由于受到一些因素的制约,有些联盟是不能形成的。基于此,Myerson提出了具有图通讯结构的合作博弈。Myerson值和Position值是超图博弈上的两个重要分配规则。2005年,Slikker给出了在图博弈上Position值的公理化刻画。但超图博弈上Position值的公理化刻画一直悬而未决。本文通过引入“赋权平衡超边贡献公理”,并结合经典的“分支有效性”,提出了超图博弈上赋权Position值的公理化刻画。作为推论,解决了超图博弈上Position值的公理化刻画问题。     

超图对策的组内和组间位置值

本文研究超图对策位置值的分解问题。1988年,Meessen考虑到以图为合作结构的对策中边在合作中的作用,提出了一个重要的分配规则,这个规则被称为位置值(Position value)。本文通过考虑超图的每条超边不仅对关联于它的联盟中的参与者的收益产生影响,同时作为中介也对不关联于它的联盟中的参与者的收益产生间接影响,引入超图对策的组内Position值和组间Position值,以区分参与者收益的成分。本文首先给出这两类值的公理化刻画。其次,通过案例对超图对策的组内Position值和组间Position值进行了分析,并讨论了中介费用不合理情况下的改进分配方案。     

边赋权图支撑树权的介值性

有关图的介值性,已有若干较好的结果,但这些结果都未涉及图的赋权。本文考虑边赋权图支撑树权的介值性。证明了定理A 设双射w:E(G)→{1,2,…|E(G)|}是连通图G=(V(G),E(G))的边赋权,如果存在G的圈基使w在它的每个圈上的象集为连续整数集,则w((G))={w(e)|T∈J(G)}是连续整数集。其中(G)是G的支撑树的集合。     

有效商Myerson值的公理化刻画

在具有图结构的合作对策中，Myerson值(Myerson, 1977)是一个著名的分配规则，它可以由分支有效性和公平性或者平衡贡献性所唯一确定。在实际中，图结构可能并不影响大联盟的形成，只是由于参与者在网络中所处的位置不同，对其讨价还价能力会产生影响。换句话说，图结构会对分配格局产生影响，但对大联盟的形成没有影响。这促使人们开始考虑Myerson值的有效推广问题。文献中已经提出了Myerson的几种有效推广形式。2020年，Li和Shan提出了有效商Myerson值并给出了公理化刻画，它是Myerson值一种新的有效推广形式。本文首先引入了准商盈余公平性这一性质，然后结合有效性和Myerson值黏性给出了有效商Myerson值的新公理化刻画。其次，通过应用案例，将该值和其他值做了比较分析。     

基于图对策的收益分配

基于具有交流结构的合作对策,即图对策,对平均树解拓展形式的特征进行刻画,提出此解满足可加性公理。进一步地,分析了对于无圈图对策此解是分支有效的。并且当连通分支中两个局中人相关联的边删掉后,此连通分支的收益变化情况可用平均树解表示。这一性质是Shapley值和Myerson值所不具有的。最后,我们给出了模糊联盟图对策中模糊平均树解的可加性和分支有效性。     

具有超图合作结构的赋权Position值

具有超图交流结构的可转移效用合作对策,也称为超图对策,它由一个三元组(N,v,H)所组成,其中(N,H)是一个可转移效用对策(简称TU-对策),而(N,H)是一个超图(超网络)。在超图对策中,除Myerson值(Myerson)外,Position值(Meessen)是另一个重要的分配规则。该模型要求把超图结构中每条超边Shapley的值平均分配给它所包含的点,而不考虑每个点的交流能力或合作水平。本文引入超图结构中点的度值来度量每条超边中每个点的交流能力或合作水平,并结合Haeringer提出用于推广Shapley值的权重系统,并由此定义了具有超图合作结构的赋权Position值。我们证明了具有超图合作结构的赋权Position值可以由“分支有效性”、“冗余超边性”、“超边可分解性”、“拟可加性”、“弱积极性”和“弱能转换”六个性质所唯一确定,并且发现参与者获得的支付随其度值的增加而增加,参与者分摊的成本随其度值的增加而降低。     

图的k-单圈划分中的优化问题

图的划分问题曾引起图论界的广泛关注，在文献[4]中讨论了k-单圈划分，本文进一步研究基于k-单圈划分的优化问题，即在一个赋权图中求一个最小权可k-单圈划分的支撑子图，以及对一个不存在k-单圈划分支撑子图的图，如何添最少的边使得它有k-单圈划分的支撑子图。     

基于Solidarity值的河流水资源分配

河流水资源分配问题可以抽象为图限制下合作对策解的模型.基于图限制下合作对策的Solidarity值对参与者的收益分配进行分析,构造了Solidarity值的结构,给出了该值的分支有效性等四个性质,并利用这四个性质刻画了Solidarity值的唯一性.最后通过一个简单的实例,证明了河流水资源分配问题中,基于Solidarity值的收益分配比Myerson值更优.     

赋权二部图最大匹配的灵敏分析

本主要从理论上讨论赋权二部图的权的变化对最优解的影响，并在原最大权匹配的基础上给出求解权值变化后的最大权匹配的算法。     

基于平均树值的无圈图博弈有效解

本文对无圈图博弈进行了研究,考虑了大联盟收益不小于各分支收益之和的情况。通过引入剩余公平分配性质,也就是任意两个分支联盟的平均支付变化相等,给出了一个基于平均树值的无圈图博弈有效解。同时,结合有效性和分支公平性对该有效解进行了刻画。特别地,若无圈图博弈满足超可加性时,证明了该有效解一定是核中的元素,说明此时的解是稳定的。最后,通过一案例分析了该有效解的特点,即越大的分支分得的剩余越多,并且关键参与者,也就是具有较大度的参与者可获得相对多的支付。     

The efficient proportional Myerson values

In this paper we introduce a class of efficient extensions of the Myerson value for games with communication graph structures in which the surplus is allocated in proportion to measures defined on the graph. We show that the efficient proportional Myerson values can be characterized by efficiency, coherence with the Myerson value for connected graphs, and $\alpha$-fairness of surplus. The axiomatization implies a new characterization of the efficient egalitarian Myerson value proposed by van den Brink et al. (2012).     

Axiomatization of the Shapley value using the balanced cycle contributions property

This paper presents an axiomatization of the Shapley value. The balanced cycle contributions property is the key axiom in this paper. It requires that, for any order of all the players, the sum of the claims from each player against his predecessor is balanced with the sum of the claims from each player against his successor. This property is satisfied not only by the Shapley value but also by some other values for TU games. Hence, it is a less restrictive requirement than the balanced contributions property introduced by Myerson (International Journal of Game Theory 9, 169–182, 1980).     

The Myerson value for directed graph games

A directed graph game consists of a cooperative game with transferable utility and a digraph which describes limited cooperation and the dominance relation among the players. Under the assumption that only coalitions of strongly connected players are able to fully cooperate, we introduce the digraph-restricted game in which a non-strongly connected coalition can only realize the sum of the worths of its strong components. The Myerson value for directed graph games is defined as the Shapley value of the digraph-restricted game. We establish axiomatic characterizations of the Myerson value for directed graph games by strong component efficiency and either fairness or bi-fairness.     

On the convexity of communication games

A communication situation consists of a game and a communication graph. By introducing two different types of corresponding communication games, point games and arc games, the Myerson value and the position value of a communication situation were introduced. This paper investigates relations between convexity of the underlying game and the two communication games. In particular, assuming the underlying game to be convex, necessary and sufficient conditions on the communication graph are provided such that the communication games are convex. Moreover, under the same conditions, it is shown that the Myerson value and the posi tion value are in the core of the point game. Some remarks are made on superadditivity and balancedness.     

Tree,web and average web values for cycle-free directed graph games

On the class of cycle-free directed graph games with transferable utility solution concepts, called web values, are introduced axiomatically, each one with respect to a chosen coalition of players that is assumed to be an anti-chain in the directed graph and is considered as a management team. We provide their explicit formula representation and simple recursive algorithms to calculate them. Additionally the efficiency and stability of web values are studied. Web values may be considered as natural extensions of the tree and sink values as has been defined correspondingly for rooted and sink forest graph games. In case the management team consists of all sources (sinks) in the graph a kind of tree (sink) value is obtained. In general, at a web value each player receives the worth of this player together with his subordinates minus the total worths of these subordinates. It implies that every coalition of players consisting of a player with all his subordinates receives precisely its worth. We also define the average web value as the average of web values over all management teams in the graph. As application the water distribution problem of a river with multiple sources, a delta and possibly islands is considered.     

Splitting graphs when calculating Myerson value for pure overhead games

A communication situation consists of a coalitional game and a graph, the nodes of the graph corresponding to the players of the game. To calculate the Myerson value for such situations, we obtain results which extend those well known for trees and cycle-complete graphs. On the other hand, in order to reduce the associated calculus for communication situations with a pure overhead game, the possibility of splitting the graph in several subgraphs is analyzed. For each fixed decomposition of the graph, a subspace of games compatible with this decomposition is given.