An axiomatization of the Banzhaf value for cooperative games on antimatroids

Cooperative games on antimatroids are cooperative games in which coalition formation is restricted by a combinatorial structure which generalizes permission structures. These games group several well-known families of games which have important applications in economics and politics. The current paper establishes axioms that determine the restricted Banzhaf value for cooperative games on antimatroids. The set of given axioms generalizes the axiomatizations given for the Banzhaf permission values. We also give an axomatization of the restricted Banzhaf value for the smaller class of poset antimatroids. Finally, we apply the above results to auction situations.     

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.     

一类具有限制联盟结构的合作对策的两阶段Shapley值

讨论一类具有限制联盟结构的合作对策,其中局中人通过优先联盟整体参与大联盟的合作,同时优先联盟内部有合取权限结构限制,利用两阶段Shapley值的分配思想并考虑到权限结构对优先联盟内合作的限制,给出了此类合作对策的解。 该解可看做具有联盟结构的合作对策的两阶段Shapley值的推广。 证明了该解满足的公理化条件,并验证了这些条件的独立性。     

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.     

Regression games

The solution of a TU cooperative game can be a distribution of the value of the grand coalition, i.e. it can be a distribution of the payoff (utility) all the players together achieve. In a regression model, the evaluation of the explanatory variables can be a distribution of the overall fit, i.e. the fit of the model every regressor variable is involved. Furthermore, we can take regression models as TU cooperative games where the explanatory (regressor) variables are the players. In this paper we introduce the class of regression games, characterize it and apply the Shapley value to evaluating the explanatory variables in regression models. In order to support our approach we consider Young’s (Int. J. Game Theory 14:65–72, 1985) axiomatization of the Shapley value, and conclude that the Shapley value is a reasonable tool to evaluate the explanatory variables of regression models.     

Values for Interior Operator Games

The aim of this paper is to study a new class of cooperative games called interior operator games. These games are additive games restricted by antimatroids. We consider several types of cooperative games as peer group games, big boss games, clan games and information market games and show that all of them are interior operator games. Next, we analyze the properties of these games and compute the Shapley, Banzhaf and Tijs values.     

The multi-core,balancedness and axiomatizations for multi-choice games

This note extends the solution concept of the core for cooperative games to multi-choice games. We propose an extension of the theorem of Bondareva (Problemy Kybernetiki 10:119–139, 1963) and Shapley (Nav Res Logist Q 14:453–460, 1967) to multi-choice games. Also, we introduce a notion of reduced games for multi-choice games and provide an axiomatization of the core on multi-choice games by means of corresponding notion of consistency and its converse.     

A polynomial time algorithm for computing the nucleolus for a class of disjunctive games with a permission structure

Recently, applications of cooperative game theory to economic allocation problems have gained popularity. In many such allocation problems there is some hierarchical ordering of the players. In this paper we consider a class of games with a permission structure describing situations in which players in a cooperative TU-game are hierarchically ordered in the sense that there are players that need permission from other players before they are allowed to cooperate. The corresponding restricted game takes account of the limited cooperation possibilities by assigning to every coalition the worth of its largest feasible subset. In this paper we provide a polynomial time algorithm for computing the nucleolus of the restricted games corresponding to a class of games with a permission structure which economic applications include auction games, dual airport games, dual polluted river games and information market games.     

Matrix analysis for associated consistency in cooperative game theory

Hamiache axiomatized the Shapley value as the unique solution verifying the inessential game property, continuity and associated consistency. Driessen extended Hamiache’s axiomatization to the enlarged class of efficient, symmetric, and linear values. In this paper, we introduce the notion of row (resp. column)-coalitional matrix in the framework of cooperative game theory. The Shapley value as well as the associated game are represented algebraically by their coalitional matrices called the Shapley standard matrix M^Sh and the associated transformation matrix M_λ, respectively. We develop a matrix approach for Hamiache’s axiomatization of the Shapley value. The associated consistency for the Shapley value is formulated as the matrix equality M^Sh = M^Sh · M_λ. The diagonalization procedure of M_λ and the inessential property for coalitional matrices are fundamental tools to prove the convergence of the sequence of repeated associated games as well as its limit game to be inessential. In addition, a similar matrix approach is applicable to study Driessen’s axiomatization of a certain class of linear values. In summary, it is illustrated that matrix analysis is a new and powerful technique for research in the field of cooperative game theory.     

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.     

Convexity properties for interior operator games

Interior operator games arose by abstracting some properties of several types of cooperative games (for instance: peer group games, big boss games, clan games and information market games). This reason allow us to focus on different problems in the same way. We introduced these games in Bilbao et al. (Ann. Oper. Res. 137:141–160, 2005) by a set system with structure of antimatroid, that determines the feasible coalitions, and a non-negative vector, that represents a payoff distribution over the players. These games, in general, are not convex games. The main goal of this paper is to study under which conditions an interior operator game verifies other convexity properties: 1-convexity, k-convexity (k≥2 ) or semiconvexity. But, we will study these properties over structures more general than antimatroids: the interior operator structures. In every case, several characterizations in terms of the gap function and the initial vector are obtained. We also find the family of interior operator structures (particularly antimatroids) where every interior operator game satisfies one of these properties.     

Weighted Shapley hierarchy levels values

A new class of values for cooperative games with level structure is introduced. We apply a multi-step proceeding to the weighted Shapley values. For characterization, two well-known axiomatizations of the weighted Shapley values are extended, the first one by efficiency and weighted balanced contributions and the second one by weighted standardness for two-player games and consistency. We get a new axiomatization of the Shapley levels value too.     

An axiomatization of the disjunctive permission value for games with a permission structure

Players that participate in acooperative game with transferable utilities are assumed to be part of apermission structure being a hierarchical organization in which there are players that need permission from other players before they can cooperate. Thus a permission structure limits the possibilities of coalition formation. Various assumptions can be made about how a permission structure affects the cooperation possibilities. In this paper we consider thedisjunctive approach in which it is assumed that each player needs permission from at least one of his predecessors before he can act. We provide an axiomatic characterization of thedisjunctive permission value being theShapley value of a modified game in which we take account of the limited cooperation possibilities.     

Aubin cores and bargaining sets for convex cooperative fuzzy games

In this paper, we deal with Aubin cores and bargaining sets in convex cooperative fuzzy games. We first give a simple and direct proof to the well-known result (proved by Branzei et al. (Fuzzy Sets Syst 139:267–281, 2003)) that for a convex cooperative fuzzy game v, its Aubin core C(v) coincides with its crisp core C ^cr (v). We then introduce the concept of bargaining sets for cooperative fuzzy games and prove that for a continuous convex cooperative fuzzy game v, its bargaining set coincides with its Aubin core, which extends a well-known result by Maschler et al. for classical cooperative games to cooperative fuzzy games. We also show that some results proved by Shapley (Int J Game Theory 1:11–26, 1971) for classical decomposable convex cooperative games can be extended to convex cooperative fuzzy games.     

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.     

Games on lattices,multichoice games and the shapley value: a new approach

Multichoice games, as well as many other recent attempts to generalize the notion of classical cooperative game, can be casted into the framework of lattices. We propose a general definition for games on lattices, together with an interpretation. Several definitions of the Shapley value of a multichoice games have already been given, among them the original one due to Hsiao and Raghavan, and the one given by Faigle and Kern. We propose a new approach together with its axiomatization, more in the spirit of the original axiomatization of Shapley, and avoiding a high computational complexity.     

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