Coalitional Interval Games for Strategic Games in Which Players Cooperate

We propose a method to associate a coalitional interval game with each strategic game. The method is based on the lower and upper values of finite two-person zero-sum games. Associating with a strategic game a coalitional interval game we avoid having to take either a pessimistic or an optimistic approach to the problem. The paper makes two contributions to the literature: It provides a theoretical foundation for the study of coalitional interval games and it also provides, studies, and characterizes a natural method of associating coalitional interval games with strategic games.      

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.

     

Hierarchies achievable in simple games

A previous work by Friedman et al. (Theory and Decision, 61:305–318, 2006) introduces the concept of a hierarchy of a simple voting game and characterizes which hierarchies, induced by the desirability relation, are achievable in linear games. In this paper, we consider the problem of determining all hierarchies, conserving the ordinal equivalence between the Shapley–Shubik and the Penrose–Banzhaf–Coleman power indices, achievable in simple games. It is proved that only four hierarchies are non-achievable in simple games. Moreover, it is also proved that all achievable hierarchies are already obtainable in the class of weakly linear games. Our results prove that given an arbitrary complete pre-ordering defined on a finite set with more than five elements, it is possible to construct a simple game such that the pre-ordering induced by the Shapley–Shubik and the Penrose–Banzhaf–Coleman power indices coincides with the given pre-ordering.     

Monotonicity of power in games with a priori unions

Power indices are commonly required to assign at least as much power to a player endowed with some given voting weight as to any player of the same game with smaller weight. This local monotonicity and a related global property however are frequently and for good reasons violated when indices take account of a priori unions amongst subsets of players (reflecting, e.g., ideological proximity). This paper introduces adaptations of the conventional monotonicity notions that are suitable for voting games with an exogenous coalition structure. A taxonomy of old and new monotonicity concepts is provided, and different coalitional versions of the Banzhaf and Shapley–Shubik power indices are compared accordingly.      

A Non-cooperative Axiomatization of the Core

We treat a class of multi-person bargaining mechanisms based on games in coalitional form. For this class of games we identify properties of non-cooperative solution concepts, which are necessary and sufficient for the equilibrium outcomes to coincide with the core of the underlying coalitional form game. We view this result as a non-cooperative axiomatization of the core. In contrast to most of the literature on multi-person bargaining we avoid a precise specification of the rules of the game. Alternatively, we impose properties of such games, which give rise to a large class of mechanisms, all of which are relevant for our axiomatization.     

Stochastic Evolution of Rules for Playing Finite Normal Form Games

The evolution of boundedly rational rules for playing normal form games is studied within stationary environments of stochastically changing games. Rules are viewed as algorithms prescribing strategies for the different normal form games that arise. It is shown that many of the “folk results” of evolutionary game theory, typically obtained with a fixed game and fixed strategies, carry over to the present environments. The results are also related to some recent experiments on rules and games.      

Strategic games with security and potential level players

This paper examines the existence of strategic solutions to finite normal form games under the assumption that strategy choices can be described as choices among lotteries where players have security- and potential level preferences over lotteries (e.g., Cohen, Theory and Decision, 33, 101–104, 1992, Gilboa, Journal of Mathematical Psychology, 32, 405–420, 1988, Jaffray, Theory and Decision, 24, 169–200, 1988). Since security- and potential level preferences require discontinuous utility representations, standard existence results for Nash equilibria in mixed strategies (Nash, Proceedings of the National Academy of Sciences, 36, 48–49, 1950a, Non-Cooperative Games, Ph.D. Dissertation, Princeton University Press, 1950b) or for equilibria in beliefs (Crawford, Journal of Economic Theory, 50, 127–154, 1990) do not apply. As a key insight this paper proves that non-existence of equilibria in beliefs, and therefore non-existence of Nash equilibria in mixed strategies, is possible in finite games with security- and potential level players. But, as this paper also shows, rationalizable strategies (Bernheim, Econometrica, 52, 1007–1028, 1984, Moulin, Mathematical Social Sciences, 7, 83–102, 1984, Pearce, Econometrica, 52, 1029–1050, 1984) exist for such games. Rationalizability rather than equilibrium in beliefs therefore appears to be a more favorable solution concept for games with security- and potential level players.      

