Perfect information stochastic games and related classes

Forn-person perfect information stochastic games and forn-person stochastic games with Additive Rewards and Additive Transitions (ARAT) we show the existence of pure limiting average equilibria. Using a similar approach we also derive the existence of limiting average ε-equilibria for two-person switching control stochastic games. The orderfield property holds for each of the classes mentioned, and algorithms to compute equilibria are pointed out.     

Nonlinear programming and stationary equilibria in stochastic games

Stationary equilibria in discounted and limiting average finite state/action space stochastic games are shown to be equivalent to global optima of certain nonlinear programs. For zero sum limiting average games, this formulation reduces to a linear objective, nonlinear constraints program, which finds the best stationary strategies, even when-optimal stationary strategies do not exist, for arbitrarily small. The work of the first author was supported in part by the Air Force Office of Scientific Research, and by the National Science Foundation under Grant No ECS-8704954.The work of the third author was supported by The Netherlands Organization for Scientific Research NWO, project 10-64-10.     

Equilibria and global dynamics of a problem with bifurcation from infinity

We consider a parabolic equation ut−Δu+u=0 with nonlinear boundary conditions , where as |s|→∞. In [J.M. Arrieta, R. Pardo, A. Rodríguez-Bernal, Bifurcation and stability of equilibria with asymptotically linear boundary conditions at infinity, Proc. Roy. Soc. Edinburgh Sect. A 137 (2) (2007) 225-252] the authors proved the existence of unbounded branches of equilibria for λ close to a Steklov eigenvalue of odd multiplicity. In this work, we characterize the stability of such equilibria and analyze several features of the bifurcating branches. We also investigate several question related to the global dynamical properties of the system for different values of the parameter, including the behavior of the attractor of the system when the parameter crosses the first Steklov eigenvalue and the existence of extremal equilibria. We include Appendix A where we prove a uniform antimaximum principle and several results related to the spectral behavior when the potential at the boundary is perturbed.     

Metric Characterizations of Tikhonov Well-Posedness in Value

In this paper, we discuss and give metric characterizations of Tikhonov well-posedness in value for Nash equilibria. Roughly speaking, Tikhonov well-posedness of a problem means that approximate solutions converge to the true solution when the degree of approximation goes to zero. If we add to the condition of -equilibrium that of -closeness in value to some Nash equilibrium, we obtain Tikhonov well-posedness in value, which we have defined in a previous paper. This generalization of Tikhonov well-posedness has the remarkable property of ordinality; namely, it is preserved under monotonic transformations of the payoffs. We show that a metric characterization of Tikhonov well-posedness in value is not possible unless the set of Nash equilibria is compact and nonempty.     

Equilibria of a stationary economy with recursive preferences

We consider an intertemporal stationary economy in discrete time, where agents have recursive preferences. Using dynamic programming, we show that equilibrium consumption trajectories from a capital stock are interior Pareto optima and are characterized by a strictly positive parameter in ^n–1, the set of agents' initial weights. We then exhibit prices that support the Pareto optima and use the Negishi method to characterize the parameters corresponding to equilibria. Finally, we prove the existence of equilibria and show that the number of regular equilibria is odd.     

Asymptotic Analysis of Linear Feedback Nash Equilibria in Nonzero-Sum Linear-Quadratic Differential Games

In this paper, we discuss nonzero-sum linear-quadratic differential games. For this kind of games, the Nash equilibria for different kinds of information structures were first studied by Starr and Ho. Most of the literature on the topic of nonzero-sum linear-quadratic differential games is concerned with games of fixed, finite duration; i.e., games are studied over a finite time horizon t _f. In this paper, we study the behavior of feedback Nash equilibria for t _f.In the case of memoryless perfect-state information, we study the so-called feedback Nash equilibrium. Contrary to the open-loop case, we note that the coupled Riccati equations for the feedback Nash equilibrium are inherently nonlinear. Therefore, we limit the dynamic analysis to the scalar case. For the special case that all parameters are scalar, a detailed dynamical analysis is given for the quadratic system of coupled Riccati equations. We show that the asymptotic behavior of the solutions of the Riccati equations depends strongly on the specified terminal values. Finally, we show that, although the feedback Nash equilibrium over any fixed finite horizon is generically unique, there can exist several different feedback Nash equilibria in stationary strategies for the infinite-horizon problem, even when we restrict our attention to Nash equilibria that are stable in the dynamical sense.     

