Abstract
This thesis is devoted to a theoretical and numerical investigation of methods to solve games. These problems arise in many appli- cations, e.g., biology, economics, physics, where competition between different agents appears. In this case, the goal of each agent is in contrast with those of the others, and a competition game can be interpreted as a coupled optimization problem for which, in general, an optimal solution does not exist. In fact, an optimal strategy for one player may be unsatisfactory for the others. For this reason, a solution of a game is sought as an equilibrium and among the solutions concepts proposed in the literature, that of Nash equilibrium (NE) is the focus of this thesis.
The building blocks of the resulting differential Nash games are a dynamical model with different control functions associated with different players that pursue non-cooperative objectives. In particular, the aim of this thesis is on differential models having linear or bilinear state-strategy structures.
In this framework, in the first chapter, some well-known results are recalled, especially for non-cooperative linear-quadratic differential Nash games. Then, a bilinear Nash game is formulated and analysed. The main achievement in this chapter is Theorem 1.4.2 concerning existence of Nash equilibria for non-cooperative differential bilinear games. This result is obtained assuming a sufficiently small time horizon T , and an estimate of T is provided in Lemma 1.4.8 using specific properties of the regularized Nikaido-Isoda function.
In Chapter 2, in order to solve a bilinear Nash game, a semi-smooth Newton (SSN) scheme combined with a relaxation method is investigated, where the choice of a SSN scheme is motivated by the presence of constraints on the players’ actions that make the problem non-smooth. The resulting method is proved to be locally convergent in Theorem 2.1, and an estimate on the relaxation parameter is also obtained that relates the relaxation factor to the time horizon of a Nash equilibrium and to the other parameters of the game.
For the bilinear Nash game, a Nash bargaining problem is also introduced and dis- cussed, aiming at determining an improvement of all players’ objectives with respect to the Nash equilibrium. A characterization of a bargaining solution is given in Theorem 2.2.1 and a numerical scheme based on this result is presented that allows to compute this solution on the Pareto frontier. Results of numerical experiments based on a quantum model of two spin-particles and on a population dynamics model with two competing species are presented that successfully validate the proposed algorithms.
In Chapter 3 a functional formulation of the classical homicidal chauffeur (HC) Nash game is introduced and a new numerical framework for its solution in a time-optimal formulation is discussed. This methodology combines a Hamiltonian based scheme, with proximal penalty to determine the time horizon where the game takes place, with a Lagrangian optimal control approach and relaxation to solve the Nash game at a fixed end-time. The resulting numerical optimization scheme has a bilevel structure, which aims at decoupling the computation of the end-time from the solution of the pursuit-evader game. Several numerical experiments are performed to show the ability of the proposed algorithm to solve the HC game. Focusing on the case where a collision may occur, the time for this event is determined.
The last part of this thesis deals with the analysis of a novel sequential quadratic Hamiltonian (SQH) scheme for solving open-loop differential Nash games. This method is formulated in the framework of Pontryagin’s maximum principle and represents an efficient and robust extension of the successive approximations strategy in the realm of Nash games. In the SQH method, the Hamilton-Pontryagin functions are augmented by a quadratic penalty term and the Nikaido-Isoda function is used as a selection criterion. Based on this fact, the key idea of this SQH scheme is that the PMP characterization of Nash games leads to a finite-dimensional Nash game for any fixed time. A class of prob- lems for which this finite-dimensional game admits a unique solution is identified and for this class of games theoretical results are presented that prove the well-posedness of the proposed scheme. In particular, Proposition 4.2.1 is proved to show that the selection criterion on the Nikaido-Isoda function is fulfilled. A comparison of the computational performances of the SQH scheme and the SSN-relaxation method previously discussed is shown. Applications to linear-quadratic Nash games and variants with control con- straints, weighted L1 costs of the players’ actions and tracking objectives are presented that corroborate the theoretical statements.
CHAPTER ONE
Introduction
Since their appearance [69, 70], Nash games have attracted the attention of many scientists as they provide a convenient mathematical framework to investigate problems of competition and cooperation. A competition game can be interpreted as a coupled op- timization problem for which the Nash equilibrium (NE) defines a solution concept. In general, new solution concepts have been defined that lead to the concept of equilibrium solutions which allow to model various situations, depending on the information available to the players. For example, one can consider games with asymmetry of information, where one player represents a leader which selects its strategy in advance and the others play their strategies accordingly. These problems lead to a solution in the sense of a Stackelberger equilibrium [87]. On the other hand, there are a lot of symmetric situations where the players have no reasons to cooperate and do not share any information about their strategies. In this framework, a solution is sougth as a NE.
Non-cooperative differential Nash games were introduced in [52], where differential (dynamical) models govern the state of the system that is subject to the action of different controls representing the strategies of the players in the game, and to each player is associated an objective (cost) functional. With this setting, a NE is obtained when no player can improve its objective by unilateral change of its strategy. However, in many applications, players have willingness to cooperate to get an improvement in their costs. To model these situations, one can consider the concept of Pareto optimality. In this framework, a cooperation game can be interpreted as a parameterized optimal control problem [41]. Since, in general, a Pareto solution is not unique, it is reasonable to investigate whether there is a preferable choice with respect to NE. In this sense, there is the so-called bargaining theory. The most commonly bargaining solutions are the Nash bargaining solution [68], the Kalai-Smorodinsky solution [56] and the egalitarian solution [55]. In this thesis, we deal with the Nash bargaining problem.
Since the study of differential games initiated by Isaacs, many authors have focused on games having the so-called zero-sum property, that is, there is only one objective cost that one player tries to maximize and the other tries to minimize. However, later in [89], A.W. Starr and Y.C. Ho introduced noncooperative non zero-sum differential games. Differential games have received much attention in the field of economics and marketing [37, 54], and are well investigated in the case of linear differential models with linear player’s action mechanism and quadratic objectives; see, e.g., [21, 40, 43, 94]. For this class of games, P. Varaiya [94] proved that open-loop Nash equilibria exist for a sufficiently small duration of the game. Few years later, R.C. Scalzo [84] extended the work of Varaiya to linear-quadratic differential games with players’ strategies constrained in compact and convex subsets of Rn, proving that a NE exists for any arbitrary time.
On the other hand, much less is known in the case of nonlinear models, especially in the case of nonlinear functions of state and strategy and, in particular, in the case of a bilinear structure, where a function of the state variable multiplies the players’ actions. For a past review of works on differential Nash games, we refer to [92], and for more recent and detailed discussion and references see [40, 44, 54]. We also remark that nonlinear differential NE games have been investigated in the framework of Young measures; see, e.g., [5, 92]. We remark that Nash games are related to multi-objective optimization with nonlinear control structure, and therefore we believe that a study of NE game problems would be beneficial also for further development and application in this and related fields. In particular, our work could be extended to differential games with partial differential equations that are of interest in many applications. In fact, they appear in multi-objective shape optimization problems [78, 10], inverse problems [47, 48] and multi-agent problems [81]. A focus of this thesis is dynamical models with bilinear strategy-state structure, also called linear-affine systems. These models play a central role in many applications [72]. In particular, they are omnipresent in the field of quantum control problems [13] and in biology. However, the bilinear structure poses additional theoretical and numerical difficulties that hinder the further application of the NE framework to many envisioned problems. This is in particular true for new problems involving quantum systems [45] and biological systems [22]. For this reason, we discuss two related dynamical models that can both be put in the following general structure...
For more Mathematics Projects Click here
===================================================================Item Type: Project Material | Size: 95 pages | Chapters: 1-5
Format: MS Word | Delivery: Within 30Mins.
===================================================================
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.