Preserving or removing special players: What keeps your payoff unchanged in TU-games?

If a player is removed from a game, what keeps the payoff of the remaining players unchanged? Is it the removal of a special player or its presence among the remaining players? This article answers this question in a complement study to Kamijo and Kongo (2012). We introduce axioms of invariance from player deletion in presence of a special player. In particular, if the special player is a nullifying player (resp. dummifying player), then the equal division value (resp. equal surplus division value) is characterized by the associated axiom of invariance plus efficiency and balanced cycle contributions. There is no type of special player from such a combination of axioms that characterizes the Shapley value.     

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.     

An axiomatization of the Shapley value using a fairness property

In this paper we provide an axiomatization of the Shapley value for TU-games using a fairness property. This property states that if to a game we add another game in which two players are symmetric then their payoffs change by the same amount. We show that the Shapley value is characterized by this fairness property, efficiency and the null player property. These three axioms also characterize the Shapley value on the class of simple games. Revised August 2001     

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.     

The Shapley value without efficiency and additivity

We provide a new characterization of the Shapley value neither using the efficiency axiom nor the additivity axiom. In this characterization, efficiency is replaced by the gain-loss axiom (Einy and Haimanko, 2011), i.e., whenever the total worth generated does not change, a player can only gain at the expense of another one. Additivity and the equal treatment axiom are substituted by fairness (van den Brink, 2001) or differential marginality (Casajus, 2011), where the latter requires equal productivity differentials of two players to translate into equal payoff differentials. The third axiom of our characterization is the standard dummy player axiom.     

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

Two-step coalition values for multichoice games

We introduce and compare several coalition values for multichoice games. Albizuri defined coalition structures and an extension of the Owen coalition value for multichoice games using the average marginal contribution of a player over a set of orderings of the player’s representatives. Following an approach used for cooperative games, we introduce a set of nested or two-step coalition values on multichoice games which measure the value of each coalition and then divide this among the players in the coalition using either a Shapley or Banzhaf value at each step. We show that when a Shapley value is used in both steps, the resulting coalition value coincides with that of Albizuri. We axiomatize the three new coalition values and show that each set of axioms, including that of Albizuri, is independent. Further we show how the multilinear extension can be used to compute the coalition values. We conclude with a brief discussion about the applicability of the different values.     

最小成本生成树对策上Shapley值的新刻画及其应用

2002年,Kar利用有效性、无交叉补贴性、群独立性和等处理性四个公理对最小成本生成树对策上的Shapley值进行了刻画。本文提出了“群有效性”这一公理,利用这一公理和“等处理性”两个公理,给出了最小成本生成树对策上Shapley值的一种新的公理化刻画。最后,运用最小成本生成树对策的Shapley值,对网络服务的费用分摊问题进行了分析。     

Power Measures and Solutions for Games Under Precedence Constraints

Games under precedence constraints model situations, where players in a cooperative transferable utility game belong to some hierarchical structure, which is represented by an acyclic digraph (partial order). In this paper, we introduce the class of precedence power solutions for games under precedence constraints. These solutions are obtained by allocating the dividends in the game proportional to some power measure for acyclic digraphs. We show that all these solutions satisfy the desirable axiom of irrelevant player independence, which establishes that the payoffs assigned to relevant players are not affected by the presence of irrelevant players. We axiomatize these precedence power solutions using irrelevant player independence and an axiom that uses a digraph power measure. We give special attention to the hierarchical solution, which applies the hierarchical measure. We argue how this solution is related to the known precedence Shapley value, which does not satisfy irrelevant player independence, and thus is not a precedence power solution. We also axiomatize the hierarchical measure as a digraph power measure.     

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.     

Values on regular games under Kirchhoff’s laws

The Shapley value is a central notion defining a rational way to share the total worth of a cooperative game among players. We address a general framework leading to applications to games with communication graphs, where the feasible coalitions form a poset whose all maximal chains have the same length. Considering a new way to define the symmetry among players, we propose an axiomatization of the Shapley value of these games. Borrowing ideas from electric networks theory, we show that our symmetry axiom and the efficiency axiom correspond to the two Kirchhoff’s laws in the circuit associated to the Hasse diagram of feasible coalitions.     

Inferior players in simple games

Power indices like those of Shapley and Shubik (1954) or Banzhaf (1965) measure the distribution of power in simple games. This paper points at a deficiency shared by all established indices: players who are inferior in the sense of having to accept (almost) no share of the spoils in return for being part of a winning coalition are assigned substantial amounts of power. A strengthened version of the dummy axiom based on a formalized notion of inferior players is a possible remedy. The axiom is illustrated first in a deterministic and then a probabilistic setting. With three axioms from the Banzhaf index, it uniquely characterizes the Strict Power Index (SPI). The SPI is shown to be a special instance of a more general family of power indices based on the inferior player axiom. Received: December 1999/Final version: June 2001     

Compensations in the Shapley value and the compensation solutions for graph games

