A Banzhaf share function for cooperative games in coalition structure

A cooperative game with transferable utility–or simply a TU-game– describes a situation in which players can obtain certain payoffs by cooperation. A value function for these games assigns to every TU-game a distribution of payoffs over the players. Well-known solutions for TU-games are the Shapley and the Banzhaf value. An alternative type of solution is the concept of share function, which assigns to every player in a TU-game its share in the worth of the grand coalition. In this paper we consider TU-games in which the players are organized into a coalition structure being a finite partition of the set of players. The Shapley value has been generalized by Owen to TU-games in coalition structure. We redefine this value function as a share function and show that this solution satisfies the multiplication property that the share of a player in some coalition is equal to the product of the Shapley share of the coalition in a game between the coalitions and the Shapley share of the player in a game between the players within the coalition. Analogously we introduce a Banzhaf coalition structure share function. Application of these share functions to simple majority games show some appealing properties.     

Stable coalition structures in symmetric majority games: a coincidence between myopia and farsightedness

The objective of this paper is to study stable coalition structures in symmetric majority games. We assume that players deviate from a coalition structure to another to maximize their power given by the Owen power index. We introduce three myopic core concepts and one farsighted stability concept, the farsighted vNM stable set. Our main result is that the pessimistic core, the largest myopic core, coincides with some farsighted vNM stable set for any number of players. Moreover, we show that a coalition structure belongs to the pessimistic core and the farsighted vNM stable set if and only if it contains an exact majority coalition.     

Socially Structured Games

We generalize the concept of a cooperative non-transferable utility game by introducing a socially structured game. In a socially structured game every coalition of players can organize themselves according to one or more internal organizations to generate payoffs. Each admissible internal organization on a coalition yields a set of payoffs attainable by the members of this coalition. The strengths of the players within an internal organization depend on the structure of the internal organization and are represented by an exogenously given power vector. More powerful players have the power to take away payoffs of the less powerful players as long as those latter players are not able to guarantee their payoffs by forming a different internal organization within some coalition in which they have more power. We introduce the socially stable core as a solution concept that contains those payoffs that are both stable in an economic sense, i.e., belong to the core of the underlying cooperative game, and stable in a social sense, i.e., payoffs are sustained by a collection of internal organizations of coalitions for which power is distributed over all players in a balanced way. The socially stable core is a subset and therefore a refinement of the core. We show by means of examples that in many cases the socially stable core is a very small subset of the core. We will state conditions for which the socially stable core is non-empty. In order to derive this result, we formulate a new intersection theorem that generalizes the KKMS intersection theorem. We also discuss the relationship between social stability and the wellknown concept of balancedness for NTU-games, a sufficient condition for non-emptiness of the core. In particular we give an example of a socially structured game that satisfies social stability and therefore has a non-empty core, but whose induced NTU-game does not satisfy balancedness in the general sense of Billera.      

Population monotonic path schemes for simple games

A path scheme for a game is composed of a path, i.e., a sequence of coalitions that is formed during the coalition formation process and a scheme, i.e., a payoff vector for each coalition in the path. A path scheme is called population monotonic if a player’s payoff does not decrease as the path coalition grows. In this study, we focus on Shapley path schemes of simple games in which for every path coalition the Shapley value of the associated subgame provides the allocation at hand. Obviously, each Shapley path scheme of a game is population monotonic if and only if the Shapley allocation scheme of the game is population monotonic in the sense of Sprumont (Games Econ Behav 2:378–394, 1990). We prove that a simple game allows for population monotonic Shapley path schemes if and only if the game is balanced. Moreover, the Shapley path scheme of a specific path is population monotonic if and only if the first winning coalition that is formed along the path contains every minimal winning coalition. We also show that each Shapley path scheme of a simple game is population monotonic if and only if the set of veto players of the game is a winning coalition. Extensions of these results to other efficient probabilistic values are discussed.     

Game-theoretic analyses of coalition behavior

