边赋权图对策Myerson值的和分解

2003年,Gómez等在考虑社会网络中心性度量时,引入了对称对策上Myerson值的和分解概念,本文将这一概念推广到边赋权图对策上,给出了相应于边赋权图对策的组内Myerson值和组间Myerson值。其中边的权表示这条边的两个端点之间的直接通讯容量,组内Myerson值衡量了每个参与者来自它所在联盟的收益,而组间Myerson值评估了参与者作为其他参与者中介所获取的收益。本文侧重分析了边赋权图对策的组内Myerson值和组间Myerson值的权稳定性和广义稳定性, 并给出了这两类值的刻画。     

超网络博弈的位置值的公理化刻画

在图博弈中,Myerson假设只有连通的联盟才能获得完全的效用,而忽略连通联盟的具体结构.1996年,Jackson和Wolinsky提出了“网络情形博弈”的模型,拓展了Myerson的图博弈模型.它是利用值函数代替原来的特征函数以体现不同网络结构对合作结果的影响.考虑超网络情形博弈,它是网络情形博弈的自然推广,由三元组（N,H,v）所组成,这里v是值函数,用于描述在超网络（N,H）合作结构下的合作收益.2012年,van den Nouweland和Slikker利用四个公理给出了位置值的公理化刻画.通过分支有效性和局部平衡超边贡献性两个公理,给出了超网络博弈中位置值的公理化刻画.作为推论,得到了网络博弈中位置值的新刻画.     

基于图对策的收益分配

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

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

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

张量积图的Tutte多项式及其应用

图G为具有m条边的连通图,E(G)={e₁,e₂,…,e_m},H={H₁,H₂,…,H_m}为由m个连通图构成的集合.图G[H]为G与H的张量积图,即对每个i(1≤i≤m),e_i被H_i替代而得到的图.张量积这一图运算包含了多个边替代图运算,例如细分、三角化、钻石化等图运算.本文中,我们给出了G[H]的Tutte多项式的显式表达式,进而得到了细分图、三角化图、钻石化图等运算图的Tutte多项式和生成树数目.     

基于矩阵方法的Myerson值的一种规范化

在合作对策中,将一个值规范化意味着让其满足有效性.Hamiache利用矩阵方法得到了带图结构效用可转移合作对策Myerson值的一种规范化.通过给出一种新的满足最小划分唯一性的集合簇,本文利用矩阵方法得到了Myerson值的另一种规范化.特殊地,当所考虑的图结构在各连通分支上的限制均为完全图时,文中给出了带联盟结构效用可转移合作对策AumannDrèze值的一种规范化.与其它Myerson值规范化的比较分析表明本文规范化与van den Brink等的等价.由此van den Brink等的规范化与Hamiache的规范化都可用矩阵方法来描述,而它们之间的区别则被归结于满足最小划分唯一性的集合簇之不同.     

极大3限制边连通二部图的充分条件

设G=(V,E)是一个连通图.称一个边集合S■E是一个k限制边割,如果G-S的每个连通分支至少有k个顶点.称G的所有k限制边割中所含边数最少的边割的基数为G的k限制边连通度,记为λ_k(G).定义ξ_k(G)=min{[X,■]:|X|=k,G[X]连通,■=V(G)\X}.称图G是极大k限制边连通的,如果λ_k(G)=ξ_k(G).本文给出了围长为g>6的极大3限制边连通二部图的充分条件.     

有效商Myerson值的公理化刻画

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

整数流与子图覆盖

整数流和子图覆盖是当今图论领域的两个重要研究方向,与著名的四色问题密切相关.四色问题等价于平面图的整数4-流问题.一个图有整数k-流,当且仅当对该图的某个定向,存在从边集合到k阶交换群的一个函数,使得对图中每个点,进入该点的边函数值之和等于离开该点的边函数值之和.整数流理论与数学其他领域一些著名问题有一定的关联,如组合学的孤独跑步者、数论的丢番图逼近、几何学的视线阻碍和线性空间堆垒基等.四色问题还等价于平面图的偶子图覆盖问题:是否存在3个偶子图,覆盖一个2-边连通平面图的每条边恰好两次.著名的Fulkerson猜想认为,对每个2-边连通图(不必是平面图),存在6个偶子图,覆盖该图的每条边恰好4次.本文对整数流和子图覆盖这两个研究方向及相关问题的历史和现状作一个综述.     

