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

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

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.     

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.     

基于图对策的收益分配

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

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

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

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).     

Harsanyi power solutions for graph-restricted games

We consider cooperative transferable utility games, or simply TU-games, with limited communication structure in which players can cooperate if and only if they are connected in the communication graph. Solutions for such graph games can be obtained by applying standard solutions to a modified or restricted game that takes account of the cooperation restrictions. We discuss Harsanyi solutions which distribute dividends such that the dividend shares of players in a coalition are based on power measures for nodes in corresponding communication graphs. We provide axiomatic characterizations of the Harsanyi power solutions on the class of cycle-free graph games and on the class of all graph games. Special attention is given to the Harsanyi degree solution which equals the Shapley value on the class of complete graph games and equals the position value on the class of cycle-free graph games. The Myerson value is the Harsanyi power solution that is based on the equal power measure. Finally, various applications are discussed.     

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

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

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.     

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.     

The degree value for games with communication structure

A new value concept, called degree value, is proposed by employing the degree game induced by an original game for hypergraph communication situations (including graph communication situations). We provide an axiomatic characterization of the degree value for arbitrary hypergraph communication situations by applying component efficiency and balanced conference contributions, which is a natural extension of balanced link contributions introduced in Slikker (Int J Game Theory 33:505–514, 2005) for graph communication situations. By comparing the degree value with the position value and the Myerson value, it is verified that the degree value is a new allocation rule that differs from both the Myerson value and the position value, and the degree value highlights the important role of the degree of a player in hypergraph communication situations. Particularly, in a uniform hypergraph communication situation, where every conference contains the same number of players, we show that the degree value coincides with the position value.     

A value for generalized probabilistic communication situations

We introduce in this work an extension of the model of games with probabilistic graphs arising in Calvo et al. (1999, Math. Soc. Sci. 37, 79), which itself generalizes the one developed by Myerson (1977, Math. of Oper. Res. 2, 225) for games with communications restrictions. In the first of these models, each pair of nodes has a given probability of direct communication. In this paper a more general setting is considered: we suppose that a probability distribution over the set of all possible communication networks among the players is given. A generalization of the Myerson value is defined and characterized in this context.     

Cost allocation in the Chinese postman problem

This paper considers a cost allocation problem that arises from a delivery problem associated with the Chinese postman problem (CPP). A delivery problem is described by a connected undirected graph in which each edge belongs to a different player, a cost function on the edges of this graph and a fixed vertex which is referred to as the post office. Assume that the post office is providing some service to the players. The nature of this service, which can be thought of as mail delivery, requires that a server will travel along the edges of the graph and returns to the post office. The cost allocation problem is concerned with the cost of providing the service to all players. A specific cost allocation rule is introduced and characterized. Further, the class of delivery problems gives rise to a new class of cooperative combinatorial optimization games called delivery games. It is shown that the outcome of the allocation rule with respect to a bridge-connected Euler graph is a core element of the corresponding delivery 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.     

Parameterized fairness axioms on cycle-free graph games

We study cooperative transferable utility games with a communication structure represented by an undirected graph, i.e., a group of players can cooperate only if they are connected on the graph. This type of games is called graph games and the best-known solution for them is the Myerson value, which is characterized by the component efficiency axiom and the fairness axiom. Recently the average tree solution has been proposed on cycle-free graph games, and shown to be characterized by the component efficiency axiom and the component fairness axiom. We propose e{\epsilon} -parameterized fairness axiom on cycle-free graph games that incorporates the preceding fairness axioms, and show the existence and the uniqueness of the solution. We then discuss a relationship between the existing and our proposed solutions by a numerical example.     

A linear proportional effort allocation rule

This paper proposes a new class of allocation rules in network games. Like the solution theory in cooperative games of how the Harsanyi dividend of each coalition is distributed among a set of players, this new class of allocation rules focuses on the distribution of the dividend of each network. The dividend of each network is allocated in proportion to some measure of each player’s effort, which is called an effort function. With linearity of the allocation rules, an allocation rule is specified by the effort functions. These types of allocation rules are called linear proportional effort allocation rules. Two famous allocation rules, the Myerson value and the position value, belong to this class of allocation rules. In this study, we provide a unifying approach to define the two aforementioned values. Moreover, we provide an axiomatic analysis of this class of allocation rules, and axiomatize the Myerson value, the position value, and their non-symmetric generalizations in terms of effort functions. We propose a new allocation rule in network games that also belongs to this class of allocation rules.     

Static search games played over graphs and general metric spaces

We define a general game which forms a basis for modelling situations of static search and concealment over regions with spatial structure. The game involves two players, the searching player and the concealing player, and is played over a metric space. Each player simultaneously chooses to deploy at a point in the space; the searching player receiving a payoff of 1 if his opponent lies within a predetermined radius r of his position, the concealing player receiving a payoff of 1 otherwise. The concepts of dominance and equivalence of strategies are examined in the context of this game, before focusing on the more specific case of the game played over a graph. Methods are presented to simplify the analysis of such games, both by means of the iterated elimination of dominated strategies and through consideration of automorphisms of the graph. Lower and upper bounds on the value of the game are presented and optimal mixed strategies are calculated for games played over a particular family of graphs.     

A set of axioms for a value for partition function games

Myerson (1977) derived an efficient value for games in partition function form. In this paper, we present a set of axioms which characterize a different efficient value for such games. This latter value assigns value 0 to dummies and assigns nonnegative values to players in monotone simple games.     

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).