Random Holonomy for Yang–Mills Fields: Long-Time Asymptotics

We study weak and strong convergence of the stochastic parallel transport for time t on Euclidean space. We show that the asymptotic behavior can be controlled by the Yang–Mills action and the Yang–Mills equations. For open paths we show that under appropriate curvature conditions there exits a gauge in which the stochastic parallel transport converges almost surely. For closed paths we show that there exists a gauge invariant notion of a weak limit of the random holonomy and we give conditions that insure the existence of such a limit. Finally, we study the asymptotic behavior of the average of the random holonomy in the case of t'Hooft's 1-instanton.     

A Technique to Improve the Error Propagation when Integrating Relative Equilibria

We study and perform a way to improve the propagation of errors in the numerical integration of relative equilibria solutions of Hamiltonian differential equations with symmetries. It is well known that in this case and for stable equilibria, the error growth is typically quadratic for general schemes and linear for schemes that preserve the invariant quantities of the problem. Here we present a technique to construct methods whose error propagation in time integration of stable relative equilibria is bounded. Numerical results are presented.     

Bias and Overtaking Equilibria for Zero-Sum Stochastic Differential Games

This paper deals with zero-sum stochastic differential games with long-run average payoffs. Our main objective is to give conditions for existence and characterization of bias and overtaking optimal equilibria. To this end, first we characterize the family of optimal average payoff strategies. Then, within this family, we impose suitable conditions to determine the subfamilies of bias and overtaking equilibria. A key step to obtain these facts is to show the existence of solutions to the average payoff optimality equations. This is done by the usual “vanishing discount” approach. Finally, a zero-sum game associated to a certain manufacturing process illustrates our results.     

Existence theorems of nash equilibria for non-cooperative n-person games

In this paper, we first obtain existence theorems of Nash equilibria for non-cooperative n-person games which generalize a corresponding result of Nikaido and Isoda (1955). As applications, we give two new existence theorems of -equilibrium points which generalize that of Tijs (1981). Finally, a saddle point theorem of Komiya (1986) is deduced from one of our existence theorems of -equilibrium points.     

Stochastic games with non-observable actions

We examine n-player stochastic games. These are dynamic games where a play evolves in stages along a finite set of states; at each stage players independently have to choose actions in the present state and these choices determine a stage payoff to each player as well as a transition to a new state where actions have to be chosen at the next stage. For each player the infinite sequence of his stage payoffs is evaluated by taking the limiting average. Normally stochastic games are examined under the condition of full monitoring, i.e. at any stage each player observes the present state and the actions chosen by all players. This paper is a first attempt towards understanding under what circumstances equilibria could exist in n-player stochastic games without full monitoring. We demonstrate the non-existence of -equilibria in n-player stochastic games, with respect to the average reward, when at each stage each player is able to observe the present state, his own action, his own payoff, and the payoffs of the other players, but is unable to observe the actions of them. For this purpose, we present and examine a counterexample with 3 players. If we further drop the assumption that the players can observe the payoffs of the others, then counterexamples already exist in games with only 2 players.     

Continuous-time constrained stochastic games with average criteria

In this paper, we consider the continuous-time nonzero-sum stochastic games under the constrained average criteria. The state space is denumerable and the action space of each player is a general Polish space. The transition rates, reward and cost functions are allowed to be unbounded. The main hypotheses in this paper include the standard drift conditions, continuity-compactness condition and some ergodicity assumptions. By applying the vanishing discount method, we obtain the existence of stationary constrained average Nash equilibria.     

Linear stability of relative equilibria in the charged three-body problem

A relative equilibrium is a periodic orbit of the n-body problem that rotates uniformly maintaining the same central configuration for all time. In this paper we generalize some results of R. Moeckel and we apply it to study the linear stability of relative equilibria in the charged three-body problem. We find necessary conditions to have relative equilibria linearly stable for the collinear charged three-body problem, for planar relative equilibria we obtain necessary and sufficient conditions for linear stability in terms of the parameters, masses and electrostatic charges. In the last case we obtain a stability inequality which generalizes the Routh condition of celestial mechanics. We also proof the existence of spatial relative equilibria and the existence of planar relative equilibria of any triangular shape.     

