Nash-solvable two-person symmetric cycle game forms

A two-person positional game form g (with perfect information and without moves of chance) is modeled by a finite directed graph (digraph) whose vertices and arcs are interpreted as positions and moves, respectively. All simple directed cycles of this digraph together with its terminal positions form the set A of the outcomes. Each non-terminal position j is controlled by one of two players i∈I={1,2}. A strategy x_i of a player i∈I involves selecting a move (j,j^′) in each position j controlled by i. We restrict both players to their pure positional strategies; in other words, a move (j,j^′) in a position j is deterministic (not random) and it can depend only on j (not on preceding positions or moves or on their numbers). For every pair of strategies (x₁,x₂), the selected moves uniquely define a play, that is, a directed path form a given initial position j₀ to an outcome (a directed cycle or terminal vertex). This outcome a∈A is the result of the game corresponding to the chosen strategies, a=a(x₁,x₂). Furthermore, each player i∈I={1,2} has a real-valued utility function u_i over A. Standardly, a game form g is called Nash-solvable if for every u=(u₁,u₂) the obtained game (g,u) has a Nash equilibrium (in pure positional strategies).A digraph (and the corresponding game form) is called symmetric if (j,j^′) is its arc whenever (j^′,j) is. In this paper we obtain necessary and sufficient conditions for Nash-solvability of symmetric cycle two-person game forms and show that these conditions can be verified in linear time in the size of the digraph.     

Infinite horizon noncooperative differential games with nonsmooth costs

For a noncooperative differential game, the value functions of the various players satisfy a system of Hamilton-Jacobi equations. In the present paper, we study a class of infinite-horizon scalar games with either piecewise linear or piecewise smooth costs, exponentially discounted in time. By the analysis of the value functions, we find that results about existence and uniqueness of admissible solutions to the HJ system, and therefore of Nash equilibrium solutions in feedback form, can be recovered as in the smooth costs case, provided the costs are globally monotone. On the other hand, we present examples of costs such that the corresponding HJ system has infinitely many admissible solutions or no admissible solutions at all, suggesting that new concepts of equilibria may be needed to study games with general nonlinear costs.     

On differential games with a feedback nash equilibrium

This note provides a lemma on differential games which possess a feedback Nash equilibrium (FNE). In particular, it shows that (i) a class of games with a degenerate FNE can be constructucted from every game which has a nondegenerate FNE and (ii) a class of games with a nondegenerate FNE can be constructed from every game which has a degenerate FNE.The author would like to thank an anonymous referee for invaluable comments and suggestions.     

Strong stability of Nash equilibria in load balancing games

We study strong stability of Nash equilibria in load balancing games of m(m 2)identical servers,in which every job chooses one of the m servers and each job wishes to minimize its cost,given by the workload of the server it chooses.A Nash equilibrium(NE)is a strategy profile that is resilient to unilateral deviations.Finding an NE in such a game is simple.However,an NE assignment is not stable against coordinated deviations of several jobs,while a strong Nash equilibrium(SNE)is.We study how well an NE approximates an SNE.Given any job assignment in a load balancing game,the improvement ratio(IR)of a deviation of a job is defined as the ratio between the pre-and post-deviation costs.An NE is said to be aρ-approximate SNE(ρ1)if there is no coalition of jobs such that each job of the coalition will have an IR more thanρfrom coordinated deviations of the coalition.While it is already known that NEs are the same as SNEs in the 2-server load balancing game,we prove that,in the m-server load balancing game for any given m 3,any NE is a(5/4)-approximate SNE,which together with the lower bound already established in the literature yields a tight approximation bound.This closes the final gap in the literature on the study of approximation of general NEs to SNEs in load balancing games.To establish our upper bound,we make a novel use of a graph-theoretic tool.     

Constrained cost-coupled stochastic games with independent state processes

We study non-cooperative constrained stochastic games in which each player controls its own Markov chain based on its own state and actions. Interactions between players occur through their costs and constraints which depend on the state and actions of all players. We provide an example from wireless communications.     

General sum games with joint chance constraints

We consider an $n$-player non-cooperative game with continuous strategy sets. The strategy set of each player contains a set of stochastic linear constraints. We model the stochastic linear constraints of each player as a joint chance constraint. We assume that the row vectors of a matrix defining the stochastic constraints of each player are independent and each row vector follows a multivariate normal distribution. Under certain conditions, we show the existence of a Nash equilibrium for this game.     

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     

