Stability by deterrence in cooperative non-sidepayment n-person games

This paper reports several experimental tests of the deterrence set, a solution concept for n-person games proposed by Laffond and Moulin (1977, 1981). This solution concept is distinctive because it specifies equilibria attained through the use of threats, where threats are conceptualized as costly not only to the target but also to the user. The laboratory tests were conducted in the context of 3- and 4-person cooperative non-sidepayment matrix games. In the first experimental test, the deterrence set was juxtaposed against the imputation set. Results indicate that the deterrence set has greater predictive accuracy than the imputation set. In a series of further tests, the deterrence set was juxtaposed against both the imputation set and the von Neumann-Morgenstern stable set solution. Results again show that the deterrence set is more accurate than the imputation set, but neither the deterrence set nor the stable set is reliably more accurate than the other. Overall, these results indicate that deterrence is a viable basis for stability in cooperative non-sidepayment games.     

Repeated Games with Bounded Entropy

We investigate the asymptotic behavior of the maxmin values of repeated two-person zero-sum games with a bound on the strategic entropy of the maximizer's strategies while the other player is unrestricted. We will show that if the bound η(n), a function of the number of repetitions n, satisfies the condition η(n)/n → γ (n → ∞), then the maxmin value Wⁿ(η(n)) converges to (cav U)(γ), the concavification of the maxmin value of the stage game in which the maximizer's actions are restricted to those with entropy at most γ. A similar result is obtained for the infinitely repeated games. Journal of Economic Literature Classification Numbers: C73, C72.     

A general structure theorem for the Nash equilibrium correspondence

I consider n-person normal form games where the strategy set of each player is a non-empty compact convex subset of an Euclidean space, and the payoff function of player i is continuous in joint strategies and continuously differentiable and concave in the player i's strategy. No further restrictions (such as multilinearity of the payoff functions or the requirement that the strategy sets be polyhedral) are imposed. I demonstrate that the graph of the Nash equilibrium correspondence on this domain is homeomorphic to the space of games. This result generalizes a well-known structure theorem in [Kohlberg, E., Mertens, J.-F., 1986. On the strategic stability of equilibria. Econometrica 54, 1003–1037]. It is supplemented by an extension analogous to the unknottedness theorems in [Demichelis S., Germano, F., 2000. Some consequences of the unknottedness of the Walras correspondence. J. Math. Econ. 34, 537–545; Demichelis S., Germano, F., 2002. On (un)knots and dynamics in games. Games Econ. Behav. 41, 46–60]: the graph of the Nash equilibrium correspondence is ambient isotopic to a trivial copy of the space of games.     

Cooperation through imitation

This paper characterizes long-run outcomes for broad classes of symmetric games, when players select actions on the basis of average historical performance. Received wisdom suggests that when agent's interests are partially opposed, behavior is excessively competitive: “keeping up with the Jones' ” lowers everyones' welfare. Here, we study the long-run consequences of imitative behavior when agents have sufficiently long memories and evaluate past actions in terms of (weighted) average payoff. Imitation robustly leads to cooperative outcomes (with highest symmetric payoffs) in the long run. Furthermore, lengthening memory reinforces this effect. This provides a rationale, for example, for collusive cartel-like behavior without collusive intent.     

Best response equivalence

Two games are best-response equivalent if they have the same best-response correspondence. We provide a characterization of when two games are best-response equivalent. The characterizations exploit a dual relationship between payoff differences and beliefs. Some “potential game” arguments [Games Econ. Behav. 14 (1996) 124] rely only on the property that potential games are best-response equivalent to identical interest games. Our results show that a large class of games are best-response equivalent to identical interest games, but are not potential games. Thus we show how some existing potential game arguments can be extended.     

A New Bargaining Set of an N-Person Game and Endogenous Coalition Formation

The two most fundamental questions in cooperative game theory are: When a game is played, what coalitions will be formed and what payoff vectors will be chosen? Few solution concepts or theories in the current literature provide satisfactory answers to both questions; answers are especially lacking for the first one. In this paper we introduce a new bargaining set, which is the first solution concept in cooperative game theory that provides answers to both fundamental questions endogenously. Journal of Economic Literature Classification Number: C71.     

Bounding the inefficiency of equilibria in nonatomic congestion games

