Indefinite terminating points and the iterated Prisoner's Dilemma

Conclusion In conclusion, I shall indicate one consequence of (3.4). The major resultof work on infinitely iterated Prisoner's Dilemma games is that there existcooperative equilibria in such games. I have suggested above that myaccount of finitely, but indefinitely, iterated Prisoner's Dilemma gamesreflects the nature of genuine iterated Prisoner's Dilemmas more accu-rately than accounts involving infinite iterations. If my suggestion iscorrect, then one consequence of (3.4) - of there being only uncooperativeequilibria in finitely, but indefinitely, iterated games - is to call intoquestion the significance of the existence of cooperative equilibria ininfinitely iterated Prisoner's Dilemma games.Thanks to Jules Coleman, Mark Isaac, John Pollock, and Gregory Karva for helpful comments on earlier versions of this paper. Some of these results were presented as part of similar papers given at the 1986 meeting of the society for Exact Philosophy and at Bowling Green University.     

Bayesian boundedly rational agents play the Finitely Repeated Prisoner's Dilemma

In this paper a model of boundedly rational decision making in the Finitely Repeated Prisoner's Dilemma is proposed in which: (1) each player is Bayesianrational; (2) this is common knowledge; (3) players are constrained by limited state spaces (their Bayesian minds) in processing (1) and (2). Under these circumstances, we show that cooperative behavior may arise as an individually optimal response, except for the latter part of the game. Indeed, such behaviorwill necessarily obtain in long enough games if belief systems satisfy a natural condition: essentially, that all events consistent with the players' analysis of the game be attributed by them positive (although arbitrarily small) subjective probability.     

Folk theorems for the observable implications of repeated games

The fact that infinitely repeated games have many different equilibrium outcomes is known as the Folk Theorem. Previous versions of the Folk Theorem have characterized only the payoffs of the game. This paper shows that over a finite portion of an infinitely repeated game, the concept of perfect equilibrium imposes virtually no restrictions on observable behavior. The Prisoner's Dilemma is presented as an example and discussed in detail.I would like to thank an anonymous referee, Sushil Bikhchandani, David Hirshleifer, David Levine, Thomas Voss, and participants in the UCLA Game Theory Seminar for helpful comments.     

The gradual decline of cooperation: Endgame effects in evolutionary game theory

The article provides an evolutionary analysis of a finitely iterated Prisoner's Dilemma. The backward induction reasoning for a breakdown of cooperation in this game is transformed to an evolutionary degradation effect. After the introduction of random variations in the strategies' population size, however, cyclical variations of cooperativeness may appear. A breakdown of cooperation is no longer inevitable. An analysis for all possible payoff relations in Prisoner's Dilemma matrices shows that only four qualitatively different dynamical flows can emerge.     

Institutions matter! Why the Herder Problem is not a Prisoner’s Dilemma

In the game theory literature, Garrett Hardin’s famous allegory of the “tragedy of the commons” has been modeled as a variant of the Prisoner’s Dilemma, labeled the Herder Problem (or, sometimes, the Commons Dilemma). This brief paper argues that important differences in the institutional structures of the standard Prisoner’s Dilemma and Herder Problem render the two games different in kind. Specifically, institutional impediments to communication and cooperation that ensure a dominant strategy of defection in the classic Prisoner’s Dilemma are absent in the Herder Problem. Their absence does not ensure that players will achieve a welfare-enhancing, cooperative solution to the Herders Problem, but does create far more opportunity for players to alter the expected payoffs through cooperative arrangements. In a properly modeled Herder Problem—along the lines of an assurance game—defection would not always be the dominant strategy. Consequently, the Herder Problem is not in the nature of a Prisoner’s Dilemma.     

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.     

A taxonomy of all ordinal 2 × 2 games

The 2 × 2 game is the simplest and most commonly employed representation of strategic conflict. The 78 strict ordinal 2 × 2 games have been used as conflict models extensively, and have been related in several different taxonomies. However, interest has recently focussed on the full set of 726 general ordinal games, in which one or both players may have equal preferences for two or more outcomes. This paper describes the development of a practical taxonomy of all 726 ordinal 2 × 2 games. The taxonomy provides for rapid identification of particular games, gives a convenient ordering, is as consistent as possible with previous work, and yet is not tied to any specific solution concepts. As well, definitions of several significant game properties are developed or extended to general ordinal games and applied in conjunction with the taxonomy.     

