Equilibrium play in matches: Binary Markov games

We study two-person extensive form games, or “matches,” in which the only possible outcomes (if the game terminates) are that one player or the other is declared the winner. The winner of the match is determined by the winning of points, in “point games.” We call these matches binary Markov games. We show that if a simple monotonicity condition is satisfied, then (a) it is a Nash equilibrium of the match for the players, at each point, to play a Nash equilibrium of the point game; (b) it is a minimax behavior strategy in the match for a player to play minimax in each point game; and (c) when the point games all have unique Nash equilibria, the only Nash equilibrium of the binary Markov game consists of minimax play at each point. An application to tennis is provided.     

Games of fixed rank: a hierarchy of bimatrix games

We propose and investigate a hierarchy of bimatrix games (A, B), whose (entry-wise) sum of the pay-off matrices of the two players is of rank k, where k is a constant. We will say the rank of such a game is k. For every fixed k, the class of rank k-games strictly generalizes the class of zero-sum games, but is a very special case of general bimatrix games. We study both the expressive power and the algorithmic behavior of these games. Specifically, we show that even for k = 1 the set of Nash equilibria of these games can consist of an arbitrarily large number of connected components. While the question of exact polynomial time algorithms to find a Nash equilibrium remains open for games of fixed rank, we present polynomial time algorithms for finding an ε-approximation.     

Intermediate Preferences and Behavioral Conformity in Large Games

Motivated by Wooders, Cartwright, and Selten (2006) , we consider games with a continuum of players and intermediate preferences. We show that any such game has a Nash equilibrium that induces a partition of the set of attributes into a bounded number of convex sets with the following property: all players with an attribute in the interior of the same element of the partition play the same action. We then use this result to show that all sufficiently large, equicontinuous games with intermediate preferences have an approximate equilibrium with the same property. Our result on behavior conformity for large finite game generalizes Theorem 3 of Wooders et al. (2006) by allowing both a wider class of preferences and a more general attribute space.     

On the Irrelevance of Risk Attitudes in Repeated Two-Outcome Games

We study equilibrium and maximin play in supergames consisting of the sequential play of a finite collection of stage games, where each stage game has two outcomes for each player. We show that for two-player supergames in which each stage game is strictly competitive, in any Nash equilibrium of the supergame, play at each stage is a Nash equilibrium of the stage game provided preferences over certain supergame outcomes satisfy a natural monotonicity condition. In particular, equilibrium play does not depend on risk attitudes. We establish an invariance result for games with more than two players when the solution concept is subgame perfection. Journal of Economic Literature Classification Numbers: C72, C9.     

N-PERSON NASH BNARGAINING WITH VARIABEL THREATS*

We consider two models of n-person bargaining problems with the endogenous determination of disagreement points. In the first model, which is a direct extension of Nash's variable threat bargaining model, the disagreement point is determined as an equilibrium threat point. In the second model, the disagreement point is given as a Nash equilibrium of the underlying noncooperative game. These models are formulated as extensive games, and axiomatizations of solutions are given for both models. It is argued that for games with more than two players, the first bargaining model does not preserve some important properties valid for two-person games, e.g., the uniqueness of equilibrium payoff vector. We also show that when the number of players is large, any equilibrium threat point becomes approximately a Nash equilibrium in the underlying noncooperative game, and vice versa. This result suggests that the difference between the two models becomes less significant when the number of players is large.     

Learning in games with unstable equilibria

We propose a new concept for the analysis of games, the TASP, which gives a precise prediction about non-equilibrium play in games whose Nash equilibria are mixed and are unstable under fictitious play-like learning. We show that, when players learn using weighted stochastic fictitious play and so place greater weight on recent experience, the time average of play often converges in these “unstable” games, even while mixed strategies and beliefs continue to cycle. This time average, the TASP, is related to the cycle identified by Shapley [L.S. Shapley, Some topics in two person games, in: M. Dresher, et al. (Eds.), Advances in Game Theory, Princeton University Press, Princeton, 1964]. The TASP can be close to or quite distinct from Nash equilibrium.     

A Risk‐Dominant Allocation: Maximizing Coalition Stability

This paper presents a rule to allocate a coalition’s worth for superadditive games with positive externalities. The allocation rule awards each member their outside payoff, plus an equal share of the surplus. The resulting allocation maximizes coalition stability. Stable coalitions are Strong Nash equilibria since no subset of members has an incentive to leave. Similarly, no subset of non‐members has an incentive to join a stable coalition if the game is concave in this region. The allocation is risk‐dominant. All stable coalitions are robust to the maximum probability of 50% that players’ deviate from their individual best‐responses. The paper compares the allocation to the Shapley value and the Nash bargaining solution, and illustrates why these traditional rules result in small coalitions when applied to issues such as international environmental agreements.     

Learning to Learn, Pattern Recognition, and Nash Equilibrium

The paper studies a large class of bounded-rationality, probabilistic learning models on strategic-form games. The main assumption is that players “recognize” cyclic patterns in the observed history of play. The main result is convergence with probability one to a fixed pattern of pure strategy Nash equilibria, in a large class of “simple games” in which the pure equilibria are nicely spread along the lattice of the game. We also prove that a necessary condition for convergence of behavior to a mixed strategy Nash equilibrium is that the players consider arbitrarily long histories when forming their predictions.Journal of Economic LiteratureClassification Numbers: C72, D83.     

Variational convergence: Approximation and existence of equilibria in discontinuous games

