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.     

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.     

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.     

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.     

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.     

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     

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.     

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 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     

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.     

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.     

Equi-well-posed games

In this paper, the notion of equi-well-posed optimization problem as studied by Dontchev and Zolezzi, (Ref. 1) is extended to noncooperative games. Some existence theorems for Berge and Nash equilibria are obtained. Under some invariance properties, the existence of Berge equilibria which are also Nash equilibria points is studied.     

Congestion games with failures

We introduce a new class of games, congestion games with failures (CGFs), which allows for resource failures in congestion games. In a CGF, players share a common set of resources (service providers), where each service provider (SP) may fail with some known probability (that may be constant or depend on the congestion on the resource). For reliability reasons, a player may choose a subset of the SPs in order to try and perform his task. The cost of a player for utilizing any SP is a function of the total number of players using this SP. A main feature of this setting is that the cost for a player for successful completion of his task is the minimum of the costs of his successful attempts. We show that although CGFs do not, in general, admit a (generalized ordinal) potential function and the finite improvement property (and thus are not isomorphic to congestion games), they always possess a pure strategy Nash equilibrium. Moreover, every best reply dynamics converges to an equilibrium in any given CGF, and the SPs’ congestion experienced in different equilibria is (almost) unique. Furthermore, we provide an efficient procedure for computing a pure strategy equilibrium in CGFs and show that every best equilibrium (one minimizing the sum of the players’ disutilities) is semi-strong. Finally, for the subclass of symmetric CGFs we give a constructive characterization of best and worst equilibria.     

Average stochastic games for continuous-time jump processes

We consider nonzero-sum games for continuous-time jump processes with unbounded transition rates under expected average payoff criterion. The state and action spaces are Borel spaces and reward rates are unbounded. We introduce an approximating sequence of stochastic game models with extended state space, for which the uniform exponential ergodicity is obtained. Moreover, we prove the existence of a stationary almost Markov Nash equilibrium by introducing auxiliary static game models. Finally, a cash flow model is employed to illustrate the results.     

Remarks on sensitive equilibria in stochastic games with additive reward and transition structure

A class of stochastic games with additive reward and transition structure is studied. For zero-sum games under some ergodicity assumptions 1-equilibria are shown to exist. They correspond to so-called sensitive optimal policies in dynamic programming. For a class of nonzero-sum stochastic games with nonatomic transitions nonrandomized Nash equilibrium points with respect to the average payoff criterion are also obtained. Included examples show that the results of this paper can not be extented to more general payoff or transition structure.     

Strong equilibria in claim games corresponding to convex games

This paper deals with a specific aspect of the problem of coalition formation in a situation described by a TU-game. First, we define a very simple normal form game which models the process of coalition formation. To define the payoff functions of the players we use an allocation rule for TU-games. The main objective of this paper is ascertain what conditions of the allocation rule lead to the grand coalition being a strong equilibrium of the normal form game, when the original TU-game is convex. Received January 1996/Revised version December 1996/Final version May 1997     

无限阶段网络博弈中合作解的策略稳定性

合作博弈的经典合作解不满足时间一致性, 并缺乏策略稳定性. 本文研究无限阶段网络博弈合作解的策略稳定性理论. 首先建立时间一致的分配补偿程序实现合作解的动态分配, 然后建立针对联盟的惩罚策略, 给出合作解能够被强Nash均衡策略支撑的充分性条件, 最后证明了博弈中的惩罚策略局势是强Nash均衡, 从而保证了合作解的策略稳定性. 作为应用, 考察了重复囚徒困境网络博弈中Shapley值的策略稳定性.     

On acyclicity of games with cycles

We study restricted improvement cycles (ri-cycles) in finite positional n-person games with perfect information modeled by directed graphs (di-graphs) that may contain directed cycles (di-cycles). We assume that all these di-cycles form one outcome c, for example, a draw. We obtain criteria of restricted improvement acyclicity (ri-acyclicity) in two cases: for n=2 and for acyclic di-graphs. We provide several examples that outline the limits of these criteria and show that, essentially, there are no other ri-acyclic cases.We also discuss connections between ri-acyclicity and some open problems related to Nash-solvability.     

微分对策中的联盟解

提出时间区间[t_0,∞)上的n人微分对策两阶段联盟解. 在第一阶段不能形成大联盟的假设是自然的,即源于这一思想. 在第一阶段以联盟作为局中人的对策中计算得到其纳什均衡,之后对每个联盟的收益按Shapley值进行分配. 一个n人微分减排模型的例子阐明了上述结果.