We consider an alternative expression of the Shapley value that reveals a system of compensations: each player receives an equal share of the worth of each coalition he belongs to, and has to compensate an equal share of the worth of any coalition he does not belong to. We give a representation in terms of formation of the grand coalition according to an ordering of the players and define the corresponding compensation vector. Then, we generalize this idea to cooperative games with a communication graph in order to construct new allocation rules called the compensation solutions. Firstly, we consider cooperative games with arbitrary graphs and construct rooted spanning trees (see Demange, J Political Econ 112:754–778, 2004) instead of orderings of the players by using the classical algorithms DFS and BFS. If the graph is complete, we show that the compensation solutions associated with DFS and BFS coincide with the Shapley value and the equal surplus division respectively. Secondly, we consider cooperative games with a forest (cycle-free graph) and all its rooted spanning trees. The compensation solution is characterized by component efficiency and relative fairness. The latter axiom takes into account the relative position of a player with respect to his component in the communication graph.     

Node-Consistent Shapley Value for Games Played over Event Trees with Random Terminal Time

We consider a class of dynamic games played over an event tree, with random terminal time. We assume that the players wish to jointly optimize their payoffs throughout the whole planning horizon and adopt the Shapley value to share the joint cooperative outcome. We devise a node-consistent decomposition of the Shapley value, which means that in any node of the event tree, the players prefer to stick to cooperation and to continue implementing the Shapley value rather than switching to noncooperation. For each node and each player, we provide two payment values, one that applies if the game terminates at that node and the other if the game continues. We illustrate our results with an example of pollution control.     

Egalitarian allocation and players of certain type

In cooperative game theory the Shapley value is different from the egalitarian value, the latter of which allocates payoffs equally. The null player property and the nullifying player property assign zero payoff to each null player and each nullifying player, respectively. It is known that if the null player property for characterizing the Shapley value is replaced by the nullifying player property, then the egalitarian value is determined uniquely. We propose several properties to replace the nullifying player property to characterize the egalitarian value. Roughly speaking, the results in this note hint that equal division for players of certain types may lead to the egalitarian allocation.     

Whose deletion does not affect your payoff? The difference between the Shapley value, the egalitarian value, the solidarity value, and the Banzhaf value

This study provides a unified axiomatic characterization method of one-point solutions for cooperative games with transferable utilities. Any one-point solution that satisfies efficiency, the balanced cycle contributions property (BCC), and the axioms related to invariance under a player deletion is characterized as a corollary of our general result. BCC is a weaker requirement than the well-known balanced contributions property. Any one-point solution that is both symmetric and linear satisfies BCC. The invariance axioms necessitate that the deletion of a specific player from games does not affect the other players’ payoffs, and this deletion is different with respect to solutions. As corollaries of the above characterization result, we are able to characterize the well-known one-point solutions, the Shapley, egalitarian, and solidarity values, in a unified manner. We also studied characterizations of an inefficient one-point solution, the Banzhaf value that is a well-known alternative to the Shapley value.     

Necessary versus equal players in axiomatic studies

This note introduces three variants of existing axioms in which equal players are replaced by necessary players. We highlight that necessary players can replace equal players in many well-known axiomatic characterizations, but not in all. In addition, we provide new characterizations of the Shapley value, the class of positively weighted Shapley values, the Solidarity value and the Equal Division value. This sheds a new light on the real role of equal treatment of equals in the axiomatic literature.     

“Procedural” values for cooperative games

This paper introduces a new notion of a “procedural” value for cooperative TU games. A procedural value is determined by an underlying procedure of sharing marginal contributions to coalitions formed by players joining in random order. We consider procedures under which players can only share their marginal contributions with their predecessors in the ordering, and study the set of all resulting values. The most prominent procedural value is, of course, the Shapley value obtaining under the simplest procedure of every player just retaining his entire marginal contribution. But different sharing rules lead to other interesting values, including the “egalitarian solution” and the Nowak and Radzik “solidarity value”. All procedural values are efficient, symmetric and linear. Moreover, it is shown that these properties together with two very natural monotonicity postulates characterize the class of procedural values. Some possible modifications and generalizations are also discussed. In particular, it is shown that dropping one of monotonicity axioms is equivalent to allowing for sharing marginal contributions with both predecessors and successors in the ordering.     

Games with a permission structure - A survey on generalizations and applications

In the field of cooperative games with restricted cooperation, various restrictions on coalition formation are studied. The most studied restrictions are those that arise from restricted communication and hierarchies. This survey discusses several models of hierarchy restrictions and their relation with communication restrictions. In the literature, there are results on game properties, Harsanyi dividends, core stability, and various solutions that generalize existing solutions for TU-games. In this survey, we mainly focus on axiomatizations of the Shapley value in different models of games with a hierarchically structured player set, and their applications. Not only do these axiomatizations provide insight in the Shapley value for these models, but also by considering the types of axioms that characterize the Shapley value, we learn more about different network structures. A central model of games with hierarchies is that of games with a permission structure where players in a cooperative transferable utility game are part of a permission structure in the sense that there are players that need permission from other players before they are allowed to cooperate. This permission structure is represented by a directed graph. Generalizations of this model are, for example, games on antimatroids, and games with a local permission structure. Besides discussing these generalizations, we briefly discuss some applications, in particular auction games and hierarchically structured firms.