Nash Equilibrium with Lower Probabilities

We generalize the concept of Nash equilibrium in mixed strategies for strategic form games to allow for ambiguity in the players' expectations. In contrast to other contributions, we model ambiguity by means of so-called lower probability measures or belief functions, which makes it possible to distinguish between a player's assessment of ambiguity and his attitude towards ambiguity. We also generalize the concept of trembling hand perfect equilibrium. Finally, we demonstrate that for certain attitudes towards ambiguity it is possible to explain cooperation in the one-shot Prisoner's Dilemma in a way that is in accordance with some recent experimental findings.     

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.     

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.     

Endogenizing the order of moves in matrix games

Players often have flexibility in when they move and thus whether a game is played simultaneously or sequentially may be endogenously determined. For 2 × 2 games, we analyze this using an extended game. In a stage prior to actual play, players choose in which of two periods to move. A player moving at the first opportunity knows when his opponent will move. A player moving at the second turn learns the first mover's action. If both select the same turn, they play a simultaneous move subgame.If both players have dominant strategies in the basic game, equilibrium payoffs in the basic and extended games are identical. If only one player has a dominant strategy or if the unique equilibrium in the basic game is in mixed strategies, then the extended game equilibrium payoffs differ if and only if some pair of pure strategies Pareto dominates the basic game simultaneous play payoffs. If so, sequential play attains the Pareto dominating payoffs. The mixed strategy equilibrium occurs only when it is not Pareto dominated by some pair of pure strategies.In an alternative extended game, players cannot observe delay by opponents at the first turn. Results for 2×2 games are essentially the same as with observable delay, differing only when only one player has a dominant strategy.     

Three-valued simple games

In this paper we study three-valued simple games as a natural extension of simple games. We analyze to which extent well-known results on the core and the Shapley value for simple games can be extended to this new setting. To describe the core of a three-valued simple game we introduce (primary and secondary) vital players, in analogy to veto players for simple games. Moreover, it is seen that the transfer property of Dubey (1975) can still be used to characterize the Shapley value for three-valued simple games. We illustrate three-valued simple games and the corresponding Shapley value in a parliamentary bicameral system.     

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.     

Ellsberg games

In the standard formulation of game theory, agents use mixed strategies in the form of objective and probabilistically precise devices to conceal their actions. We introduce the larger set of probabilistically imprecise devices and study the consequences for the basic results on normal form games. While Nash equilibria remain equilibria in the extended game, there arise new Ellsberg equilibria with distinct outcomes, as we illustrate by negotiation games with three players. We characterize Ellsberg equilibria in two-person conflict and coordination games. These equilibria turn out to be related to experimental deviations from Nash equilibrium play.     

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.     

Prisoner's dilemma from a moral point of view

In a recent issue of this journal, C. L. Sheng claims to havesolved andexplained the Prisoner's Dilemma (PD) by studying it from a moral point of view - i.e., by assuming that each player feels sympathy for the other. Sheng does not fully clarify this claim, but there is textual evidence that his point is this: PD's arise only for agents who feel little or no sympathy for each other; they cannot arise in the presence of a high degree of reciprocal sympathy. A high degree of such sympathysolves the PD in that it prevents PD's from arising, and a low degree of itexplains the PD in that it provides an essential condition for the occurrence of that game. This thesis is false, as some examples show. These examples are important; they prevent us from underestimating the problem posed by the PD.     

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.     

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.     

Learning to cooperate with Pavlov an adaptive strategy for the iterated Prisoner's Dilemma with noise

Conflict of interest may be modeled, heuristically, by the iterated Prisoner's Dilemma game. Although several researchers have shown that the Tit-For-Tat strategy can encourage the evolution of cooperation, this strategy can never outscore any opponent and it does poorly against its clone in a noisy environment. Here we examine the family of Pavlovian strategies which adapts its play by positive and negative conditioning, much as many animals do. Mutual cooperation will evolve in a contest with Pavlov against a wide variety of opponents and in particular against its clone. And the strategy is quite stable in a noisy environment. Although this strategy cooperates and retaliates, as does Tit-For-Tat, it is not forgiving; Pavlov will exploit altruistic strategies until he is punished by mutual defection. Moreover, Pavlovian strategies are natural models for many real life conflict-of-interest encounters as well as human and computer simulations.     

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.