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.     

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.     

Games with a local permission structure: separation of authority and value generation

It is known that peer group games are a special class of games with a permission structure. However, peer group games are also a special class of (weighted) digraph games. To be specific, they are digraph games in which the digraph is the transitive closure of a rooted tree. In this paper we first argue that some known results on solutions for peer group games hold more general for digraph games. Second, we generalize both digraph games as well as games with a permission structure into a model called games with a local permission structure, where every player needs permission from its predecessors only to generate worth, but does not need its predecessors to give permission to its own successors. We introduce and axiomatize a Shapley value-type solution for these games, generalizing the conjunctive permission value for games with a permission structure and the $\beta $ -measure for weighted digraphs.     

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.     

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.

     

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.     

Hyperplane games,prize games and NTU values

The Shapley value is a well-known solution concept for TU games. The Maschler–Owen value and the NTU Shapley value are two well-known extensions of the Shapley value to NTU games. A hyperplane game is an NTU game in which the feasible set for each coalition is a hyperplane. On the domain of monotonic hyperplane games, the Maschler–Owen value is axiomatized (Hart Essays in game theory. Springer, 1994). Although the domain of hyperplane game is a very interesting class of games to study, unfortunately, on this domain, the NTU Shapley value is not well-defined, namely, it assigns an empty set to some hyperplane games. A prize game (Hart Essays in game theory. Springer, 1994) is an NTU game that can be obtained by “truncating” a hyperplane game. As such, a prize game describes essentially the same situation as the corresponding hyperplane game. It turns out that, on the domain of monotonic prize games, the NTU Shapley value is well-defined. Thus, one can define a value which is well-defined on the domain of monotonic hyperplane games as follows: given a monotonic hyperplane game, first, transform it into a prize game, and then apply the NTU Shapley value to it. We refer to the resulting value as the “generalized Shapley value” and compare the axiomatic properties of it with those of the Maschler–Owen value on the union of the class of monotonic hyperplane games and that of monotonic prize games. We also provide axiomatizations of the Maschler–Owen value and the generalized Shapley value on that domain.

     

Mechanism robustness in multilateral bargaining

This paper discusses the relationship between coalitional stability and the robustness of bargaining outcomes to the bargaining procedure. We consider a class of bargaining procedures described by extensive form games, where payoff opportunities are given by a characteristic function (cooperative) game. The extensive form games differ on the probability distribution assigned to chance moves which determine the order in which players take actions. One way to define mechanism robustness is in terms of the property of no first mover advantage. An equilibrium is mechanism robust if for each member the expected payoff before and after being called to propose is the same. Alternatively one can define mechanism robustness as a property of equilibrium outcomes. An outcome is said to be mechanism robust if it is supported by some equilibrium in all the extensive form games (mechanisms) within our class. We show that both definitions of mechanism robustness provide an interesting characterization of the core of the underlying cooperative game.     

On Hobbes’s state of nature and game theory

Hobbes’s state of nature is often analyzed in two-person two-action non-cooperative games. By definition, this literature only focuses on duels. Yet, if we consider general games, i.e., with more than two agents, analyzing Hobbes’s state of nature in terms of duel is not completely satisfactory, since it is a very specific interpretation of the war of all against all. Therefore, we propose a definition of the state of nature for games with an arbitrary number of players. We show that this definition coincides with the strategy profile considered as the state of nature in two-person games. Furthermore, we study what we call rational states of nature (that is, strategy profiles which are both states of nature and Nash equilibria). We show that in rational states of nature, the utility level of any agent is equal to his maximin payoff. We also show that rational states of nature always exist in inessential games. Finally, we prove the existence of states of nature in a class of (not necessarily inessential) symmetric games.     

Joint Beliefs in Conflictual Coordination Games

The traditional solution concept for noncooperative game theory is the Nash equilibrium, which contains an implicit assumption that players probability distributions satisfy t probabilistic independence. However, in games with more than two players, relaxing this assumption results in a more general equilibrium concept based on joint beliefs (Vanderschraaf, 1995). This article explores the implications of this joint-beliefs equilibrium concept for two kinds of conflictual coordination games: crisis bargaining and public goods provision. We find that, using updating consistent with Bayes rule, players beliefs converge to equilibria in joint beliefs which do not satisfy probabilistic independence. In addition, joint beliefs greatly expand the set of mixed equilibria. On the face of it, allowing for joint beliefs might be expected to increase the prospects for coordination. However, we show that if players use joint beliefs, which may be more likely as the number of players increases, then the prospects for coordination in these games declines vis-à-vis independent beliefs.     

Digraph Competitions and Cooperative Games

Digraph games are cooperative TU-games associated to domination structures which can be modeled by directed graphs. Examples come from sports competitions or from simple majority win digraphs corresponding to preference profiles in social choice theory. The Shapley value, core, marginal vectors and selectope vectors of digraph games are characterized in terms of so-called simple score vectors. A general characterization of the class of (almost positive) TU-games where each selectope vector is a marginal vector is provided in terms of game semi-circuits. Finally, applications to the ranking of teams in sports competitions and of alternatives in social choice theory 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.