Congestion games revisited

Strategic games are considered where the players derive their utilities from participation in certain “processes”. Two subclasses consisting exclusively of potential games are singled out. In the first, players choose where to participate, but there is a unique way of participation, the same for all players. In the second, the participation structure is fixed, but each player may have an arbitrary set of strategies. In both cases, the players sum up the intermediate utilities; thus the first class essentially coincides with that of congestion games. The necessity of additivity in each case is proven. Financial support from Presidential Grants for the State Support of the Leading Scientific Schools (NSh-1843.2003.01 and NSh-5379.2006.1), the Russian Foundation for Basic Research (grant 05-01-00942), the Spanish Ministry of Education (project SEJ2004-00968), and the Lady Davis Foundation (a fellowship at the Technion, Haifa) is acknowledged. I thank Francisco Marhuenda and Dov Monderer, respectively, for procuring the last two grants. My deepest gratitude and apology are due to an anonymous referee, who carefully read two versions of the paper, suggested several improvements, and uncovered several errors, including a wrong formulation of Theorem 1. Finally, I apologize to Mikhail Gorelov, who had warned me that something was wrong with the theorem (unfortunately, I failed to pay proper attention).     

A procedure for finding Nash equilibria in bi-matrix games

In this paper we consider the computation of Nash equilibria for noncooperative bi-matrix games. The standard method for finding a Nash equilibrium in such a game is the Lemke-Howson method. That method operates by solving a related linear complementarity problem (LCP). However, the method may fail to reach certain equilibria because it can only start from a limited number of strategy vectors. The method we propose here finds an equilibrium by solving a related stationary point problem (SPP). Contrary to the Lemke-Howson method it can start from almost any strategy vector. Besides, the path of vectors along which the equilibrium is reached has an appealing game-theoretic interpretation. An important feature of the algorithm is that it finds a perfect equilibrium when at the start all actions are played with positive probability. Furthermore, we can in principle find all Nash equilibria by repeated application of the algorithm starting from different strategy vectors.This author is financially supported by the Co-operation Centre Tilburg and Eindhoven Universities, The Netherlands.     

Extra-proximal methods for solving two-person nonzero-sum games

We consider two-person nonzero-sum game, both in the classical form and in the form of a game with coupled variables. An extra-proximal approach for finding the game’s solutions is suggested and justified. We provide our algorithm with an analysis of its convergence.      

On Chooser-Picker positional games

Two new versions of the so-called Maker-Breaker Positional Games are defined by József Beck. In these variants Picker takes unselected pair of elements and Chooser keeps one of these elements and gives back the other to Picker. In the Picker-Chooser version Picker is Maker and Chooser is Breaker, while the roles are swapped in the Chooser-Picker version. It seems that both the Picker-Chooser and Chooser-Picker versions are not worse for Picker than the original Maker-Breaker versions. Here we give winning conditions for Picker in some Chooser-Picker games that extend the results of Beck.     

On a game in manufacturing

We analyse a non-zero sum two-person game introduced by Teraoka and Yamada to model the strategic aspects of production development in manufacturing. In particular we investigate how sensitive their solution concept (Nash equilibrium) is to small variations in their assumptions. It is proved that a Nash equilibrium is unique if it exists and that a Nash equilibrium exists when the capital costs of the players are zero or when the players are equal in every respect. However, when the capital costs differ, in general a Nash equilibrium exists only when the players' capital costs are high compared to their profit rates.     

Minimal and locally minimal games and game forms

By Shapley’s (1964) theorem, a matrix game has a saddle point whenever each of its 2×2 subgames has one. In other words, all minimal saddle point free (SP-free) matrices are of size 2×2. We strengthen this result and show that all locally minimal SP-free matrices also are of size 2×2. In other words, if A is a SP-free matrix in which a saddle point appears after deleting an arbitrary row or column then A is of size 2×2. Furthermore, we generalize this result and characterize the locally minimal Nash equilibrium free (NE-free) bimatrix games.Let us recall that a two-person game form is Nash-solvable if and only if it is tight [V. Gurvich, Solution of positional games in pure strategies, USSR Comput. Math. and Math. Phys. 15 (2) (1975) 74-87]. We show that all (locally) minimal non-tight game forms are of size 2×2. In contrast, it seems difficult to characterize the locally minimal tight game forms (while all minimal ones are just trivial); we only obtain some necessary and some sufficient conditions. We also recall an example from cooperative game theory: a maximal stable effectivity function that is not self-dual and not convex.     

