The Shapley value for cooperative games under precedence constraints

Cooperative games are considered where only those coalitions of players are feasible that respect a given precedence structure on the set of players. Strengthening the classical symmetry axiom, we obtain three axioms that give rise to a unique Shapley value in this model. The Shapley value is seen to reflect the expected marginal contribution of a player to a feasible random coalition, which allows us to evaluate the Shapley value nondeterministically. We show that every exact algorithm for the Shapley value requires an exponential number of operations already in the classical case and that even restriction to simple games is #P-hard in general. Furthermore, we outline how the multi-choice cooperative games of Hsiao and Raghavan can be treated in our context, which leads to a Shapley value that does not depend on pre-assigned weights. Finally, the relationship between the Shapley value and the permission value of Gilles, Owen and van den Brink is discussed. Both refer to formally similar models of cooperative games but reflect complementary interpretations of the precedence constraints and thus give rise to fundamentally different solution concepts.     

Interaction indices for games on combinatorial structures with forbidden coalitions

The notion of interaction among a set of players has been defined on the Boolean lattice and Cartesian products of lattices. The aim of this paper is to extend this concept to combinatorial structures with forbidden coalitions. The set of feasible coalitions is supposed to fulfil some general conditions. This general representation encompasses convex geometries, antimatroids, augmenting systems and distributive lattices. Two axiomatic characterizations are obtained. They both assume that the Shapley value is already defined on the combinatorial structures. The first one is restricted to pairs of players and is based on a generalization of a recursivity axiom that uniquely specifies the interaction index from the Shapley value when all coalitions are permitted. This unique correspondence cannot be maintained when some coalitions are forbidden. From this, a weak recursivity axiom is defined. We show that this axiom together with linearity and dummy player are sufficient to specify the interaction index. The second axiomatic characterization is obtained from the linearity, dummy player and partnership axioms. An interpretation of the interaction index in the context of surplus sharing is also proposed. Finally, our interaction index is instantiated to the case of games under precedence constraints.     

A value for partially defined cooperative games

The Shapley value provides a method, which satisfies certain desirable axioms, of allocating benefits to the players of a cooperative game. When there aren players andn is large, the Shapley value requires a large amount of accounting because the number of coalitions grows exponentially withn. This paper proposes a modified value that shares some of the axiomatic properties of the Shapley value yet allows the consideration of games that are defined only for certain coalitions. Two different axiom systems are shown to determine the same modified value uniquely.     

基于图对策的收益分配

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

Owen coalitional value without additivity axiom

We show that the Owen value for TU games with coalition structure can be characterized without the additivity axiom similarly as it was done by Young for the Shapley value for general TU games. Our axiomatization via four axioms of efficiency, marginality, symmetry across coalitions, and symmetry within coalitions is obtained from the original Owen’s one by the replacement of additivity and null-player via marginality. We show that the alike axiomatization for the generalization of the Owen value suggested by Winter for games with level structure is valid as well. The research was supported by NWO (The Netherlands Organization for Scientific Research) grant NL-RF 047.017.017.     

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.     

A new axiomatization of the Shapley–solidarity value for games with a coalition structure

In this paper, we propose a new kind of players as a compromise between the null player and the A-null player. It turns out that the axiom requiring this kind of players to get zero-payoff together with the well-known axioms of efficiency, additivity, coalitional symmetry, and intra-coalitional symmetry characterize the Shapley–solidarity value. This way, the difference between the Shapely–solidarity value and the Owen value is pinpointed to just one axiom.     

Players indifferent to cooperate and characterizations of the Shapley value

In this paper we provide new axiomatizations of the Shapley value for TU-games using axioms that are based on relational aspects in the interactions among players. Some of these relational aspects, in particular the economic or social interest of each player in cooperating with each other, can be found embedded in the characteristic function. We define a particular relation among the players that it is based on mutual indifference. The first new axiom expresses that the payoffs of two players who are not indifferent to each other are affected in the same way if they become enemies and do not cooperate with each other anymore. The second new axiom expresses that the payoff of a player is not affected if players to whom it is indifferent leave the game. We show that the Shapley value is characterized by these two axioms together with the well-known efficiency axiom. Further, we show that another axiomatization of the Shapley value is obtained if we replace the second axiom and efficiency by the axiom which applies the efficiency condition to every class of indifferent players. Finally, we extend the previous results to the case of weighted Shapley values.     

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

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

The Shapley value,the Proper Shapley value,and sharing rules for cooperative ventures