---

     

Staying power in sequential games

Staying power is the ability of a player to hold off choosing a strategy in a two-person game until the other player has selected his, after which the players are assumed to be able to move and countermove sequentially to ensure their best possible outcomes before the process cycles back to the initial outcome and then repeats itself (rational termination). These rules of sequential play induce a determinate, Paretosuperior outcome in all two-person, finite, sequential games in which the preferences of the players are strict.In 57 of the 78 distinct 2 × 2 ordinal games (73 percent), it makes no difference who the (second-moving) player with staying power is, but in the other 21 games the outcome is power-dependent. In all but one of these games, staying power benefits the player who possesses it.If no player has staying power, the outcomes that result from sequential play and rational termination are called terminal; they coincide with staying power outcomes if they are Pareto-superior. Normative implications of the analysis for rationally justifying cooperation in such games as Prisoners' Dilemma and Chicken, and implementing Pareto-superior outcomes generally, are also discussed.We are grateful to D. Marc Kilgour for very valuable comments on an earlier version of this paper, causing us to rethink and redefine staying power. The earlier version was presented at the Seventeenth North American Conference, Peace Science Society (International), University of Pennsylvania, November 9–11, 1981.     

Focal points in pure coordination games: An experimental investigation

This paper reports an experimental investigation of the hypothesis that in coordination games, players draw on shared concepts of salience to identify focal points on which they can coordinate. The experiment involves games in which equilibria can be distinguished from one another only in terms of the way strategies are labelled. The games are designed to test a number of specific hypotheses about the determinants of salience. These hypotheses are generally confirmed by the results of the experiment.     

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.     

Comparative accuracy of value solutions in non-sidepayment games with empty core

This article reports a test of the predictive accuracy of solution concepts in cooperative non-sidepayment n-person games with empty core. Six solutions were tested. Three of these were value solutions (i.e., -transfer value, -transfer nucleolus, and -transfer disruption value) and three were equilibrium solutions (deterrence set, stable set, and imputation set). The test was based on a laboratory experiment utilizing 5-person, 2-choice normal form games with empty core; other related data sets were also analyzed. Goodness-of-fit results based on discrepancy scores show that the three value solutions are about equally accurate in predicting outcomes, and that all three are substantially more accurate than the other solutions tested.     

On the predictive efficiency of the core solution in side-payment games

This paper reports the first cross-study competitive test of thecore solution in side-payment games where the core is nonempty and nonunique (i.e., larger than a single point). The core was tested against five alternative theories including the Shapley value, the disruption nucleolus, the nucleolus, the 2-center, and the equality solution. A generalized Euclidean distance metric which indexes the average distance between an observed payoff vector and the entire set of predicted payoff vectors (Bonacich, 1979) was used as the measure of goodness-of-fit. Analysis of data assembled from six previously reported studies (encompassing a total of 1,464 observations over 56 3-person and 4-person side-payment games) showed the core to predict less accurately than the Shapley value, disruption nucleolus, and nucleolus solutions (p < 0.01). These findings are consistent with previous empirical results that show the core to have a low level of predictive accuracy in side-payment games.This research was supported by grants SOC-7726932 and SES-8015528 from the National Science Foundation. Data analysis was performed at the Madison Academic Computing Center.     

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.     

Punishing greediness in divide-the-dollar games

Brams and Taylor 1994 presented a version of the divide-the-dollar game (DD), which they call DD1. DD1 suffers from the following drawback: when each player demands approximately the entire dollar, then if the least greedy player is unique, then this player obtains approximately the entire dollar even if he is only slightly less greedy than the other players. I introduce a parametrized family of 2-person DD games, whose “endpoints” (the games that correspond to the extreme points of the parameter space) are (1) a variant of DD1, and (2) a game that completely overcomes the greediness-related problem. I also study an n-person generalization of this family. Finally, I show that the modeling choice between discrete and continuous bids may have far-reaching implications in DD games.     

Five legitimate definitions of correlated equilibrium in games with incomplete information

Aumann's (1987) theorem shows that correlated equilibrium is an expression of Bayesian rationality. We extend this result to games with incomplete information.First, we rely on Harsanyi's (1967) model and represent the underlying multiperson decision problem as a fixed game with imperfect information. We survey four definitions of correlated equilibrium which have appeared in the literature. We show that these definitions are not equivalent to each other. We prove that one of them fits Aumann's framework; the agents normal form correlated equilibrium is an expression of Bayesian rationality in games with incomplete information.We also follow a universal Bayesian approach based on Mertens and Zamir's (1985) construction of the universal beliefs space. Hierarchies of beliefs over independent variables (states of nature) and dependent variables (actions) are then constructed simultaneously. We establish that the universal set of Bayesian solutions satisfies another extension of Aumann's theorem.We get the following corollary: once the types of the players are not fixed by the model, the various definitions of correlated equilibrium previously considered are equivalent.