Equilibria in noncooperative games are typically inefficient, as illustrated by the Prisoner's Dilemma. In this paper, we quantify this inefficiency by comparing the payoffs of equilibria to the payoffs of a “best possible” outcome. We study a nonatomic version of the congestion games defined by Rosenthal [Int. J. Game Theory 2 (1973) 65], and identify games in which equilibria are approximately optimal in the sense that no other outcome achieves a significantly larger total payoff to the players—games in which optimization by individuals approximately optimizes the social good, in spite of the lack of coordination between players. Our results extend previous work on traffic routing games.     

Iterated strict dominance in general games

We offer a definition of iterated elimination of strictly dominated strategies (IESDS^*) for games with (in)finite players, (non)compact strategy sets, and (dis)continuous payoff functions. IESDS^* is always a well-defined order independent procedure that can be used to solve Nash equilibrium in dominance-solvable games. We characterize IESDS^* by means of a “stability” criterion, and offer a sufficient and necessary epistemic condition for IESDS^*. We show by an example that IESDS^* may generate spurious Nash equilibria in the class of Reny's better-reply secure games. We provide sufficient/necessary conditions under which IESDS^* preserves the set of Nash equilibria.     

Infinite horizon common interest games with perfect information

We consider infinite horizon common interest games with perfect information. A game is a K-coordination game if each player can decrease other players' payoffs by at most K times his own cost of punishment. The number K represents the degree of commonality of payoffs among the players. The smaller K is, the more interest the players share. A K-coordination game tapers off if the greatest payoff variation conditional on the first t periods of an efficient history converges to 0 at a rate faster than K^−t as t→∞. We show that every subgame perfect equilibrium outcome is efficient in any tapering-off game with perfect information. Applications include asynchronously repeated games, repeated games of extensive form games, asymptotically finite horizon games, and asymptotically pure coordination games.     

Evolution and Mixed Strategies

Selten (1980, J. Theoret. Biol., 84, 93–101) showed that no mixed equilibria are evolutionarily stable when players can condition their strategies on their roles in a game. Alternatively, Harsanyi's (1973, Int. J. Game Theory, 2, 1–23) purification argument implies that all mixed equilibria are approximations of strict, and hence evolutionarily stable, equilibria of games with slightly perturbed payoffs. This paper reconciles these results: Approximations of mixed equilibria have high invasion barriers, and hence are likely to persist, when payoff perturbations are relatively important and role identification is relatively noisy. When payoff perturbations are unimportant and role identification is precise, approximations of mixed equilibria will have small invasion barriers and are unlikely to persist. Journal of Economic Literature Classification Numbers: C70, C78.     

The Core of Large Differentiable TU Games

For suitable non-atomic TU games ν, the core can be determined by computing appropriate derivatives of ν, yielding one of two stark conclusions: either core(ν) is empty or it consists of a single measure that can be expressed explicitly in terms of derivatives of ν. In this sense, core theory for a class of games may be reduced to calculus. Journal of Economic Literature Classification Number: C71.     

Evolutionary stability and lexicographic preferences

We explore the interaction between evolutionary stability and lexicographic preferences. To do so, we define a limit Nash equilibrium for a lexicographic game as the limit of Nash equilibria of nearby games with continuous preferences. Nash equilibria of lexicographic games are limit Nash equilibria, but not conversely. Modified evolutionarily stable strategies (Binmore and Samuelson, 1992. J. Econ. Theory 57, 278–305) are limit Nash equilibria. Modified evolutionary stability differs from “lexicographic evolutionarily stability” (defined by extending the common characterization of evolutionary stability to lexicographic preferences) in the order in which limits in the payoff space and the space of invasion barriers are taken.     

Strong equilibrium in cost sharing connection games

We study network games in which each player wishes to connect his source and sink, and the cost of each edge is shared among its users either equally (in Fair Connection Games—FCG's) or arbitrarily (in General Connection Games—GCG's). We study the existence and quality of strong equilibria (SE)—strategy profiles from which no coalition can improve the cost of each of its members—in these settings. We show that SE always exist in the following games: (1) Single source and sink FCG's and GCG's. (2) Single source multiple sinks FCG's and GCG's on series parallel graphs. (3) Multi source and sink FCG's on extension parallel graphs. As for the quality of the SE, in any FCG with n players, the cost of any SE is bounded by H(n) (i.e., the harmonic sum), contrasted with the Θ(n) price of anarchy. For any GCG, any SE is optimal.     

Payoff dominance and risk dominance in the observable delay game: a note