In this note, we discuss two solutions for cooperative transferable utility games, namely the Shapley value and the Proper Shapley value. We characterize positive Proper Shapley values by affine invariance and by an axiom that requires proportional allocation of the surplus according to the individual singleton worths in generalized joint venture games. As a counterpart, we show that affine invariance and an axiom that requires equal allocation of the surplus in generalized joint venture games characterize the Shapley value.     

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 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 Owen value values friendship

This paper presents two new axiomatizations of the Owen value for games with coalition structures. Two associated games are defined and a consistency axiom is required. The construction of the associated games presupposes that coalitions behave in an aggressive manner towards players who are not members of the same unions and in a friendly manner towards players that do belong to their unions. The consistency axiom necessitates the definition of only one associated game which is not a reduced game. Received: February 1999/Revised version: January 2000     

The Harsanyi paradox and the “right to talk” in bargaining among coalitions

We describe a coalitional value from a non-cooperative point of view, assuming coalitions are formed for the purpose of bargaining. The idea is that all the players have the same chances to make proposals. This means that players maintain their own “right to talk” when joining a coalition. The resulting value coincides with the weighted Shapley value in the game between coalitions, with weights given by the size of the coalitions. Moreover, the Harsanyi paradox (forming a coalition may be disadvantageous) disappears for convex games.     

On bargaining position descriptions in non-transferable utility games

We present a generalization to the Harsanyi solution for non-transferable utility (NTU) games based on non-symmetry among the players. Our notion of non-symmetry is presented by a configuration of weights which correspond to players' relative bargaining power in various coalitions. We show not only that our solution (i.e., the bargaining position solution) generalizes the Harsanyi solution, (and thus also the Shapley value), but also that almost all the non-symmetric generalizations of the Shapley value for transferable utility games known in the literature are in fact bargaining position solutions. We also show that the non-symmetric Nash solution for the bargaining problem is also a special case of our general solution. We use our general representation of non-symmetry to make a detailed comparison of all the recent extensions of the Shapley value using both a direct and an axiomatic approach.     

On the Convenience to Form Coalitions or Partnerships in Simple Games

A partnership in a cooperative game is a coalition that possesses an internal structure and, simultaneously, behaves as an individual member. Forming partnerships leads to a modification of the original game which differs from the quotient game that arises when one or more coalitions are actually formed. In this paper, the Shapley value is used to discuss the convenience to form either coalitions or partnerships. To this end, the difference between the additive Shapley value of the partnership in the partnership game and the Shapley alliance value of the coalition, and also between the corresponding value of the internal and external players, are analysed. Simple games are especially considered. Research partially supported by Grant BFM 2003-01314 of the Science and Technology Spanish Ministry and the European Regional Development Fund.     

The collective value: a new solution for games with coalition structures

In this study, we provide a new solution for cooperative games with coalition structures. The collective value of a player is defined as the sum of the equal division of the pure surplus obtained by his coalition from the coalitional bargaining and of his Shapley value for the internal coalition. The weighted Shapley value applied to a game played by coalitions with coalition-size weights is assigned to each coalition, reflecting the size asymmetries among coalitions. We show that the collective value matches exogenous interpretations of coalition structures and provide an axiomatic foundation of this value. A noncooperative mechanism that implements the collective value is also presented.     

A Shapley function on a class of cooperative fuzzy games

In this paper, we make a study of the Shapley values for cooperative fuzzy games, games with fuzzy coalitions, which admit the representation of rates of players' participation to each coalition. A Shapley function has been introduced by another author as a function which derives the Shapley value from a given pair of a fuzzy game and a fuzzy coalition. However, the previously proposed axioms of the Shapley function can be considered unnatural. Furthermore, the explicit form of the function has been given only on an unnatural class of fuzzy games. We introduce and investigate a more natural class of fuzzy games. Axioms of the Shapley function are renewed and an explicit form of the Shapley function on the natural class is given. We make sure that the obtained Shapley value for a fuzzy game in the natural class has several rational properties. Finally, an illustrative example is given.     

Implementation of weighted values in hierarchical and horizontal cooperation structures

This paper studies a non-cooperative mechanism implementing a cooperative solution for a situation in which members of a society are subdivided into groups and/or coalitions and there is asymmetry among the individuals of the society. To describe hierarchical and horizontal cooperation structure simultaneously, we present unified classes of games, the games with social structure, and define a weighted value for these games. We show that our mechanism works in any zero-monotonic environment and implements the Shapley value, the weighted Shapley value, the Owen’s coalitional value, and the weighted coalitional value, in some special cases.