On the existence of Nash equilibria in large games

We study the existence of Nash equilibria in games with an infinite number of players. We show that there exists a Nash equilibrium in mixed strategies in all normal form games such that pure strategy sets are compact metric spaces and utility functions are continuous. The player set can be any nonempty set.     

On the probability of existence of pure equilibria in matrix games

We examine the probability that a randomly chosen matrix game admits pure equilibria and its behavior as the number of actions of the players or the number of players increases. We show that, for zero-sum games, the probability of having pure equilibria goes to zero as the number of actions goes to infinity, but it goes to a nonzero constant for a two-player game. For many-player games, if the number of players goes to infinity, the probability of existence of pure equilibria goes to zero even if the number of actions does not go to infinity.This research was supported in part by NSF Grant CCR-92-22734.     

A non-zero-zum War of Attrition

The division of a cake by two players is modelled by means of a game of timing in which the players have a probability of learning when their opponent acts. It is shown that the game has a unique Nash equilibrium when both players are non-noisy but that there are many Nash equilibria including pure ones when at least one of the players is noisy. Explicit expressions for the strategies used in these Nash equilibria are obtained.This work was carried out while Dr. Garnaev was visiting the University of Southampton on a Postdoctoral Fellowship of The Royal Society of London.     

Distributed consensus in noncooperative inventory games

This paper deals with repeated nonsymmetric congestion games in which the players cannot observe their payoffs at each stage. Examples of applications come from sharing facilities by multiple users. We show that these games present a unique Pareto optimal Nash equilibrium that dominates all other Nash equilibria and consequently it is also the social optimum among all equilibria, as it minimizes the sum of all the players’ costs. We assume that the players adopt a best response strategy. At each stage, they construct their belief concerning others probable behavior, and then, simultaneously make a decision by optimizing their payoff based on their beliefs. Within this context, we provide a consensus protocol that allows the convergence of the players’ strategies to the Pareto optimal Nash equilibrium. The protocol allows each player to construct its belief by exchanging only some aggregate but sufficient information with a restricted number of neighbor players. Such a networked information structure has the advantages of being scalable to systems with a large number of players and of reducing each player’s data exposure to the competitors.     

Nash equilibrium in compact-continuous games with a potential

If the preferences of the players in a strategic game satisfy certain continuity conditions, then the acyclicity of individual improvements implies the existence of a (pure strategy) Nash equilibrium. Moreover, starting from any strategy profile, an arbitrary neighborhood of the set of Nash equilibria can be reached after a finite number of individual improvements.     

On existence of undominated pure strategy Nash equilibria in anonymous nonatomic games: a generalization

In this paper, we generalize the exitence result for pure strategy Nash equilibria in anonymous nonatomic games. By working directly on integrals of pure strategies, we also generalize, for the same class of games, the existence result for undominated pure strategy Nash equilibria even though, in general, the set of pure strategy Nash equilibria may fail to be weakly compact. Received August 2001     

Pure strategy Nash equilibria and the probabilistic prospects of Stackelberg players

We consider the set of all m×n bimatrix games with ordinal payoffs. We show that on the subset E of such games possessing at least one pure strategy Nash equilibrium, both players prefer the role of leader to that of follower in the corresponding Stackelberg games. This preference is in the sense of first-degree stochastic dominance by leader payoffs of follower payoffs. It follows easily that on the complement of E, the follower’s role is preferred in the same sense. Thus we see a tendency for leadership preference to obtain in the presence of multiple pure strategy Nash equilibria in the underlying game.     

On extremal pure Nash equilibria for mixed extensions of normal-form games

In this paper we derive conditions under which mixed extensions of normal-form games have least and greatest Nash equilibria in pure strategies, and either of them gives best utilities among all mixed Nash equilibria when strategy spaces are complete separable metric spaces equipped with closed partial orderings, and the values of utility functions are in separable ordered Banach spaces. The obtained results are applied to supermodular normal-form games whose strategy spaces are multidimensional.     

Non-cooperative stochastic dominance games

