Differential Games of Mixed Type with Control and Stopping Times

We study a zero sum differential game of mixed type where each player uses both control and stopping times. Under certain conditions we show that the value function for this problem exists and is the unique viscosity solution of the corresponding variational inequalities. We also show the existence of saddle point equilibrium for a special case of differential game.      

Strategic bidding in a discrete accumulating priority queue

We consider an unobservable M/G/1 accumulating priority queue where homogeneous customers choose one of a finite number of priority classes. We show that there are either one or two pure Nash equilibrium strategies. In the latter case they are two consecutive classes and there exists an equilibrium strategy mixing between these two classes. We find the best-response function and show that it is unimodal, with follow-the-crowd and avoid-the-crowd instances.     

Algorithm for constructing an optimal control strategy in a nonlinear differential game with Lipschitz compactly supported payoff

For a zero-sum differential game, we consider an algorithm for constructing optimal control strategies with the use of backward minimax constructions. The dynamics of the game is not necessarily linear, the players’ controls satisfy geometric constraints, and the terminal payoff function satisfies the Lipschitz condition and is compactly supported. The game value function is computed by multilinear interpolation of grid functions. We show that the algorithm error can be arbitrarily small if the discretization step in time is sufficiently small and the discretization step in the state space has a higher smallness order than the time discretization step. We show that the algorithm can be used for differential games with a terminal set. We present the results of computations for a problem of conflict control of a nonlinear pendulum.     

Stochastic Differential Games with Multiple Modes and Applications to Portfolio Optimization

Abstract

We study a zero-sum stochastic differential game with multiple modes. The state of the system is governed by “controlled switching” diffusion processes. Under certain conditions, we show that the value functions of this game are unique viscosity solutions of the appropriate Hamilton–Jacobi–Isaac' system of equations. We apply our results to the analysis of a portfolio optimization problem where the investor is playing against the market and wishes to maximize his terminal utility. We show that the maximum terminal utility functions are unique viscosity solutions of the corresponding Hamilton–Jacobi–Isaac' system of equations.     

Two-stage non-cooperative games with risk-averse players

This paper formally introduces and studies a non-cooperative multi-agent game under uncertainty. The well-known Nash equilibrium is employed as the solution concept of the game. While there are several formulations of a stochastic Nash equilibrium problem, we focus mainly on a two-stage setting of the game wherein each agent is risk-averse and solves a rival-parameterized stochastic program with quadratic recourse. In such a game, each agent takes deterministic actions in the first stage and recourse decisions in the second stage after the uncertainty is realized. Each agent’s overall objective consists of a deterministic first-stage component plus a second-stage mean-risk component defined by a coherent risk measure describing the agent’s risk aversion. We direct our analysis towards a broad class of quantile-based risk measures and linear-quadratic recourse functions. For this class of non-cooperative games under uncertainty, the agents’ objective functions can be shown to be convex in their own decision variables, provided that the deterministic component of these functions have the same convexity property. Nevertheless, due to the non-differentiability of the recourse functions, the agents’ objective functions are at best directionally differentiable. Such non-differentiability creates multiple challenges for the analysis and solution of the game, two principal ones being: (1) a stochastic multi-valued variational inequality is needed to characterize a Nash equilibrium, provided that the players’ optimization problems are convex; (2) one needs to be careful in the design of algorithms that require differentiability of the objectives. Moreover, the resulting (multi-valued) variational formulation cannot be expected to be of the monotone type in general. The main contributions of this paper are as follows: (a) Prior to addressing the main problem of the paper, we summarize several approaches that have existed in the literature to deal with uncertainty in a non-cooperative game. (b) We introduce a unified formulation of the two-stage SNEP with risk-averse players and convex quadratic recourse functions and highlight the technical challenges in dealing with this game. (c) To handle the lack of smoothness, we propose smoothing schemes and regularization that lead to differentiable approximations. (d) To deal with non-monotonicity, we impose a generalized diagonal dominance condition on the players’ smoothed objective functions that facilitates the application and ensures the convergence of an iterative best-response scheme. (e) To handle the expectation operator, we rely on known methods in stochastic programming that include sampling and approximation. (f) We provide convergence results for various versions of the best-response scheme, particularly for the case of private recourse functions. Overall, this paper lays the foundation for future research into the class of SNEPs that provides a constructive paradigm for modeling and solving competitive decision making problems with risk-averse players facing uncertainty; this paradigm is very much at an infancy stage of research and requires extensive treatment in order to meet its broad applications in many engineering and economics domains.     