Coalitions are frequently more visible than payoffs. The theory of n-person games seeks primarily to identify stable allocations of valued resources; consequently, it gives inadequate attention to predicting which coalitions form. This paper explores a way of correcting this deficiency of game-theoretic reasoning by extending the theory of two-person cooperative games to predict both coalitions and payoffs in a three-person game of status in which each player seeks to maximize the rank of his total score. To accomplish this, we analyze the negotiations within each potential two-person coalition from the perspective of Nash's procedure for arbitrating two-person bargaining games, then assume that players expect to achieve the arbitrated outcome selected by this procedure and use these expectations to predict achieved ranks and to identify players' preferences between alternative coalition partners in order to predict the probability that each coalition forms. We test these payoff and coalition predictions with data from three laboratory studies, and compare the results with those attained in the same data by von Neumann and Morgenstern's solution of two-person cooperative games, Aumann and Maschler's bargaining set solution for cooperative n-person games, and an alternative model of coalition behavior in three-person sequential games of status.

---

     

A model of influence with an ordered set of possible actions

In the article, a yes–no model of influence is generalized to a multi-choice framework. We introduce and study the weighted influence indices of a coalition on a player in a social network where the players have an ordered set of possible actions. Each player has an inclination to choose one of the actions. Due to the mutual influence among players, the final decision of each player may be different from his original inclination. In a particular case, the decision of the player is closer to the inclination of the influencing coalition than his inclination was, i.e., the distance between the inclinations of the player and of the coalition is greater than the distance between the decision of the player and the inclination of the coalition in question. The weighted influence index which captures such a case is called the weighted positive influence index. We also consider the weighted negative influence index where the final decision of the player goes farther away from the inclination of the coalition. We consider several influence functions defined in the generalized model of influence and study their properties. The concept of a follower of a given coalition and its particular case, a perfect follower, are defined. The properties of the set of followers are analyzed.     

Perceptron versus automaton in the finitely repeated prisoner’s dilemma

We study the finitely repeated prisoner’s dilemma in which the players are restricted to choosing strategies which are implementable by a machine with a bound on its complexity. One player has to use a finite automaton while the other player has to use a finite perceptron. Some examples illustrate that the sets of strategies which are induced by these two types of machines are different and not ordered by set inclusion. Repeated game payoffs are evaluated according to the limit of means. The main result establishes that a cooperation at almost all stages of the game is an equilibrium outcome if the complexity of the machines the players may use is limited enough and if the length T of the repeated game is sufficiently large. This result persists when more than T states are allowed in the player’s automaton. We further consider a variant of the model in which the two players are restricted to choosing strategies which are implementable by perceptrons and prove that the players can cooperate at most of the stages provided that the complexity of their perceptrons is sufficiently reduced.     

On the coase theorem and coalitional stability: the principle of equal relative concession