n 阶临界3-边连通图的最大边数

本文中未经说明的术语和记号采自[2].设 G=(V,E)是一个简单图。G 的顶点数记作 n(G),边数记作 m(G),即 n(G)=|V|,m(G)=|E|.假设 G 是3-边连通图.G 的顶点 v(?)V 称为 G 的临界点,如果 G-v 不是3-边连通的;否则称为 G 的非临界点.如果每个 v(?)V 都是 G 临界点,则称 G 是临界3-边连通图.临界3-边连通图类记作 A,A_n 是 A 中所有 n 阶图的集合.假设 G(?)A,则对每个 v∈A,     

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.     

The core and the Weber set of games on augmenting systems

This paper deals with cooperative games in which only certain coalitions are allowed to form. There have been previous models developed to confront the problem of unallowable coalitions. Games restricted by a communication graph were introduced by Myerson and Owen. In their model, the feasible coalitions are those that induce connected subgraphs. Another type of model is introduced in Gilles, Owen and van den Brink. In their model, the possibilities of coalition formation are determined by the positions of the players in a so-called permission structure. Faigle proposed a general model for cooperative games defined on lattice structures. In this paper, the restrictions to the cooperation are given by a combinatorial structure called augmenting system which generalizes antimatroid structure and the system of connected subgraphs of a graph. In this framework, the core and the Weber set of games on augmenting systems are introduced and it is proved that monotone convex games have a non-empty core. Moreover, we obtain a characterization of the convexity of these games in terms of the core of the game and the Weber set of the extended game.     

Axiomatizations of the Shapley value for games on augmenting systems

This paper deals with cooperative games in which only certain coalitions are allowed to form. There have been previous models developed to confront the problem of unallowable coalitions. Games restricted by a communication graph were introduced by Myerson and Owen. In their model, the feasible coalitions are those that induce connected subgraphs. Another type of model is introduced in Gilles, Owen and van den Brink. In their model, the possibilities of coalition formation are determined by the positions of the players in a so-called permission structure. Faigle proposed another model for cooperative games defined on lattice structures. We introduce a combinatorial structure called augmenting system which is a generalization of the antimatroid structure and the system of connected subgraphs of a graph. In this framework, the Shapley value of games on augmenting systems is introduced and two axiomatizations of this value are showed.     

The Myerson Value and Superfluous Supports in Union Stable Systems

In this paper, the set of feasible coalitions in a cooperative game is given by a union stable system. Well-known examples of such systems are communication situations and permission structures. Two games associated with a game on a union stable system are the restricted game (on the set of players in the game) and the conference game (on the set of supports of the system). We define two types of superfluous support property through these two games and provide new characterizations for the Myerson value. Finally, we analyze inheritance of properties between the restricted game and the conference game.     

Games on fuzzy communication structures with Choquet players

Myerson (1977) used graph-theoretic ideas to analyze cooperation structures in games. In his model, he considered the players in a cooperative game as vertices of a graph, which undirected edges defined their communication possibilities. He modified the initial games taking into account the graph and he established a fair allocation rule based on applying the Shapley value to the modified game. Now, we consider a fuzzy graph to introduce leveled communications. In this paper players play in a particular cooperative way: they are always interested first in the biggest feasible coalition and second in the greatest level (Choquet players). We propose a modified game for this situation and a rule of the Myerson kind.     

Games with externalities: games in coalition configuration function form

In this paper we introduce a model of cooperative game with externalities which generalizes games in partition function form by allowing players to take part in more than one coalition. We provide an extension of the Shapley value (1953) to these games, which is a generalization of the Myerson value (1977) for games in partition function form. This value is derived by considering an adaptation of an axiomatic characterization of the Myerson value (1977).     

The consistent Shapley value for hyperplane games

A new value is defined for n-person hyperplane games, i.e., non-sidepayment cooperative games, such that for each coalition, the Pareto optimal set is linear. This is a generalization of the Shapley value for side-payment games. It is shown that this value is consistent in the sense that the payoff in a given game is related to payoffs in reduced games (obtained by excluding some players) in such a way that corrections demanded by coalitions of a fixed size are cancelled out. Moreover, this is the only consistent value which satisfies Pareto optimality (for the grand coalition), symmetry and covariancy with respect to utility changes of scales. It can be reached by players who start from an arbitrary Pareto optimal payoff vector and make successive adjustments.