Political influence in multi-choice institutions: cyclicity,anonymity, and transitivity

We study political influence in institutions where each member chooses a level of support for a collective goal. These individual choices determine the degree to which the goal is reached. Influence is assessed by newly defined binary relations, each of which ranks members on the basis of their relative performance at a corresponding level of participation. For institutions with three options (e.g., voting games in which each voter may vote “yes”, “abstain”, or vote “no”), we obtain three influence relations, and show that their strict components may be cyclic. This latter property describes a “paradox of power” which contrasts with the transitivity of the unique influence relation of binary voting games. Weak conditions of anonymity suffice for each of these relations to be transitive. We also obtain a necessary and sufficient condition for each of these relations to be complete. Further, we characterize institutions in which the rankings induced by these relations, and the Banzhaf–Coleman and Shapley–Shubik power indices coincide. We argue that extending the influence relations to firms would be useful in efficiently assigning workers to different units of production. Finally, we provide applications to various forms of political and economic organizations.     

Binary 2 × 2 games

The 2 × 2 game is the simplest interactive decision model that portrays concerned decision makers with genuine choices. There are two players, each of whom must choose one of two strategies, so that there are four possible outcomes. Binary 2 × 2 games are 2 × 2 games with no restrictions on the players' preference relations over the outcomes. They therefore generalize the strict ordinal 2 × 2 games and the ordinal 2 × 2 games, classes which have already been studied extensively. This paper enumerates the strategically distinct binary 2 × 2 games. It also identifies important subsets defined by the number of pure Nash equilibria and the occurrence of dominant strategies.     

Achievable Hierarchies In Voting Games

Previous work by Diffo Lambo and Moulen [Theory and Decision 53, 313–325 (2002)] and Felsenthal and Machover [The Measurement of Voting Power, Edward Elgar Publishing Limited (1998)], shows that all swap preserving measures of voting power are ordinally equivalent on any swap robust simple voting game. Swap preserving measures include the Banzhaf, the Shapley–Shubik and other commonly used measures of a priori voting power. In this paper, we completely characterize the achievable hierarchies for any such measure on a swap robust simple voting game. Each possible hierarchy can be induced by a weighted voting game and we provide a constructive proof of this result. In particular, the strict hierarchy is always achievable as long as there are at least five players.     

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.     

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.     

Ordinal equivalence of power notions in voting games

In this paper, we are concerned with the preorderings (SS) and (BC) induced in the set of players of a simple game by the Shapley–Shubik and the Banzhaf–Coleman's indices, respectively. Our main result is a generalization of Tomiyama's 1987 result on ordinal power equivalence in simple games; more precisely, we obtain a characterization of the simple games for which the (SS) and the (BC) preorderings coincide with the desirability preordering (T), a concept introduced by Isbell (1958), and recently reconsidered by Taylor (1995): this happens if and only if the game is swap robust, a concept introduced by Taylor and Zwicker (1993). Since any weighted majority game is swap robust, our result is therefore a generalization of Tomiyama's. Other results obtained in this paper say that the desirability relation keeps itself in all the veto-holder extensions of any simple game, and so does the (SS) preordering in all the veto-holder extensions of any swap robust simple game.     

A recursive core for partition function form games

We present a well-defined generalisation of the core to coalitional games with externalities, where the value of a deviation is given by an endogenous response, the solution (if nonempty: the core) of the residual game.     

Complementary relations in the theory of preference

