Non-cooperative games with minmax objectives

We consider noncooperative games where each player minimizes the sum of a smooth function, which depends on the player, and of a possibly nonsmooth function that is the same for all players. For this class of games we consider two approaches: one based on an augmented game that is applicable only to a minmax game and another one derived by a smoothing procedure that is applicable more broadly. In both cases, centralized and, most importantly, distributed algorithms for the computation of Nash equilibria can be derived.     

On the existence of equilibria in generalized games

This paper deals with the existence of equilibrium in generalized games (the so-called abstract economies) and Nash equilibrium in games with general assumptions. Preference correspondences, unlike the existing theorems in the literature, need not have open graphs or open lower sections, strategy spaces need not be compact and finite dimensional, the number of agents need not be countable, and preference relations need not be ordered. Thus, our results generalize many of the existence theorems on equilibria in generalized games, including those of Debreu (1952), Shafer and Sonnenschein (1975), Toussaint (1984), Kim and Richter (1986), and Yannelis (1987).I wish to thank the editor and an anonymous referee for helpful comments and suggestions.     

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.     

An existence result for farsighted stable sets of games in characteristic function form

In this paper we show that every finite-player game in characteristic function form (not necessarily with side payments) obeying an innocuous condition (that the set of individually rational pay-off vectors is bounded) possesses a farsighted von-Neumann–Morgenstern stable set.     

On the existence of efficient points

In this note we will study the existence ofefficient points of a set X with respect to a coneC by introducing the so-called quasi-C-bounded sets; relationships among C-compactness, C-boundedness and quasi-C-boundedness are studied in a systematic way, and new existence theorems are obtained which generalize some known results and which allow us to find existence conditions for vector optimization problem.     

On the existence of values for arbitration games

Two-person games in normal form are considered, where the players may use correlated strategies and where the problem arises, which Pareto optimal point in the payoff region to choose. We suppose that the players solve this problem with the aid of an arbitration function, which is continuous and profitable, and for which the inverse image of each Pareto point is a convex set. Then the existence of values and defensive ε-optimal strategies is discussed. Existence theorems are derived, using families of suitable dummy zero-sum games. The derived existence theorems contain all known existence results as special cases.     

Assignment games with stable core

We prove that the core of an assignment game (a two-sided matching game with transferable utility as introduced by Shapley and Shubik, 1972) is stable (i.e., it is the unique von Neumann-Morgenstern solution) if and only if there is a matching between the two types of players such that the corresponding entries in the underlying matrix are all row and column maximums. We identify other easily verifiable matrix properties and show their equivalence to various known sufficient conditions for core-stability. By these matrix characterizations we found that on the class of assignment games, largeness of the core, extendability and exactness of the game are all equivalent conditions, and strictly imply the stability of the core. In turn, convexity and subconvexity are equivalent, and strictly imply all aformentioned conditions. Final version: April 1, 2001     

On the probability of existence of pure equilibria in matrix games

Previous work related to Ref. 1, not known to the author, is reported.     

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.     

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     

On the existence and uniqueness of pairwise stable networks

In this paper we show how externalities between links affect the existence and uniqueness of pairwise stable (PS) networks. For this we introduce the properties ordinal convexity (concavity) and ordinal strategic complements (substitutes) of utility functions on networks. It is shown that there exists at least one PS network if the profile of utility functions is ordinal convex and satisfies the ordinal strategic complements property. On the other hand, ordinal concavity and ordinal strategic substitutes are sufficient for some uniqueness properties of PS networks. Additionally, we elaborate on the relation of the link externality properties to definitions in the literature.     

Equilibrium existence and uniqueness in network games with additive preferences

A directed network game of imperfect strategic substitutes with heterogeneous players is analyzed. We consider concave additive separable utility functions that encompass the quasi-linear ones. It is found that pure strategy Nash equilibria verify a non-linear complementarity problem. By requiring appropriate concavity in the utility functions, the existence of an equilibrium point is shown and equilibrium uniqueness is established with a P-matrix. For this reason, it appears that previous findings on network structure and sparsity hold for many more games.     

On the existence of efficient points in locally convex spaces

We study the existence of efficient points in a locally convex space ordered by a convex cone. New conditions are imposed on the ordering cone such that for a set which is closed and bounded in the usual sense or with respect to the cone, the set of efficient points is nonempty and the domination property holds.     

Bicriterion differential games with qualitative outcomes

Combat games are studied as bicriterion differential games with qualitative outcomes determined by threshold values on the criterion functions. Survival and capture strategies of the players are defined using the notion of security levels. Closest approach survival strategies (CASS) and minimum risk capture strategies (MRCS) are important strategies for the players identified as solutions to four optimization problems involving security levels. These are used, in combination with the preference orderings of the qualitative outcomes by the players, to delineate the win regions and the secured draw and mutual kill regions for the players. It is shown that the secured draw regions and the secured mutual kill regions for the two players are not necessarily the same. Simple illustrative examples are given.This paper is based partially on research supported by the Council of Scientific and Industrial Research, India, through a Research Associateship Grant to the second author.     

On the existence of good stationary strategies for nonleavable stochastic games

This paper discusses the problem regarding the existence of optimal or nearly optimal stationary strategies for a player engaged in a nonleavable stochastic game. It is known that, for these games, player I need not have an -optimal stationary strategy even when the state space of the game is finite. On the contrary, we show that uniformly -optimal stationary strategies are available to player II for nonleavable stochastic games with finite state space. Our methods will also yield sufficient conditions for the existence of optimal and -optimal stationary strategies for player II for games with countably infinite state space. With the purpose of introducing and explaining the main results of the paper, special consideration is given to a particular class of nonleavable games whose utility is equal to the indicator of a subset of the state space of the game.     

The stability of the equilibrium outcomes in the admission games induced by stable matching rules

A stable matching rule is used as the outcome function for the Admission game where colleges behave straightforwardly and the students’ strategies are given by their preferences over the colleges. We show that the college-optimal stable matching rule implements the set of stable matchings via the Nash equilibrium (NE) concept. For any other stable matching rule the strategic behavior of the students may lead to outcomes that are not stable under the true preferences. We then introduce uncertainty about the matching selected and prove that the natural solution concept is that of NE in the strong sense. A general result shows that the random stable matching rule, as well as any stable matching rule, implements the set of stable matchings via NE in the strong sense. Precise answers are given to the strategic questions raised.     

On the existence of population-monotonic solutions on the domain of quasi-convex games

On the domain of convex games, the Shapley value and the Dutta–Ray solutions are two well-known solutions that satisfy population-monotonicity. The existence of a population-monotonic solution on the domain of quasi-convex games has been an open question. In this note, we show that in general, no convex combination of the above two solutions can be extended to the domain of quasi-convex games in such a way that preserves population-monotonicity and efficiency.