A non-cooperative stochastic dominance game is a non-cooperative game in which the only knowledge about the players' preferences and risk attitudes is presumed to be their preference orders on the set ofn-tuples of pure strategies. Stochastic dominance equilibria are defined in terms of mixed strategies for the players that are efficient in the stochastic dominance sense against the strategies of the other players. It is shown that the set of SD equilibria equals all Nash equilibria that can be obtained from combinations of utility functions that are consistent with the players' known preference orders. The latter part of the paper looks at antagonistic stochastic dominance games in which some combination of consistent utility functions is zero-sum over then-tuples of pure strategies.     

On the existence of almost-pure-strategy Nash equilibrium in <Emphasis Type="Italic">n</Emphasis>-person finite games

This paper gives wide characterization of n-person non-coalitional games with finite players’ strategy spaces and payoff functions having some concavity or convexity properties. The characterization is done in terms of the existence of two-point-strategy Nash equilibria, that is equilibria consisting only of mixed strategies with supports being one or two-point sets of players’ pure strategy spaces. The structure of such simple equilibria is discussed in different cases. The results obtained in the paper can be seen as a discrete counterpart of Glicksberg’s theorem and other known results about the existence of pure (or “almost pure”) Nash equilibria in continuous concave (convex) games with compact convex spaces of players’ pure strategies.     

How to Select a Solution in Generalized Nash Equilibrium Problems

We propose a new solution concept for generalized Nash equilibrium problems. This concept leads, under suitable assumptions, to unique solutions, which are generalized Nash equilibria and the result of a mathematical procedure modeling the process of finding a compromise. We first compute the favorite strategy for each player, if he could dictate the game, and use the best response on the others’ favorite strategies as starting point. Then, we perform a tracing procedure, where we solve parametrized generalized Nash equilibrium problems, in which the players reduce the weight on the best possible and increase the weight on the current strategies of the others. Finally, we define the limiting points of this tracing procedure as solutions. Under our assumptions, the new concept selects one reasonable out of typically infinitely many generalized Nash equilibria.     

Inducing cooperation by reciprocative strategy in non-zero-sum games

In this paper, we investigate the use of reciprocative strategy to induce cooperative behavior in non-zero-sum games. Reciprocative behavior is defined mathematically in the context of a two-person non-zero-sum game in which both the players have a common set of pure strategies. Conditions under which mutual cooperative behavior results when one of the players responds optimally to reciprocative behavior by the other player are described. Also, the desirability of playing the reciprocative strategy is investigated by stating conditions under which reciprocative strategy by one of the players or by both the players leading to mutual cooperative behavior is a Nash equilibrium outcome.     

Variational inequality formulation for the games with random payoffs

We consider an n-player non-cooperative game with random payoffs and continuous strategy set for each player. The random payoffs of each player are defined using a finite dimensional random vector. We formulate this problem as a chance-constrained game by defining the payoff function of each player using a chance constraint. We first consider the case where the continuous strategy set of each player does not depend on the strategies of other players. If a random vector defining the payoffs of each player follows a multivariate elliptically symmetric distribution, we show that there exists a Nash equilibrium. We characterize the set of Nash equilibria using the solution set of a variational inequality (VI) problem. Next, we consider the case where the continuous strategy set of each player is defined by a shared constraint set. In this case, we show that there exists a generalized Nash equilibrium for elliptically symmetric distributed payoffs. Under certain conditions, we characterize the set of a generalized Nash equilibria using the solution set of a VI problem. As an application, the random payoff games arising from electricity market are studied under chance-constrained game framework.     

Bounded rationality, strategy simplification, and equilibrium

It is frequently suggested that predictions made by game theory could be improved by considering computational restrictions when modeling agents. Under the supposition that players in a game may desire to balance maximization of payoff with minimization of strategy complexity, Rubinstein and co-authors studied forms of Nash equilibrium where strategies are maximally simplified in that no strategy can be further simplified without sacrificing payoff. Inspired by this line of work, we introduce a notion of equilibrium whereby strategies are also maximally simplified, but with respect to a simplification procedure that is more careful in that a player will not simplify if the simplification incents other players to deviate. We study such equilibria in two-player machine games in which players choose finite automata that succinctly represent strategies for repeated games; in this context, we present techniques for establishing that an outcome is at equilibrium and present results on the structure of equilibria.     