The Coase theorem is argued to be incompatible with bargaining set stability due to a tension between the grand coalition and sub-coalitions. We provide a counter-intuitive argument to demonstrate that the Coase theorem may be in complete consonance with bargaining set stability. We establish that an uncertainty concerning the formation of sub-coalitions will explain such compatibility: each agent fears that others may `gang up' against him and this fear forces the agents to negotiate. The grand coalition emerges from the negotiations if each agent uses the principle of equal relative sacrifice to determine the actual allocation. We also establish the rational basis for the choice of the principle of equal relative concession by the negotiating agents. Hence we argue that the Coase theorem will be valid even if there are stable sub-coalitions.     

A test of the Core,Bargaining Set,Kernel and Shapley models in n-person quota games with one weak player

n-person (n – 1)-quota-games where the quotas are positive for certain n – 1 (strong) players and negative for the remaining (weak) player, are discussed. Normative solutions predicted by the Core,the Kernel, the Bargaining Set, the Competitive Bargaining Set, and by the Shapley Value are presented and exemplified.Each of twelve groups of subjects participated in a four-person and a five-person (n – 1)-quota games with one weak player. The weak player was always excluded from the ratified coalition. The division of payoffs among the strong players was more egalitarian than the Kernel solution but less egalitarian than the Shapley value. The Core and the Bargaining Sets were fully supported for the two strongest players, but less supported for the other players. Analyses of the bargaining process confirmed a dynamic interpretation of the Bargaining Set Theory.This research was performed while the author was at the University of North Carolina. The research was partially supported by a PHS Research Grant No. MH-10006 from the National Institute of Mental Health. The author thanks Professor Amnon Rapoport for helpful advice in the design of this study.     

Communication and its cost in graph-restricted games

We consider cooperative games which are modified by subordination to communication networks. Two players i and j will be able to cooperate only if they pay for the cost w _ij of their communication link (i,j). Coalitions of players are treated similarly and a new characteristic function form game is developed thus. We also examine incentive for players to cooperate in such situations as well as a related index of a player's communicative strength.     

Rawlsian Nash solutions

We investigate the conditions which guarantee the choice of Rawlsian solutions by players of unequal maximin positions bargaining under Nash rules. The conditions, viz., subsymmetry and the location of the Pareto set, relate to the structure of the utility set,S.     

Domination structures and multicriteria problems in n-person games

Multiple criteria decision problems with one decision maker have been recognized and discussed in the recent literature in optimization theory, operations research and management science. The corresponding concept with n-decision makers, namely multicriteria n-person games, has not yet been extensively explored.In this paper we first demonstrate that existing solution concepts for single criterion n-person games in both normal form and characteristic function form induce domination structures (similar to those defined and studied by Yu [39] for multicriteria single decision maker problems) in various spaces, including the payoff space, the imputation space and the coalition space. This discussion provides an understanding of some underlying assumptions of the solution concepts and provides a basis for generalizing and generating new solution concepts not yet defined. Also we illustrate that domination structures may be regarded as a measure of power held by the players.We then illustrate that a multicriteria problem can naturally arise in decision situations involving (partial) conflict among n-persons. Using our discussion of solution concepts for single criterion games as a basis, various approaches for resolving both normal form and characteristic function form multicriteria n-person games are proposed. For multicriteria games in characteristic function form, we define a multicriteria core and show that there exists a single game point whose core is equal to the multicriteria core. If we reduce a multicriteria game to a single criterion game, domination structures which are more general than classical ones must be considered, otherwise some crucial information in the game may be lost. Finally, we discuss a parametrization process which, for a given multicriteria game, associates a single criterion game to each point in a parametric space. This parametrization provides a basis for the discussion of solution concepts in multicriteria n-person games.     

Strengthening Advocacy Coalitions: Lessons for Structure,Engagement, and Effectiveness from an IPV Coalition

Social workers who are active in the area of intimate partner violence (IPV) must understand how to structure their coalitions for maximum effectiveness. The purpose of this study was to examine the communication strategies, organizational structures, and relationships between one IPV coalition and its membership to glean recommendations for the field. The authors purposively sampled ten subjects from one state, including staff from the state IPV advocacy coalition (N = 2) and staff from the state coalition's member agencies (N = 8). After completing phone interviews with the subjects, the authors utilized directed content analysis to derive themes from the data. Study findings point to different perceptions regarding access to the coalition, flow of information to and from the coalition, the shaping of the IPV movement, and coalition structure. These differences occurred between executive versus direct practice staff, and nearby versus distant member agencies. Executives and those in nearby regions were more likely to describe a reciprocal relationship between member agencies and the coalition than were direct practice staff or those working in distant agencies. Future research should address the benefits and drawbacks of coalitions cultivating centralized versus decentralized relationships with member agencies, particularly in terms of impact on member agency social service delivery.     

Axiomatization of a class of share functions for n-person games

The Shapley value is the unique value defined on the class of cooperative games in characteristic function form which satisfies certain intuitively reasonable axioms. Alternatively, the Banzhaf value is the unique value satisfying a different set of axioms. The main drawback of the latter value is that it does not satisfy the efficiency axiom, so that the sum of the values assigned to the players does not need to be equal to the worth of the grand coalition. By definition, the normalized Banzhaf value satisfies the efficiency axiom, but not the usual axiom of additivity.In this paper we generalize the axiom of additivity by introducing a positive real valued function on the class of cooperative games in characteristic function form. The so-called axiom of -additivity generalizes the classical axiom of additivity by putting the weight (v) on the value of the gamev . We show that any additive function determines a unique share function satisfying the axioms of efficient shares, null player property, symmetry and -additivity on the subclass of games on which is positive and which contains all positively scaled unanimity games. The axiom of efficient shares means that the sum of the values equals one. Hence the share function gives the shares of the players in the worth of the grand coalition. The corresponding value function is obtained by multiplying the shares with the worth of the grand coalition. By defining the function appropiately we get the share functions corresponding to the Shapley value and the Banzhaf value. So, for both values we have that the corresponding share functions belong to this class of share functions. Moreover, it shows that our approach provides an axiomatization of the normalized Banzhaf value. We also discuss some other choices of the function and the corresponding share functions. Furthermore we consider the axiomatization on the subclass of monotone simple games.     

Dynamic focal points in N-person coordination games

To understand how groups coordinate, we study infinitely repeated N-player coordination games in the context of strategic uncertainty. In a situation where players share no common language or culture, ambiguity is always present. However, finding an adequate principle for a common language is not easy: a tradeoff between simplicity and efficiency has to be made. All these points are illustrated on repeated N-player coordination games on m loci. In particular, we demonstrate how a common principle can accelerate coordination. We present very simple rules that are optimal in the space of all languages for m (number of coordination loci) from 2 to 5 and for all N, the number of players. We also show that when more memory is used in the language (strategies), players may not coordinate, whereas this is never the case when players remember only the previous period.     

Partial cooperation in strategic multi-sided decision situations

We consider a normal-form game in which there is a single exogenously given coalition of cooperating players that can write a binding agreement on pre-selected actions. The actions representing other dimensions of the strategy space remain under the sovereign, individual control of the players. We consider a standard extension of the Nash equilibrium concept denoted as a partial cooperative equilibrium as well as an equilibrium concept in which the coalition of cooperators has a leadership position. Existence results are stated and we identify conditions under which the various equilibrium concepts are equivalent. We apply this framework to existing models of multi-market oligopolies and international pollution abatement. In a multi-market oligopoly, typically, a merger paradox emerges in the partial cooperative equilibrium. The paradox vanishes if the cartel attains a leadership position. For international pollution abatement treaties, cooperation by a sufficiently large group of countries results in a Pareto improvement over the standard tragedy of the commons outcome described by the Nash equilibrium.     

Characterization of dominance relations in finite coalitional games

McGarvey (Econometrica, 21(4), 608–610, 1953) has shown that any irreflexive and anti-symmetric relation can be obtained as a relation induced by majority rule. We address the analogous issue for dominance relations of finite cooperative games with non-transferable utility (coalitional NTU games). We find any irreflexive relation over a finite set can be obtained as the dominance relation of some finite coalitional NTU game. We also show that any such dominance relation is induced by a non-cooperative game through β-effectivity. Dominance relations obtainable through α-effectivity, however, have to comply with a more restrictive condition, which we refer to as the edge-mapping property.     

Procedural and optimization implementation of the weighted ENSC value

The main purpose of this article is to introduce the weighted ENSC value for cooperative transferable utility games which takes into account players’ selfishness about the payoff allocations. Similar to Shapley’s idea of a one-by-one formation of the grand coalition [Shapley (1953)], we first provide a procedural implementation of the weighted ENSC value depending on players’ selfishness as well as their marginal contributions to the grand coalition. Second, in the spirit of the nucleolus [Schmeidler (1969)], we prove that the weighted ENSC value is obtained by lexicographically minimizing a complaint vector associated with a new complaint criterion relying on players’ selfishness.

     

Equilibrium and potential in coalitional congestion games

The model of congestion games is widely used to analyze games related to traffic and communication. A central property of these games is that they are potential games and hence posses a pure Nash equilibrium. In reality, it is often the case that some players cooperatively decide on their joint action in order to maximize the coalition’s total utility. This is modeled by Coalitional Congestion Games. Typical settings include truck drivers who work for the same shipping company, or routers that belong to the same ISP. The formation of coalitions will typically imply that the resulting coalitional congestion game will no longer posses a pure Nash equilibrium. In this paper, we provide conditions under which such games are potential games and posses a pure Nash equilibrium.     

Axiomatizations of a Class of Equal Surplus Sharing Solutions for TU-Games

A situation, in which a finite set of players can obtain certain payoffs by cooperation can be described by a cooperative game with transferable utility, or simply a TU-game. A (point-valued) solution for TU-games assigns a payoff distribution to every TU-game. In this article we discuss a class of equal surplus sharing solutions consisting of all convex combinations of the CIS-value, the ENSC-value and the equal division solution. We provide several characterizations of this class of solutions on variable and fixed player set. Specifications of several properties characterize specific solutions in this class.