Directed graphical structure,Nash equilibrium,and potential games

This paper considers the directed graphical structure of a game, called influence structure, where a directed edge from player $i$ to player $j$ indicates that player $i$ may be able to affect $j$’s payoff via his unilateral change of strategies. We give a necessary and sufficient condition for the existence of pure-strategy Nash equilibrium of games having a directed graph in terms of the structure of that graph. We also discuss the relationship between the structure of graphs and potential games.     

Interactive economic dynamics and differential games

This survey reviews the applications of differential game theory in analyzing issues in the economic literature. The needs of the economic discipline are juxtaposed with the merits of various existing types of differential games. Suggestions are also made as to areas holding great promise for future research.The authors are grateful to Prof. George Leitmann for suggestions to their final draft, which improved the clarity of certain assumptions in keeping with the literature.     

Randomized stopping games and Markov market games

We study nonzero-sum stopping games with randomized stopping strategies. The existence of Nash equilibrium and ɛ-equilibrium strategies are discussed under various assumptions on players random payoffs and utility functions dependent on the observed discrete time Markov process. Then we will present a model of a market game in which randomized stopping times are involved. The model is a mixture of a stochastic game and stopping game. Research supported by grant PBZ-KBN-016/P03/99.     

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.     

Borel stay-in-a-set games

Consider an n-person stochastic game with Borel state space S, compact metric action sets A ₁,A ₂,,A _n , and law of motion q such that the integral under q of every bounded Borel measurable function depends measurably on the initial state x and continuously on the actions (a ₁,a ₂,,a _n ) of the players. If the payoff to each player i is 1 or 0 according to whether or not the stochastic process of states stays forever in a given Borel set G _i , then there is an -equilibrium for every >0. AMS (1991) subject classification: 60G40, 91A60, 60E15, 46A55.     

Infinite horizon noncooperative differential games

For a noncooperative differential game, the value functions of the various players satisfy a system of Hamilton-Jacobi equations. In the present paper, we consider a class of infinite horizon games with nonlinear costs exponentially discounted in time. By the analysis of the value functions, we establish the existence of Nash equilibrium solutions in feedback form and provide results and counterexamples on their uniqueness and stability.     

On Nikaido-Isoda type theorems for discounted stochastic games

We present a class of countable state space stochastic games with discontinuous payoff functions satisfying some assumptions similar to the ones of Nikaido and Isoda for one-stage games. We prove that these games possess stationary equilibria. We show that after adding some concavity assumptions these equilibria are nonrandomized. Further, we present an example of input (or production) dynamic game satisfying the assumptions of our model. We give a closed-form solution for this game.     

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.     

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 taxonomy of best-reply multifunctions in 2×2×2 trimatrix games

This paper provides an overview of the various shapes the best-reply multifunctions can take in 2×2×2 trimatrix games. It is shown that, unlike in 2×2 bimatrix games, the best replies to the opponents’ pure strategies do not completely determine the structure of the Nash equilibrium set.      

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 purification of equilibrium in Bayesian games and expost Nash equilibrium

Treating games of incomplete information, we demonstrate that the existence of an ex post stable strategy vector implies the existence of an approximate Bayesian equilibrium in pure strategies that is also expost stable. Through examples we demonstrate the ‘bounds obtained on the approximation’ are tight. The main results of this paper first appeared in University of Warwick Department of Economics Discussion Paper #710. 2004.     

On the saddle-point stability for a class of dynamic games

In this paper, we study the stability properties of the class of capital accumulation games introduced by Fershtman and Muller (Ref. 1). Both discrete and continuous time versions are discussed. It is shown that the open-loop Nash equilibrium solutions for both games are characterized by a general saddle-point property, a result best known from the turnpike literature in optimal growth theory. In the case of zero discount rates, an even stronger result can be derived: As long as the Hessian matrix of the instantaneous profit functions has a quasidominant diagonal, no pure imaginary roots are possible.The authors thank J. Boyd III, G. Feichtinger, S. Jørgensen, and G. Schwann for helpful comments. The first author acknowledges financial support from the Natural Science and Engineering Research Council of Canada, Grant No. OGP-0037342.     

On nash equilibrium solutions in nonzero-sum stochastic games with complete information

Two-person nonzero-sum stochastic games with complete information are considered. It is shown that it is sufficient to search the equilibrium solutions in a class of deterministic strategy pairs — the so-calledintimidation strategy pairs. Furthermore, properties of the set of all equilibrium losses of such strategy pairs are proved.     

On linear-quadratic Gaussian continuous-time Nash games

Two classes of linear-quadratic Gaussian continuous-time Nash games are considered. Their main characteristic is that the -fields with respect to which the control actions of the players have to be measurable at each instance of time are not affected by the past controls of the players. We show that, if a solution exists, then there exists a solution linear in the information, and also show how to construct all the solutions. Several conditions guaranteeing the existence of a unique solution are also given.This work was supported in part by the United States Air Force, Office of Scientific Research, under Grants Nos. AFOSR-80-0171 and AFOSR-82-0174.     

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.