Nondominated Nash points: application of biobjective mixed integer programming

We study the connection between biobjective mixed integer linear programming and normal form games with two players. We first investigate computing Nash equilibria of normal form games with two players using single-objective mixed integer linear programming. Then, we define the concept of efficient (Pareto optimal) Nash equilibria. This concept is precisely equivalent to the concept of efficient solutions in multi-objective optimization, where the solutions are Nash equilibria. We prove that the set of all points in the payoff (or objective) space of a normal form game with two players corresponding to the utilities of players in an efficient Nash equilibrium, the so-called nondominated Nash points, is finite. We demonstrate that biobjective mixed integer linear programming, where the utility of each player is an objective function, can be used to compute the set of nondominated Nash points. Finally, we illustrate how the nondominated Nash points can be used to determine the disagreement point of a bargaining problem.     

A survey of static and dynamic potential games

Potential games are noncooperative games for which there exist auxiliary functions, called potentials, such that the maximizers of the potential are also Nash equilibria of the corresponding game. Some properties of Nash equilibria, such as existence or stability, can be derived from the potential, whenever it exists. We survey different classes of potential games in the static and dynamic cases, with a finite number of players, as well as in population games where a continuum of players is allowed. Likewise, theoretical concepts and applications are discussed by means of illustrative examples.     

Probabilities of Pure Nash Equilibria in Matrix Games when the Payoff Entries of One Player Are Randomly Selected

The Nash equilibrium in pure strategies represents an important solution concept in nonzero sum matrix games. Existence of Nash equilibria in games with known and with randomly selected payoff entries have been studied extensively. In many real games, however, a player may know his own payoff entries but not the payoff entries of the other player. In this paper, we consider nonzero sum matrix games where the payoff entries of one player are known, but the payoff entries of the other player are assumed to be randomly selected. We are interested in determining the probabilities of existence of pure Nash equilibria in such games. We characterize these probabilities by first determining the finite space of ordinal matrix games that corresponds to the infinite space of matrix games with random entries for only one player. We then partition this space into mutually exclusive spaces that correspond to games with no Nash equilibria and with r Nash equilibria. In order to effectively compute the sizes of these spaces, we introduce the concept of top-rated preferences minimal ordinal games. We then present a theorem which provides a mechanism for computing the number of games in each of these mutually exclusive spaces, which then can be used to determine the probabilities. Finally, we summarize the results by deriving the probabilities of existence of unique, nonunique, and no Nash equilibria, and we present an illustrative example.     

On the existence of equilibria in discontinuous games: three counterexamples

We study whether we can weaken the conditions given in Reny [4] and still obtain existence of pure strategy Nash equilibria in quasiconcave normal form games, or, at least, existence of pure strategy ɛ-equilibria for all ɛ>0. We show by examples that there are:1. quasiconcave, payoff secure games without pure strategy ɛ-equilibria for small enough ɛ>0 (and hence, without pure strategy Nash equilibria),2. quasiconcave, reciprocally upper semicontinuous games without pure strategy ɛ-equilibria for small enough ɛ>0, and3. payoff secure games whose mixed extension is not payoff secure.The last example, due to Sion and Wolfe [6], also shows that non-quasiconcave games that are payoff secure and reciprocally upper semicontinuous may fail to have mixed strategy equilibria.I wish to thank the editor, an associate editor and an anonymous referee for very helpful comments. I thank also John Huffstot for editorial assistance. Any remaining error is, of course, mine     

Jeux à champ moyen. I – Le cas stationnaire

We introduce here a general approach to model games with a large number of players. More precisely, we consider N players Nash equilibria for long term stochastic problems and establish rigorously the ‘mean field’ type equations as N goes to infinity. We also prove general uniqueness results and determine the deterministic limit. To cite this article: J.-M. Lasry, P.-L. Lions, C. R. Acad. Sci. Paris, Ser. I 343 (2006).