Feedback Solution of a Class of Differential Games with Endogenous Horizons

In this paper, we consider a class of differential games in which the game ends when a subset of its state variables reaches a certain target at the terminal time. A special feature of the game is that its horizon is not fixed at the outset, but is determined endogenously by the actions of the players; conditions characterizing a feedback Nash equilibrium (FNE) solution of the game are derived for the first time. Extensions and illustrations of the derivation of FNE solutions of the game are provided.     

Identification of classes of differential games for which the open loop is a degenerate feedback Nash equilibrium

In general, it is clear that open-loop Nash equilibrium and feedback Nash equilibrium do not coincide. In this paper, we study the structure of differential games and develop a technique using which we can identify classes of games for which the open-loop Nash equilibrium is a degenerate feedback equilibrium. This technique clarifies the relationship between the assumptions made on the structure of the game and the resultant equilibrium.The author would like to thank E. Dockner, A. Mehlmann, and an anonymous referee for helpful comments.     

On Coincidence of Feedback Nash Equilibria and Stackelberg Equilibria in Economic Applications of Differential Games

The scope of the applicability of the feedback Stackelberg equilibrium concept in differential games is investigated. First, conditions for obtaining the coincidence between the stationary feedback Nash equilibrium and the stationary feedback Stackelberg equilibrium are given in terms of the instantaneous payoff functions of the players and the state equations of the game. Second, a class of differential games representing the underlying structure of a good number of economic applications of differential games is defined; for this class of differential games, it is shown that the stationary feedback Stackelberg equilibrium coincides with the stationary feedback Nash equilibrium. The conclusion is that the feedback Stackelberg solution is generally not useful to investigate leadership in the framework of a differential game, at least for a good number of economic applications This paper was presented at the 8th Viennese Workshop on Optimal Control, Dynamic Games, and Nonlinear Dynamics: Theory and Applications in Economics and OR/MS, Vienna, Austria, May 14–16, 2003, at the Seminar of the Instituto Complutense de Analisis Economico, Madrid, Spain, June 20, 2003, and at the Sevilla Workshop on Dynamic Economics and the Environment, Sevilla, Spain, July 2–3, 2003. The author is grateful to the participants in these sessions, in particular F.J. Andre and J. Ruiz, for their comments. Five referees provided particularly helpful suggestions. Financial support from the Ministerio de Ciencia y Tecnologia under Grant BEC2000-1432 is gratefully acknowledged.     

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.     

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.     

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.     

A Discrete-Time Dynamic Game of Seasonal Water Allocation

We present a method for the derivation of feedback Nash equi- libria in discrete-time finite-horizon nonstationary dynamic games. A partic- ular motivation for such games stems from environmental economics, where problems of seasonal competition for water levels occur frequently among heterogeneous economic agents. These agents are coupled through a state variable, which is the water level. Actions are strategically chosen to max- imize the agents individual season-dependent utility functions. We observe that, although a feedback Nash equilibrium exists, it does not satisfy the (exogenous) environmental watchdog expectations. We devise an incentive scheme to help meeting those expectations and calculate a feedback Nash equilibrium for the new game that uses the scheme. This solution is more environmentally friendly than the previous one. The water allocation game solutions help us to draw some conclusions regarding the agents behavior and also about the existence of feedback Nash equilibria in dynamic games. The paper draws from Refs.1–2. Its earlier version was presented at the Victoria International Conference 2004, Victoria University of Wellington, Wellington, New Zealand, February 9–13, 2004. We thank the anonymous referee and Christophe Deissenberg for insightful comments, which have helped us to clarify its message. We also thank our colleagues Sophie Thoyer, Robert Lifran, Odile Pourtalier, and Vladimir Petkov for helpful discussions on the model and techniques used in this Paper. Gratitude is expressed to the Kyoto Institute for Economic Research, Kyoto University, for this author's support in the final stages of the paper preparation     

An Approach to Fuzzy Noncooperative Nash Games

Systems that involve more than one decision maker are often optimized using the theory of games. In the traditional game theory, it is assumed that each player has a well-defined quantitative utility function over a set of the player decision space. Each player attempts to maximize/minimize his/her own expected utility and each is assumed to know the extensive game in full. At present, it cannot be claimed that the first assumption has been shown to be true in a wide variety of situations involving complex problems in economics, engineering, social and political sciences due to the difficulty inherent in defining an adequate utility function for each player in these types of problems. On the other hand, in many of such complex problems, each player has a heuristic knowledge of the desires of the other players and a heuristic knowledge of the control choices that they will make in order to meet their ends.In this paper, we utilize fuzzy set theory in order to incorporate the players' heuristic knowledge of decision making into the framework of conventional game theory or ordinal game theory. We define a new approach to N-person static fuzzy noncooperative games and develop a solution concept such as Nash for these types of games. We show that this general formulation of fuzzy noncooperative games can be applied to solve multidecision-making problems where no objective function is specified. The computational procedure is illustrated via application to a multiagent optimization problem dealing with the design and operation of future military operations.     

