Cournot–Nash equilibria in continuum games with non-ordered preferences

In the usual framework of continuum games with externalities, we substantially generalize Cournot–Nash existence results [Balder, A unifying approach to existence of Nash equilibria, Int. J.Game Theory 24 (1995) 79–94; On the existence of Cournot–Nash equilibria in continuum games, J. Math. Econ. 32 (1999) 207–223; A unifying pair of Cournot–Nash equilibrium existence results, J. Econ. Theory 102 (2002) 437–470] to games with possibly non-ordered preferences, providing a continuum analogue of the seminal existence results by Mas-Colell [An equilibrium existence theorem without complete or transitive preferences, J. Math. Econ. 1 (1974) 237–246], Gale and Mas-Colell [An equilibrium existence theorem for a general model without ordered preferences, J. Math. Econ. 2 (1975) 9–15], Shafer and Sonnenschein [Equilibrium in abstract economies without ordered preferences, J. Math. Econ. 2 (1975) 345–348], Borglin and Keiding [Existence of equilibrium actions and of equilibrium: a note on the “new” existence theorems, J. Math. Econ. 3 (1976) 313–316] and Yannelis and Prabhakar [Existence of maximal elements and equilibria in linear topological spaces, J. Math. Econ. 12 (1983) 233–245].     

Mixed-Strategy Nash Equilibrium Based upon Expected Utility and Quadratic Utility

The notion of a mixed-strategy Nash equilibrium suffers from three inherent difficulties. First, given the equilibrium strategies of other players, there are many best replies. Second, the equilibrium is unstable. Third, comparative statics results are counterintuitive. We demonstrate that these difficulties all have their origin in von Neumann and Morgenstern′s expected utility. In contrast, players with "quadratic utility" have unique best replies and the Nash equilibrium appears to yield intuitive comparative statics results. Journal of Economic Literature Classification Number: C72.     

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.     

Simple search methods for finding a Nash equilibrium

We present two simple search methods for computing a sample Nash equilibrium in a normal-form game: one for 2-player games and one for n-player games. Both algorithms bias the search towards supports that are small and balanced, and employ a backtracking procedure to efficiently explore these supports. Making use of a new comprehensive testbed, we test these algorithms on many classes of games, and show that they perform well against the state of the art—the Lemke–Howson algorithm for 2-player games, and Simplicial Subdivision and Govindan–Wilson for n-player games.     

Weak monotonicity and Bayes–Nash incentive compatibility

An allocation rule is called Bayes–Nash incentive compatible, if there exists a payment rule, such that truthful reports of agents' types form a Bayes–Nash equilibrium in the direct revelation mechanism consisting of the allocation rule and the payment rule. This paper provides a characterization of Bayes–Nash incentive compatible allocation rules in social choice settings where agents have multi-dimensional types, quasi-linear utility functions and interdependent valuations. The characterization is derived by constructing complete directed graphs on agents' type spaces with cost of manipulation as lengths of edges. Weak monotonicity of the allocation rule corresponds to the condition that all 2-cycles in these graphs have non-negative length. For the case that type spaces are convex and the valuation for each outcome is a linear function in the agent's type, we show that weak monotonicity of the allocation rule together with an integrability condition is a necessary and sufficient condition for Bayes–Nash incentive compatibility.     

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.     

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.     

Aggregative games and best-reply potentials

This paper introduces quasi-aggregative games and establishes conditions under which such games admit a best-reply potential. This implies existence of a pure strategy Nash equilibrium without any convexity or quasi-concavity assumptions. It also implies convergence of best-reply dynamics under some additional assumptions. Most of the existing literature’s aggregation concepts are special cases of quasi-aggregative games, and many new situations are allowed for. An example is payoff functions that depend on own strategies as well as a linear combination of the mean and the variance of players’ strategies.     

Stable games and their dynamics

We study a class of population games called stable games. These games are characterized by self-defeating externalities: when agents revise their strategies, the improvements in the payoffs of strategies to which revising agents are switching are always exceeded by the improvements in the payoffs of strategies which revising agents are abandoning. We prove that the set of Nash equilibria of a stable game is globally asymptotically stable under a wide range of evolutionary dynamics. Convergence results for stable games are not as general as those for potential games: in addition to monotonicity of the dynamics, integrability of the agents' revision protocols plays a key role.     

Abreu–Matsushima Mechanisms: Experimental Evidence

Abreu–Matsushima mechanisms can be applied to a broad class of games to induce any desired outcome as the unique rationalizable outcome. We conduct experiments investigating the performance of such mechanisms in two simple coordination games. In these games one pure-strategy equilibrium is “focal”; we assess the efficacy of Abreu–Matsushima mechanisms for implementing the other pure-strategy equilibrium outcome. Abreu–Matsushima mechanisms induce some choices consistent with the desired outcome, but more choices reflect the focal outcome. Moreover, “strengthening” the mechanism has a perverse effect when the desired outcome is a Pareto-dominated risk-dominated equilibrium.Journal of Economic LiteratureClassification Number: C7.     

Combinatorial Games under Auction Play