Heterogeneous information lags and evolutionary stability

We investigate the effect of information lags in discrete time evolutionary game dynamics on symmetric games. At the end of each period, some players obtain information about the distribution of strategies among the entire population. They update their strategies according to this information. In contrast to the previous literature (e.g., Tao and Wang (1997)) where large delays lead to instability, we show that the relationship between information lags and the stability of equilibria is not “monotonic.” In anti-coordination games under smoothed best-response dynamics, a small probability of delay can stabilize the equilibrium, while a large probability can destabilize it.     

When “Better” is better than “Best”

We consider two-player normal form games where each player has the same finite strategy set. The payoffs of each player are assumed to be i.i.d. random variables with a continuous distribution. We show that, with high probability, the better-response dynamics converges to pure Nash equilibrium whenever there is one, whereas best-response dynamics fails to converge, as it is trapped.     

Generalization of the main equation of differential game theory

We consider feedback, two-person, zero-sum differential games. We obtain two inequalities for the directional derivatives of the nonsmooth value function. We show that these inequalities, together with the boundary conditions, constitute necessary and sufficient conditions which the value function must satisfy. In the region where the value function is differentiable, the inequalities become the well-known main equation of differential game theory (Isaacs-Bellman equation). The results obtained here may be useful in the approximation of the value function by piecewise smooth splines and also in the classification of singular surfaces.The author would like to thank Academician N. N. Krasovskii for his valuable advice and encouragement.     

A Probabilistic-Numerical Approximation for an Obstacle Problem Arising in Game Theory

We investigate a two-player zero-sum stochastic differential game in which one of the players has more information on the game than his opponent. We show how to construct numerical schemes for the value function of this game, which is given by the solution of a quasilinear partial differential equation with obstacle.     

Algorithms for generalized potential games with mixed-integer variables

We consider generalized potential games, that constitute a fundamental subclass of generalized Nash equilibrium problems. We propose different methods to compute solutions of generalized potential games with mixed-integer variables, i.e., games in which some variables are continuous while the others are discrete. We investigate which types of equilibria of the game can be computed by minimizing a potential function over the common feasible set. In particular, for a wide class of generalized potential games, we characterize those equilibria that can be computed by minimizing potential functions as Pareto solutions of a particular multi-objective problem, and we show how different potential functions can be used to select equilibria. We propose a new Gauss–Southwell algorithm to compute approximate equilibria of any generalized potential game with mixed-integer variables. We show that this method converges in a finite number of steps and we also give an upper bound on this number of steps. Moreover, we make a thorough analysis on the behaviour of approximate equilibria with respect to exact ones. Finally, we make many numerical experiments to show the viability of the proposed approaches.     

Contagion and coordination in random networks

We study the problem of spreading a particular behavior among agents located in a random social network. In each period of time, neighboring agents interact strategically playing a 2 ×  2 coordination game. Assuming myopic best-response dynamics, we show that there exists a threshold for the degree of risk dominance of an action such that below that threshold, contagion of the action occurs. This threshold depends on the connectivity distribution of the network. Based on this, we show that the well-known scale-free networks do not always properly support this type of contagion, which is better accomplished by more intermediate variance networks.     

由具奇异系数的强椭圆微分算子生成的解析半群

本文提出了低阶项系数具一定奇异性的高阶强椭圆微分算子生成解析半群的条 件,其包含了低阶项系数属于Schecter位势类的情形.特别地,低阶项系数属于LP(Rn) 的情形也在其中.作为应用,得到低阶项系数属于LP(Rn)的强椭圆算子的相应半群生 成,且p还可取到一些临界值.     

BSDES IN GAMES,COUPLED WITH THE VALUE FUNCTIONS. ASSOCIATED NONLOCAL BELLMAN-ISAACS EQUATIONS

