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.     

On equilibrium points in bimatrix games

We discuss sensitivity of equilibrium points in bimatrix games depending on small variances (perturbations) of data. Applying implicit function theorem to a linear complementarity problem which is equivalent to the bimatrix game, we investigate sensitivity of equilibrium points with respect to the perturbation of parameters in the game. Namely, we provide the calculation of equilibrium points derivatives with respect to the parameters.     

On the determinateness of semi-infinite bimatrix games

In this paper it is shown that every 2 × ∞ bimatrix game is weakly determined. For the proof of this fact we introduce ?-optimal andk-guaranteeing points for a convex set in IR ^m and a labeling technique which is typical for 2 × ∞ bimatrix games.     

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 equilibria in finite games

We are concerned with Nash equilibrium points forn-person games. It is proved that, given any real algebraic numberα, there exists a 3-person game with rational data which has a unique equilibrium point andα is the equilibrium payoff for some player. We also present a method which allows us to reduce an arbitraryn-person game to a 3-person one, so that a number of questions about generaln-person games can be reduced to consideration of the special 3-person case. Finally, a completely mixed game, where the equilibrium set is a manifold of dimension one, is constructed.     

On the set of proper equilibria of a bimatrix game

In this paper it is proved that the set of proper equilibria of a bimatrix game is the finite union of polytopes. To that purpose we split up the strategy space of each player into a finite number of equivalence classes and consider for a given >0 the set of all -proper pairs within the cartesian product of two equivalence classes. If this set is non-empty, its closure is a polytope. By considering this polytope as goes to zero, we obtain a (Myerson) set of proper equilibria. A Myerson set appears to be a polytope.     

Optimal threat strategies of bimatrix games

A bi-matrix threat game is defined as a triple (A,B,S) whereA andB arem×n payoff matrices, andS is a closed convex subset of the plane, with (a _ij,B _ij) εS for eachi,j. Given (threat) mixed strategiesx andy,Nash's model suggests that the eventual outcome will be that point (u, v) εS which maximizes the product (u ?xAy ^t) (v ?xBy ^t) subject tou ≥xAy ^t,v ≥xBy ^t. Optimality of the threat strategies is then defined in the obvious way. A constructive proof of existence of optimal threat strategies is given; in particular, it is shown that they are optimal strategies for the matrix gameA-kB, wherek is to be determined. In this paper,k is approximated by aNewton-Raphson technique. Two examples are solved in detail.     

Classification of two-person ordinal bimatrix games

The set of possible outcomes of a strongly ordinal bimatrix games is studied by imbedding each pair of possible payoffs as a point on the standard two-dimensional integral lattice. In particular, we count the number of different Pareto-optimal sets of each cardinality; we establish asymptotic bounds for the number of different convex hulls of the point sets, for the average shape of the set of points dominated by the Pareto-optimal set, and for the average shape of the convex hull of the point set. We also indicate the effect of individual rationality considerations on our results. As most of our results are asymptotic, the appendix includes a careful examination of the important case of 2×2 games.Supported by the Program in Discrete Mathematics and its Applications at Yale and NSF Grant CCR-8901484.     

Computing pure Nash and strong equilibria in bottleneck congestion games

Bottleneck congestion games properly model the properties of many real-world network routing applications. They are known to possess strong equilibria—a strengthening of Nash equilibrium to resilience against coalitional deviations. In this paper, we study the computational complexity of pure Nash and strong equilibria in these games. We provide a generic centralized algorithm to compute strong equilibria, which has polynomial running time for many interesting classes of games such as, e.g., matroid or single-commodity bottleneck congestion games. In addition, we examine the more demanding goal to reach equilibria in polynomial time using natural improvement dynamics. Using unilateral improvement dynamics in matroid games pure Nash equilibria can be reached efficiently. In contrast, computing even a single coalitional improvement move in matroid and single-commodity games is strongly NP-hard. In addition, we establish a variety of hardness results and lower bounds regarding the duration of unilateral and coalitional improvement dynamics. They continue to hold even for convergence to approximate equilibria.     

Equilibrium solutions for multiobjective bimatrix games incorporating fuzzy goals

Equilibrium solutions in terms of the degree of attainment of a fuzzy goal for games in fuzzy and multiobjective environments are examined. We introduce a fuzzy goal for a payoff in order to incorporate ambiguity of human judgments and assume that a player tries to maximize his degree of attainment of the fuzzy goal. A fuzzy goal for a payoff and the equilibrium solution with respect to the degree of attainment of a fuzzy goal are defined. Two basic methods, one by weighting coefficients and the other by a minimum component, are employed to aggregate multiple fuzzy goals. When the membership functions are linear, computational methods for the equilibrium solutions are developed. It is shown that the equilibrium solutions are equal to the optimal solutions of mathematical programming problems in both cases. The relations between the equilibrium solutions for multiobjective bimatrix games incorporating fuzzy goals and the Pareto-optimal equilibrium solutions are considered.     

Choice of solution in one-step bimatrix games

A new approach to the solution of one-step games is constructed, without using the concept of mixed strategy. The notion of a “set” solution of a bimatrix game is defined. It is shown that this solution always exists and may be found by a finite procedure. Examples are given illustrating the form of the “set” solution and the structure of the set of best responses for various levels of information availability to the players regarding the opponent’s behavior. __________ Translated from Nelineinaya Dinamika i Upravlenie, No. 4, pp. 341–356, 2004.     

Strictly perfect equilibrium points of bimatrix games

We consider the existence of strictly perfect equilibrium points for bimatrix games. We prove that an isolated and quasi-strong equilibrium point is strictly perfect. Our result shows that in a nondegenerate bimatrix game all equilibrium points are strictly perfect. Our proof is based on the labeling theory ofShapley [1974] for bimatrix games.     

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     

Constructing bimatrix games with unique equilibrium points

We construct bimatrix games with prefixed equilibrium points in the mixed extension. The uniqueness conditions are studied and we obtain a wide class of games with unique arbitrary prefixed equilibrium points.     

Uniqueness of equilibrium points in bimatrix games

Bimatrix games are constructed having a given pair (x, y) as the unique equilibrium point within the class of all mixed strategy pairs whose nonzero components are the same as (resp., among) those of (x, y). In each case, necessary and sufficient conditions on (x, y) for the existence of such a game are obtained. All games having the first property are constructed. The work extends and complements recent (separate) works ofMillham [1972],Raghavan [1970] and the author. The methods and results are valid in the context of any ordered field.