ARichman gameis a combinatorial game in which, rather than alternating moves, the two players bid for the privilege of making the next move. The theory of such games is a hybrid between the classical theory of games (von Neumann, Morgenstern, …) and the combinatorial theory of games (Berlekamp, Conway, Guy, …). We expand upon our previous work by considering games with infinitely many positions as well as several variants including thePoorman variantin which the high bidder pays a third party (rather than the other player).Journal of Economic LiteratureClassification Number: C7.     

Generalised weakened fictitious play

A general class of adaptive processes in games is developed, which significantly generalises weakened fictitious play [Van der Genugten, B., 2000. A weakened form of fictitious play in two-person zero-sum games. Int. Game Theory Rev. 2, 307–328] and includes several interesting fictitious-play-like processes as special cases. The general model is rigorously analysed using the best response differential inclusion, and shown to converge in games with the fictitious play property. Furthermore, a new actor–critic process is introduced, in which the only information given to a player is the reward received as a result of selecting an action—a player need not even know they are playing a game. It is shown that this results in a generalised weakened fictitious play process, and can therefore be considered as a first step towards explaining how players might learn to play Nash equilibrium strategies without having any knowledge of the game, or even that they are playing a game.     

Evolutionary dynamics on infinite strategy spaces

Summary. The study of evolutionary dynamics was so far mainly restricted to finite strategy spaces. In this paper we show that this unsatisfying restriction is unnecessary. We specify a simple condition under which the continuous time replicator dynamics are well defined for the case of infinite strategy spaces. Furthermore, we provide new conditions for the stability of rest points and show that even strict equilibria may be unstable. Finally, we apply this general theory to a number of applications like the Nash demand game, the War of Attrition, linear-quadratic games, the harvest preemption game, and games with mixed strategies. Received: June 25, 1999; revised version: January 31, 2000     

Determinacy of equilibrium outcome distributions for zero sum and common utility games

We show the generic finiteness of probability distributions induced on outcomes by the Nash equilibria in two player zero sum and common interest outcome games.     

Asymptotic expected number of Nash equilibria of two-player normal form games

The formula given by McLennan [The mean number of real roots of a multihomogeneous system of polynomial equations, Amer. J. Math. 124 (2002) 49–73] is applied to the mean number of Nash equilibria of random two-player normal form games in which the two players have M and N pure strategies respectively. Holding M fixed while N→∞, the expected number of Nash equilibria is approximately . Letting M=N→∞, the expected number of Nash equilibria is , where is a constant, and almost all equilibria have each player assigning positive probability to approximately 31.5915 percent of her pure strategies.     

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.     

Melioration learning in games with constant and frequency-dependent pay-offs

The paper explores the implications of melioration learning—an empirically significant variant of reinforcement learning—for game theory. We show that in games with invariable pay-offs melioration learning converges to Nash equilibria in a way similar to the replicator dynamics. Since melioration learning is known to deviate from optimizing behavior when an action’s rewards decrease with increasing relative frequency of that action, we also investigate an example of a game with frequency-dependent pay-offs. Interactive melioration learning is then still appropriately described by the replicator dynamics, but it indeed deviates from rational choice behavior in such a game.     

EQUILIBRIA IN NON-COOPERATIVE GAMES I: PERTURBATIONS BASED REFINEMENTS OF NASH EQUILIBRIUM

The concept of Nash equilibrium is widely used to analyse non-cooperative games. However, one of the problems with that concept is that many games have multiple equilibria. Recent work has concentrated on reducing or refining the set of Nash equilibria in some games. In this paper, we survey some equilibrium concepts based on perturbations of strategies that refine the set of Nash equilibria. We discuss the pros and cons of each concept and its relationship to the others by the use of numerous examples and intuition. It is hoped that this survey will enable the economist to consider the relevance of a particular equilibrium concept to a given economic model of interest. Journal of Economic Literature Classification Number: C72.     

The supercore for normal-form games

This paper analyzes the supercore of a system derived from a normal-form game. For the case of a finite game with pure strategies, we define a sequence of games and show that the supercore coincides with the set of Nash equilibria of the last game in that sequence. This result is illustrated with the characterization of the supercore for the n-person prisoner's dilemma. With regard to the mixed extension of a normal-form game, we show that the set of Nash equilibrium profiles coincides with the supercore for games with a finite number of Nash equilibria.     

The projection dynamic and the replicator dynamic

We investigate a variety of connections between the projection dynamic and the replicator dynamic. At interior population states, the standard microfoundations for the replicator dynamic can be converted into foundations for the projection dynamic by replacing imitation of opponents with “revision driven by insecurity” and direct choice of alternative strategies. Both dynamics satisfy a condition called inflow–outflow symmetry, which causes them to select against strictly dominated strategies at interior states; still, because it is discontinuous at the boundary of the state space, the projection dynamic allows strictly dominated strategies to survive in perpetuity. The two dynamics exhibit qualitatively similar behavior in strictly stable and null stable games. Finally, the projection and replicator dynamics both can be viewed as gradient systems in potential games, the latter after an appropriate transformation of the state space.