Slightly Altruistic Equilibria

We introduce a refinement concept for Nash equilibria (slightly altruistic equilibrium) defined by a limit process and which captures the idea of reciprocal altruism as presented in Binmore (Proceedings of the XV Italian Meeting on Game Theory and Applications, [2003]). Existence is guaranteed for every finite game and for a large class of games with a continuum of strategies. Results and examples emphasize the (lack of) connections with classical refinement concepts. Finally, it is shown that, under a pseudomonotonicity assumption on a particular operator associated to the game, it is possible, by selecting slightly altruistic equilibria, to eliminate those equilibria in which a player can switch to a strategy that is better for the others without leaving the set of equilibria. Part of the results in this paper have been presented at: First Spain, Italy, Netherlands Meeting on Game Theory, Maastricht, 2005; Fifth International ISDG Workshop, Segovia, 2005; GATE, Université Lumière Lyon 2, 2005; XXX AMASES Workshop, Trieste 2006; CSEF, Università di Salerno, 2006.     

Generic stability of Nash equilibria for noncooperative differential games

The stability of Nash equilibria against the perturbation of the right-hand side functions of state equations for noncooperative differential games is investigated. By employing the set-valued analysis theory, we show that the differential games whose equilibria are all stable form a dense residual set, and every differential game can be approximated arbitrarily by a sequence of stable differential games, that is, in the sense of Baire’s category most of the differential games are stable.     

A model of a 2-player stopping game with priority and asynchronous observation

Various models of 2-player stopping games have been considered which assume that players simultaneously observe a sequence of objects. Nash equilibria for such games can be found by first solving the optimal stopping problems arising when one player remains and then defining by recursion the normal form of the game played at each stage when both players are still searching (a 2 × 2 matrix game). The model considered here assumes that Player 1 always observes an object before Player 2. If Player 1 accepts the object, then Player 2 does not see that object. If Player 1 rejects an object, then Player 2 observes it and may choose to accept or reject it. It is shown that such a game can be solved using recursion by solving appropriately defined subgames, which are played at each moment when both players are still searching. In these subgames Player 1 chooses a threshold, such that an object is accepted iff its value is above this threshold. The strategy of Player 2 in this subgame is a stopping rule to be used when Player 1 accepts this object, together with a threshold to be used when Player 1 rejects the object. Whenever the payoff of Player 1 does not depend on the value of the object taken by Player 2, such a game can be treated as two optimisation problems. Two examples are given to illustrate these approaches.     

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.     

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.     

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.     

Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games

The noncooperative multi-leader-follower game can be formulated as a generalized Nash equilibrium problem where each player solves a nonconvex mathematical program with equilibrium constraints. Two major deficiencies exist with such a formulation: One is that the resulting Nash equilibrium may not exist, due to the nonconvexity in each players problem; the other is that such a nonconvex Nash game is computationally intractable. In order to obtain a viable formulation that is amenable to practical solution, we introduce a class of remedial models for the multi-leader-follower game that can be formulated as generalized Nash games with convexified strategy sets. In turn, a game of the latter kind can be formulated as a quasi-variational inequality for whose solution we develop an iterative penalty method. We establish the convergence of the method, which involves solving a sequence of penalized variational inequalities, under a set of modest assumptions. We also discuss some oligopolistic competition models in electric power markets that lead to multi-leader-follower games.Jong-Shi Pang: The work of this authors research was partially supported by the National Science Foundation under grant CCR-0098013 and ECS-0080577 and by the Office of Naval Research under grant N00014-02-1-0286.Masao Fukushima: The work of this authors research was partially supported by a Grant-in-Aid for Scientific Research from the Ministry of Education, Science, Culture and Sports of Japan.     

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.     

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

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

A Strong Anti-Folk Theorem

We study the properties of finitely complex, symmetric, globally stable, and semi-perfect equilibria. We show that: (1) If a strategy satisfies these properties then players play a Nash equilibrium of the stage game in every period; (2) The set of finitely complex, symmetric, globally stable, semi-perfect equilibrium payoffs in the repeated game equals the set of Nash equilibria payoffs in the stage game; and (3) A strategy vector satisfies these properties in a Pareto optimal way if and only if players play some Pareto optimal Nash equilibrium of the stage game in every stage. Our second main result is a strong anti-Folk Theorem, since, in contrast to what is described by the Folk Theorem, the set of equilibrium payoffs does not expand when the game is repeated.This paper is a revised version of Chapter 3 of my Ph.D. thesis, which has circulated under the title “An Interpretation of Nash Equilibrium Based on the Notion of Social Institutions”.     

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.