A solution for noncooperative games

In this paper, we study solutions of strict noncooperative games that are played just once. The players are not allowed to communicate with each other. The main ingredient of our theory is the concept of rationalizing a set of strategies for each player of a game. We state an axiom based on this concept that every solution of a noncooperative game is required to satisfy. Strong Nash solvability is shown to be a sufficient condition for the rationalizing set to exist, but it is not necessary. Also, Nash solvability is neither necessary nor sufficient for the existence of the rationalizing set of a game. For a game with no solution (in our sense), a player is assumed to recourse to a standard of behavior. Some standards of behavior are examined and discussed.This work was sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and by the National Science Foundation under Grant No. MCS-75-17385-A01. The author is grateful to J. C. Harsanyi for his comments and to S. M. Robinson for suggesting the problem.     

Nonzero-sum semi-Markov games with the expected average payoffs

Nonzero-sum ergodic semi-Markov games with Borel state spaces are studied. An equilibrium theorem is proved in the class of correlated stationary strategies using public randomization. Under some additivity assumption concerning the transition probabilities stationary Nash equilibria are also shown to exist.Received: October 2004 / Revised: January 2005     

Stay-in-a-set games

There exists a Nash equilibrium (ε-Nash equilibrium) for every n-person stochastic game with a finite (countable) state space and finite action sets for the players if the payoff to each player i is one when the process of states remains in a given set of states G _i and is zero otherwise. Received: December 2000     

On coordination games with quantum correlations

A necessary condition is derived that helps to determine whether an entangled quantum system can improve coordination in a game with incomplete information. The author would like to express his gratitude to Diana Bloom for her help with editing this paper.     

Finding a Nash equilibrium in noncooperativeN-person games by solving a sequence of linear stationary point problems

In this paper we present an algorithm for finding a Nash equilibrium in a noncooperative normal formN-person game. More generally, the algorithm can be applied for solving a nonlinear stationary point problem on a simplotope, being the Cartesian product of several simplices. The algorithm solves the problem by solving a sequence of linear stationary point problems. Each problem in the sequence is solved in a finite number of iterations. Although the overall convergence cannot be proved, the method performs rather well. Computational results suggest that this algorithm performs at least as good as simplicial algorithms do.For the special case of a bi-matrix game (N=2), the algorithm has an appealing game-theoretic interpretation. In that case, the problem is linear and the algorithm always finds a solution. Furthermore, the equilibrium found in a bi-matrix game is perfect whenever the algorithm starts from a strategy vector at which all actions are played with positive probability.This research is part of the VF-program Co-operation and Competition, which has been approved by the Netherlands Ministery of Education and Sciences.     

Nash equilibria of Cauchy-random zero-sum and coordination matrix games

We consider zero-sum games (A,  − A) and coordination games (A,A), where A is an m-by-n matrix with entries chosen independently with respect to the Cauchy distribution. In each case, we give an exact formula for the expected number of Nash equilibria with a given support size and payoffs in a given range, and also asymptotic simplications for matrices of a fixed shape and increasing size. We carefully compare our results with recent results of McLennan and Berg on Gaussian random bimatrix games (A,B), and describe how the three situations together shed light on random bimatrix games in general.     

Stochastic differential reinsurance games with capital injections

This paper investigates a class of reinsurance game problems between two insurance companies under the framework of non-zero-sum stochastic differential games. Both insurers can purchase proportional reinsurance contracts from reinsurance markets and have the option of conducting capital injections. We assume the reinsurance premium is calculated under the generalized variance premium principle. The objective of each insurer is to maximize the expected value that synthesizes the discounted utility of his surplus relative to a reference point, the penalties caused by his own capital injection interventions, and the gains brought by capital injections of his competitor. We prove the verification theorem and derive explicit expressions of the Nash equilibrium strategy by solving the corresponding quasi-variational inequalities. Numerical examples are also conducted to illustrate our results.