We introduce a notion of variational convergence for sequences of games and we show that the Nash equilibrium map is upper semi-continuous with respect to variationally converging sequences. We then show that for a game G with discontinuous payoff, some of the most important existence results of Dasgupta and Maskin, Simon, and Reny are based on constructing approximating sequences of games that variationally converge to G. In fact, this notion of convergence will help simplify these results and make their proofs more transparent. Finally, we use our notion of convergence to establish the existence of a Nash equilibrium for Bertrand-Edgeworth games with very general forms of tie-breaking and residual demand rules.     

On the impossibility of achieving no regrets in repeated games

Regret-minimizing strategies for repeated games have been receiving increasing attention in the literature. These are simple adaptive behavior rules that lead to no regrets and, if followed by all players, exhibit nice convergence properties: the average play converges to correlated equilibrium, or even to Nash equilibrium in certain classes of games. However, the no-regret property relies on a strong assumption that each player treats her opponents as unresponsive and fully ignores the opponents’ possible reactions to her actions. We show that if at least one player is slightly responsive, it is impossible to achieve no regrets, and convergence results for regret minimization with responsive opponents are unknown.     

Action-Graph Games

Representing and reasoning with games becomes difficult once they involve large numbers of actions and players, because the space requirement for utility functions can grow unmanageably. Action-Graph Games (AGGs) are a fully-expressive game representation that can compactly express utility functions with structure such as context-specific independence, anonymity, and additivity. We show that AGGs can be used to compactly represent all games that are compact when represented as graphical games, symmetric games, anonymous games, congestion games, and polymatrix games, as well as games that require exponential space under all of these existing representations. We give a polynomial-time algorithm for computing a player's expected utility under an arbitrary mixed-strategy profile, and show how to use this algorithm to achieve exponential speedups of existing methods for computing sample Nash equilibria. We present results of experiments showing that using AGGs leads to a dramatic increase in the size of games accessible to computational analysis.²     

A Theory of Gradual Coalition Formation

We study noncooperative multilateral bargaining games, based on underlying TU games, in which coalitions can renegotiate their agreements. We distinguish between models in which players continue to bargain after implementing agreements ("reversible actions") and models in which players who implement agreements must leave the game ("irreversible actions"). We show that renegotiation always results in formation of the grand coalition if actions are reversible, but that the process may otherwise end with smaller coalitions. On the other hand, we show that the grand coalition cannot form in one step if the core of the game is empty, irrespective of the reversibility of actions.     

Coalition formation in general apex games under monotonic power indices

An apex game consists of one apex player and a set of minor players. We identify two key properties of apex games and use them to introduce the class of general apex games. We derive players' preferences over winning coalitions by applying strongly monotonic power indices on such a game and all its subgames and investigate whether there are core stable coalitions in the induced hedonic coalition formation game. Besides several general results, in particular, we develop conditions on the game for the Shapley–Shubik index, the Banzhaf index, and the normalized Banzhaf index.     

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.     

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.     

Repeated games with present-biased preferences

We study infinitely repeated games with perfect monitoring, where players have β-δ preferences. We compute the continuation payoff set using recursive techniques and then characterize equilibrium payoffs. We then explore the cost of the present-time bias, producing comparative statics. Unless the minimax outcome is a Nash equilibrium of the stage game, the equilibrium payoff set is not monotonic in β or δ. Finally, we show how the equilibrium payoff set is contained in that of a repeated game with smaller discount factor.     

Equilibria in large games with continuous procedures

We study existence of equilibria in large games where players use boundedly rational procedures. The equilibria are different from Nash equilibria; the difference persists even when players use procedures for which the observations gathered in any period are used to evaluate the payoff from different actions.     

Game theory and climate diplomacy

Starting with the “New Periodic Table” (NPT) of 2 × 2 order games introduced by Robinson and Goforth (2005), we provide an exhaustive treatment of the possible game-theoretic characterizations of climate negotiations between two players (e.g., Great Powers or coalitions of states). Of the 144 distinct 2 × 2 games in which the players have strict ordinally ranked utilities, 25 are potentially relevant to climate problem. The negotiations may be characterized as a No-Conflict Game, Prisoner's Dilemma, Coordination Game, Chicken, Type Game, or Cycle, depending on the payoff matrix. Which game corresponds to the actual state of the world depends both on the severity of risks associated with climate change and the perceptions of the governments engaged in the negotiations. Nash equilibrium or Maxi-min equilibrium (or neither) may be the outcome. Achieving universal abatement of greenhouse gas emissions may require side payments or enforcement mechanisms outside the game framework, but we show how the negotiations themselves may offer opportunities to select between Nash equilibria or alter the payoff rankings and strategic choices of the players. In particular, scientific information pointing to the severity of the risks of climate change suggests characterization of the negotiations as a Coordination Game rather than a Prisoner's Dilemma.     

Better-reply dynamics and global convergence to Nash equilibrium in aggregative games

We consider n-person games with quasi-concave payoffs that depend on a player's own action and the sum of all players' actions. We show that a discrete-time, stochastic process in which players move towards better replies—the better-reply dynamics—converges globally to a Nash equilibrium if actions are either strategic substitutes or strategic complements for all players around each Nash equilibrium that is asymptotically stable under a deterministic, adjusted best-reply dynamics. We present an example of a 2-person game with a unique equilibrium where the derivatives of the best-reply functions have different signs and the better-reply dynamics does not converge.     

Adaptive Learning and Iterated Weak Dominance

This article addresses the idea that rational players should not play iteratively weakly dominated strategies by showing that when a particular type of adaptive learning process converges, then players must have learned to play strategy profiles equivalent to those that survive iterated nice weak dominance and, for certain games, equivalent to those that survive iterated weak dominance. For games satisfying the weak single crossing condition, the set of strategies that survive iterated weak dominance is small in that its bounds are pure strategy Nash equilibria. The results hold regardless of the order in which dominated strategies are eliminated.Journal of Economic LiteratureClassification Number: C72.