(1) This paper uses the following binary relations: > (is preferred to); ⩽ (is not preferred to); < (is less preferred than); ~ (is indifferent to). (2) Savage used primitive ⩾, postulated to be connected and transitive onA (the set of acts), to define the others: [x ~ y ⇔ (x ⩽ y and y ⩽ x)]; [y < x ⇔ notx ⩽ y]; [x > y ⇔ y < x]. Independently of the axioms, this definition implies that ⩽ and > are complementary relations onA: [x < y ⇔ notx > y]. (3) Pratt, Raiffa and Schlaifer used primitive ⩽, postulated to be transitive onL (the set of lotteries), to define the others with a different expression for <: [x < y ⇔ (x ⩽ y and noty ⩽ x)]. Thus, ⩽ and > are not necessarily complementary onL; since ⩽ is not postulated to be connected onL, but connected ⩽ is necessary and sufficient for such complementarity. Since the restriction of ⩽ to the subsetA ofL is connected, ⩽ and > are complementary onA. (4) Fishburn used primitive < onA to define the others with different expression for ~ and ⩽: [x ~ y ⇔ (notx < y and noty < x)]; [x ⩽ y ⇔ (x < y orx ~ y)]. His version of Savage's theory then assumed that < is asymmetric and negatively transitive onA. Thus, ⩽ and > are complementary, since asymmetric < is necessary and sufficient for such complementarity. (5) This analysis provides a new proof that the same list of elementary properties of binary relations onA applies to all three theories: ⩽ is connected, transitive, weakly connected, reflexive, and negatively transitive; while both < and > are asymmetric, negatively transitive, antisymmetric, irreflexive, and transitive; but only ~ is symmetric.     

Using turn taking to achieve intertemporal cooperation and symmetry in infinitely repeated 2 × 2 games

Turn taking is observed in many field and laboratory settings captured by various widely studied 2 × 2 games. This article develops a repeated game model that allows us to systematically investigate turn-taking behavior in many 2 × 2 games, including the battle of the sexes, the game of chicken, the game of common-pool-resources assignment, and a particular version of the prisoners’ dilemma. We consider the “turn taking with independent randomizations” (TTIR) strategy that achieves three objectives: (a) helping the players reach the turn-taking path, (b) resolving the question of who takes the good turn first, and (c) deterring defection. We determine conditions under which there exists a unique TTIR strategy profile that can be supported as a subgame-perfect equilibrium. We also show that there exist conditions under which an increase in the “degree of conflict” of the stage game leads to a decrease in the expected number of periods in reaching the turn-taking path.     

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 Relative Strengths of Altruism and Fairness

Some researchers have attributed deviations from selfish behavior to fairness. Violations of fairness theories, however, are observed in experimental dictator games with transfer rates greater than 1 (a transfer of x from the dictator yields an income of tx for the beneficiary, where x < tx): the dictator’s final income is less than the beneficiary’s. We theoretically propose that dictator giving also involves altruism, further supporting our claim with empirical evidence from four separate samples of dictator game experiments. Our nonlinear specification allows the relative measurement of the independent motives in dictator behavior.     

The Evolution of Coding in Signaling Games

Signaling games with reinforcement learning have been used to model the evolution of term languages (Lewis 1969, Convention. Cambridge, MA: Harvard University Press; Skyrms 2006, “Signals” Presidential Address. Philosophy of Science Association for PSA). In this article, syntactic games, extensions of David Lewis’s original sender–receiver game, are used to illustrate how a language that exploits available syntactic structure might evolve to code for states of the world. The evolution of a language occurs in the context of available vocabulary and syntax—the role played by each component is compared in the context of simple reinforcement learning.     

Potential and ‘Power of a Collectivity to Act’<Superscript>*</Superscript>

This paper connects two notions: Hart and Mas-Colell’s ‘potential’, related to the value of coalitional games, and Coleman’s earlier notion of ‘power of a collectivity to act’, related to the easiness to make decisions by means of a voting rule. ^*This research has been supported by the Spanish Ministerio de Ciencia y Tecnología under project BEC2000-0875, and by the Universidad del País Vasco under project UPV/EHU000031.321-HA-7918/2000. The first author acknowledges financial support from the Spanish Ministerio de Ciencia y Tecnología under the Ramón y Cajal programme.