We examine whether the payoff dominant sequential-move (Stackelberg) outcome is realized when timing is endogenized. We adopt the observable delay game formulated by Hamilton and Slutsky [Games Econ Behav 2(1):29–46, 1990]. We find that if one sequential-move outcome is payoff dominant, either (i) the outcome both players prefer is the unique equilibrium; or (ii) two sequential-move outcomes are equilibria and the one both players prefer is risk dominant. In other words, no conflict between payoff dominance and risk dominance in the observable delay game exists, in contrast to other games such as (non pure) coordination games. We also find that even if one of two sequential-move outcomes is the unique equilibrium outcome in the observable delay game, it does not imply that the equilibrium outcome is payoff dominant to the other sequential-move outcome.      

Benchmarking real-valued acts

A benchmarking procedure ranks real-valued acts by the probability that they outperform a benchmark β which may itself be a random variable; that is, an act f is evaluated by means of the functional V(f)=P(fβ). Expected utility is a special case of benchmarking procedure, where the acts and the benchmark are stochastically independent. This paper provides axiomatic characterizations of preference relations that are representable as benchmarking procedures. The key axiom is the sure-thing principle. When the state space is infinite, different continuity assumptions translate into different properties of the probability P.     

Coordination and transfer

We study the ability of subjects to transfer principles between related coordination games. Subjects play a class of order statistic coordination games closely related to the well-known minimum (or weak-link) and median games (Van Huyck et al. in Am Econ Rev 80:234–248, 1990, Q J Econ 106(3):885–910, 1991). When subjects play a random sequence of games with differing order statistics, play is less sensitive to the order statistic than when a fixed order statistic is used throughout. This is consistent with the prediction of a simple learning model with transfer. If subjects play a series of similar stag hunt games, play converges to the payoff dominant equilibrium when a convention emerges, replicating the main result of Rankin et al. (Games Econ Behav 32:315–337, 2000). When these subjects subsequently play a random sequence of order statistic games, play is shifted towards the payoff dominant equilibrium relative to subjects without previous experience. The data is consistent with subjects absorbing a general principle, play of the payoff dominant equilibrium, and applying it in a new related setting.     

Pure Strategy Nash Equilibrium in a Group Formation Game with Positive Externalities

This paper identifies a domain of payoff functions inno spillovernoncooperative games withPositive externalitywhich admit a pure strategy Nash equilibrium. Since in general a Nash equilibrium may fail to exist, in order to guarantee the existence of an equilibrium, we impose two additional assumptions,AnonymityandOrder preservation. The proof of our main result is carried out by constructing, for a given gameG, a potential function Ψ over the set of strategy profiles in such a way that the maximum of Ψ yields a Nash equilibrium in pure strategies ofG.Journal of Economics LiteratureClassification Numbers: C72, D62, H73.     

A limit characterization of belief-free equilibrium payoffs in repeated games

The present paper studies repeated games with private monitoring, and characterizes the set of belief-free equilibrium payoffs in the limit as the discount factor approaches one and the noise on private information vanishes. Contrary to the conjecture by Ely et al. [J.C. Ely, J. Hörner, W. Olszewski, Belief-free equilibria in repeated games, Econometrica 73 (2005) 377-415], the equilibrium payoff set is computed by the same formula, no matter how many players there are. As an application of this result, a version of the folk theorem is established for N-player prisoner's dilemma games.     

The α-beauty contest: Choosing numbers, thinking intervals

We present a model for the α-beauty contest that explains common patterns in experimental data of one-shot and iterative games. The approach is based on two basic assumptions. First, players iteratively update their recent guesses. Second, players estimate intervals rather than exact numbers to cope with incomplete knowledge of other players' rationality. Under these assumptions we extend the cognitive hierarchy model of Camerer et al. [Camerer, C., Ho, T., Chong, J., 2003b. A cognitive hierarchy model of one-shot games. Quart. J. Econ. 119, 861–898]. The extended model is estimated on experimental data from a newspaper experiment.     

A game of timing and visibility

We consider the following abstraction of competing publications. There are n players in the game. Each player i chooses a point x_i in the interval [0,1], and a player's payoff is the distance from its point x_i to the next larger point, or to 1 if x_i is the largest. For this game, we give a complete characterization of the Nash equilibrium for the two-player game, and, more important, we give an efficient approximation algorithm to compute numerically the symmetric Nash equilibrium for the n-player game. The approximation is computed via a discrete version of the game. In both cases, we show that the (symmetric) equilibrium is unique. Our algorithmic approach to the n-player game is non-standard in that it does not involve solving a system of differential equations. We believe that our techniques can be useful in the analysis of other timing games.