We establish a new type of backward stochastic differential equations(BSDEs)connected with stochastic differential games(SDGs), namely, BSDEs strongly coupled with the lower and the upper value functions of SDGs, where the lower and the upper value functions are defined through this BSDE. The existence and the uniqueness theorem and comparison theorem are proved for such equations with the help of an iteration method. We also show that the lower and the upper value functions satisfy the dynamic programming principle. Moreover, we study the associated Hamilton-Jacobi-Bellman-Isaacs(HJB-Isaacs)equations, which are nonlocal, and strongly coupled with the lower and the upper value functions. Using a new method, we characterize the pair(W, U) consisting of the lower and the upper value functions as the unique viscosity solution of our nonlocal HJB-Isaacs equation. Furthermore, the game has a value under the Isaacs' condition.     

On balanced games with infinitely many players: Revisiting Schmeidler's result

We consider transferable utility cooperative games with infinitely many players and the core understood in the space of bounded additive set functions. We show that, if a game is bounded below, then its core is non-empty if and only if the game is balanced. This finding generalizes Schmeidler (1967) “On Balanced Games with Infinitely Many Players”, where the game is assumed to be non-negative. We also generalize Schmeidler's (1967) result to the case of restricted cooperation too.     

A BSDE approach to stochastic differential games with incomplete information

We consider a two-player zero-sum stochastic differential game in which one of the players has a private information on the game. Both players observe each other, so that the non-informed player can try to guess his missing information. Our aim is to quantify the amount of information the informed player has to reveal in order to play optimally: to do so, we show that the value function of this zero-sum game can be rewritten as a minimization problem over some martingale measures with a payoff given by the solution of a backward stochastic differential equation.     

Correlated equilibria in some classes of two-person games

A correlated equilibrium in a two-person game is “good” if for everyNash equilibrium there is a player who prefers the correlated equilibrium to theNash equilibrium. If a game is “best-response equivalent” to a two-person zero-sum game, then it has no good correlated equilibria. But games which are “almost strictly competitive” or “order equivalent” to a two-person zero-sum game may have good correlated equilibria.     

Advertising in a Differential Oligopoly Game

We illustrate a differential oligopoly game where firms compete à la Cournot in homogeneous goods in the market phase and invest in advertising activities aimed at increasing the consumers reservation price. Such investments produce external effects, characterizing the advertising activity as a public good. We derive the open-loop and closed-loop Nash equilibria, and show that the properties of the equilibria depend on the curvature of the market demand function. The comparative assessment of these equilibria shows that the firms advertising efforts are larger in the open-loop equilibrium than in the closed-loop equilibrium. We also show that a cartel involving all the firms, setting both output levels and advertising efforts, may produce a steady state where the social welfare level is higher than the social welfare levels associated with both open-loop and closed-loop noncooperative settings.     

Nash bargaining solution under externalities

We define a Nash bargaining solution (NBS) of partition function games. Based on a partition function game, we define an extensive game, which is a propose–respond sequential bargaining game where the rejecter of a proposal exits from the game with some positive probability. We show that the NBS is supported as the expected payoff profile of any stationary subgame perfect equilibrium (SSPE) of the extensive game such that in any subgame, a coalition of all active players forms immediately. We provide a necessary and sufficient condition for such an SSPE to exist. Moreover, we consider extensions to the cases of nontransferable utilities, time discounting and multiple-coalition formation.     

Weak and Strong Time Consistency in a Differential Oligopoly Game with Capital Accumulation

We illustrate a differential oligopoly game with capital accumulation where the accumulation dynamics of productive capacity is modelled à la Ramsey. The model is solved under the open-loop information structure, to show that it admits an open-loop Nash equilibrium which is indeed a degenerate feedback one and therefore strongly time consistent, even if, by construction, the problem under consideration is not a linear state game. We thank George Leitmann, Massimo Marinacci, Daniele Ritelli, Arsen Palestini and two anonymous referees for very useful comments and suggestions.     

An Iterative Global Optimization Algorithm for Potential Energy Minimization

In this paper we propose an algorithm for the minimization of potential energy functions. The new algorithm is based on the differential evolution algorithm of Storn and Price (Journal of Global Optimization, vol. 11, pp. 341–359, 1997). The algorithm is tested on two different potential energy functions. The first function is the Lennard Jones energy function and the second function is the many-body potential energy function of Tersoff (Physics Review B, vol. 37, pp. 6991–7000, 1988; vol. 38, pp. 9902–9905, 1988). The first problem is a pair potential and the second problem is a semi-empirical many-body potential energy function considered for silicon-silicon atomic interactions. The minimum binding energies of up to 30 atoms are reported.Visitor at the Institute for Mathematics and its Applications, University of Minnesota, USA.