Some counterexamples to a generalized Saari's conjecture

For the Newtonian -body problem, Saari's conjecture states that the only solutions with a constant moment of inertia are relative equilibria, solutions rigidly rotating about their center of mass. We consider the same conjecture applied to Hamiltonian systems with power-law potential functions. A family of counterexamples is given in the five-body problem (including the Newtonian case) where one of the masses is taken to be negative. The conjecture is also shown to be false in the case of the inverse square potential and two kinds of counterexamples are presented. One type includes solutions with collisions, derived analytically, while the other consists of periodic solutions shown to exist using standard variational methods.

     

On equilibria in repeated games with absorbing states

We prove the existence of ε-(Nash) equilibria in two-person non-zerosum limiting average repeated games with absorbing states. These are stochastic games in which all states but one are absorbing. A state is absorbing if the probability of ever leaving that state is zero for all available pairs of actions.     

Iterative computation of noncooperative equilibria in nonzero-sum differential games with weakly coupled players

We study the Nash equilibria of a class of two-person nonlinear, deterministic differential games where the players are weakly coupled through the state equation and their objective functionals. The weak coupling is characterized in terms of a small perturbation parameter . With =0, the problem decomposes into two independent standard optimal control problems, while for 0, even though it is possible to derive the necessary and sufficient conditions to be satisfied by a Nash equilibrium solution, it is not always possible to construct such a solution. In this paper, we develop an iterative scheme to obtain an approximate Nash solution when lies in a small interval around zero. Further, after requiring strong time consistency and/or robustness of the Nash equilibrium solution when at least one of the players uses dynamic information, we address the issues of existence and uniqueness of these solutions for the cases when both players use the same information, either closed loop or open loop, and when one player uses open-loop information and the other player uses closed-loop information. We also show that, even though the original problem is nonlinear, the higher (than zero) order terms in the Nash equilibria can be obtained as solutions to LQ optimal control problems or static quadratic optimization problems.This research was supported in part by the US Department of Energy under Grant DE-FG-02-88-ER-13939.Paper presented at the 29th IEEE Conference on Decision and Control, Honolulu, Hawaii, 1990.     

Nonrandomized strategy equilibria in noncooperative stochastic games with additive transition and reward structure

In this paper, we study a discounted noncooperative stochastic game with an abstract measurable state space, compact metric action spaces of players, and additive transition and reward structure in the sense of Himmelberget al. (Ref. 1) and Parthasarathy (Ref. 2). We also assume that the transition law of the game is absolutely continuous with respect to some probability distributionp of the initial state and together with the reward functions of players satisfies certain continuity conditions. We prove that such a game has an equilibrium stationary point, which extends a result of Parthasarathy from Ref. 2, where the action spaces of players are assumed to be finite sets. Moreover, we show that our game has a nonrandomized (- )-equilibrium stationary point for each >0, provided that the probability distributionp is nonatomic. The latter result is a new existence theorem.     

Coordination games on graphs

We introduce natural strategic games on graphs, which capture the idea of coordination in a local setting. We study the existence of equilibria that are resilient to coalitional deviations of unbounded and bounded size (i.e., strong equilibria and k-equilibria respectively). We show that pure Nash equilibria and 2-equilibria exist, and give an example in which no 3-equilibrium exists. Moreover, we prove that strong equilibria exist for various special cases. We also study the price of anarchy (PoA) and price of stability (PoS) for these solution concepts. We show that the PoS for strong equilibria is 1 in almost all of the special cases for which we have proven strong equilibria to exist. The PoA for pure Nash equilbria turns out to be unbounded, even when we fix the graph on which the coordination game is to be played. For the PoA for k-equilibria, we show that the price of anarchy is between \(2(n-1)/(k-1) - 1\) and \(2(n-1)/(k-1)\). The latter upper bound is tight for \(k=n\) (i.e., strong equilibria). Finally, we consider the problems of computing strong equilibria and of determining whether a joint strategy is a k-equilibrium or strong equilibrium. We prove that, given a coordination game, a joint strategy s, and a number k as input, it is co-NP complete to determine whether s is a k-equilibrium. On the positive side, we give polynomial time algorithms to compute strong equilibria for various special cases.