Files in this item
Files  Description  Format 

application/pdf Yin_Huibing.pdf (3MB)  (no description provided) 
Description
Title:  Noncooperative static and dynamic games: addressing shared constraints and phase transitions 
Author(s):  Yin, Huibing 
Director of Research:  Mehta, Prashant G.; Shanbhag, Vinayak V. 
Doctoral Committee Chair(s):  Mehta, Prashant G. 
Doctoral Committee Member(s):  Shanbhag, Vinayak V.; Basar, Tamer; Cox, Charles L.; Meyn, Sean P.; Vakakis, Alexander F. 
Department / Program:  Mechanical Sci & Engineering 
Discipline:  Mechanical Engineering 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  meanfield game
oscillators synchronization of oscillators static and dynamic game phase transition flow control meanfield approximation optimal control nonlinear system HamiltonJacobiBellman (HJB) equation FokkerPlanckKolmogorov (FPK) equation Approximate Dynamic Programming (ADP) Nash equilibrium active queue management 
Abstract:  Compared to linear systems, nonlinear generalizations may exhibit both nonequilibrium and equilibrium behavior in the long run. The characterization of such behavior is challenging, particularly when overlaid by an optimization or control layer, and is of relevance in a range of applications, e.g., neuroscience, biology, economics, communication networks and power systems. The objective of this thesis is to consider these questions for two prototypical applications of nonlinear multiagent systems: (1) large population of coupled oscillators and (2) communication networks. The research is divided into the following three parts: Synchronization of oscillators: The purpose of this part is to understand phase transition in noncoop erative dynamic games with a large number of agents. The focus of analysis is on a variation of the large population linear quadratic Gaussian (LQG) model proposed by Huang et. al. 2007 [1], comprised here of a controlled Ndimensional stochastic differential equation model, coupled only through a cost function. The states are interpreted as phase angles for a collection of nonhomogeneous oscillators, and in this way the model may be regarded as an extension of the classical coupled oscillator model of Kuramoto. A deterministic PDE model is proposed, which is shown to approximate the stochastic system as the population size approaches infinity. Key to the analysis of the PDE model is the existence of a particular Nash equilibrium in which the agents ‘opt out’ of the game, setting their controls to zero, resulting in the ‘incoherence’ equilibrium. Next we introduce approximate dynamic programming (ADP) techniques for the design and adaptation (learning) of approximately optimal control laws for this model. For this purpose, a parameterization is proposed, based on analysis of the meanfield PDE model for the game. In an offline setting, a Galerkin procedure is introduced to choose the optimal parameters. In an online setting, a steepest descent algorithm is proposed. We provide detailed analysis of the optimal parameter values as well as the Bellman error with both the Galerkin approximation and the online algorithm. Methods from dynamical systems theory are used in a bifurcation analysis, based on a linearization of the PDE model about the incoherence equilibrium. A critical value of the control cost parameter is identified: Above this value, the oscillators are incoherent; and below this value (when control is sufficiently cheap) the oscillators synchronize. Then we simplify the analysis by relating the solutions of the PDE model to the solutions of a certain nonlinear eigenvalue problem. Both analysis and computation are significantly easier for the nonlinear eigenvalue problem. Apart from the bifurcation analysis that shows existence of a phase transition, we also describe a LyapunovSchmidt perturbation method to obtain asymptotic formulae for the small amplitude bifurcated solutions. A key question in the design of engineered competitive systems has been that of the efficiency of the associated equilibria. Yet, there is little known in this regard in the context of stochastic dynamic games in a large population regime. Here, we examine the efficiency of the associated meanfield equilibria with respect to a related welfare optimization problem. We construct variational problems both for the noncooperative game and its centralized counterpart and employ these problems as a vehicle for conducting this analysis. Using a bifurcation analysis, we analyze the variational solutions and the associated efficiency loss. An expression for the local bound of efficiency loss is obtained for the homogeneous population. All the conclusions are illustrated with results from numerical experiments. Nash games with coupled strategy sets: Generalized Nash equilibria (GNE) represent extensions of the Nash solution concept when the strategy sets are coupled across agents. We consider a restricted class of such games, referred to as generalized Nash games, in which the agents contend with shared or common constraints and their payoff functions are further linked via a scaled congestion cost metric. When strategy sets are continuous and the metric is an increasing convex function, a solution to a related variational in equality provides a set of equilibria characterized by common Lagrange multipliers for shared constraints. In general, this variational inequality problem is nonmonotone. However, we show that under mild con ditions, it admits solutions, even in the absence of restrictive compactness assumptions on strategy sets. Additionally, we show that the equilibrium is locally unique both in the primal space as well as in the larger primaldual space. The existence statements can be generalized to accommodate a piecewisesmooth metric while affine restrictions, surprisingly, lead to both existence and uniqueness guarantees. The second half of the part provides a brief discussion of distributed computation of such equilibria in monotone regimes via a distributed iterative Tikhonov regularization (ITR) scheme. Notably, such schemes are singletimescale counterparts of standard Tikhonov regularization methods and involve updating the regularization parameter after every gradient step. Application of such techniques to a class of network flow rate allocation games suggests that the ITR schemes perform better than their twotimescale counterparts. Nonlinear network flow control with AQM feedback: The last part of this thesis investigates stability, bifurcation and oscillations arising in a communication network model with a large number of heteroge neous users adopting a Transmission Control Protocol (TCP)like rate control scheme with an Active Queue Management (AQM) router. The heterogeneity in the system is due to different user delays that are known and fixed but taken from a given distribution. It is shown that for any given distribution of delays, there exists a critical amount of feedback (due to AQM) at which the equilibrium loses stability and a limit cy cling solution develops via a Hopf bifurcation. The nature (criticality) of the bifurcation is investigated with the aid of LyapunovSchmidt perturbation method. The results of the analysis are numerically verified and provide valuable insights into dynamics of the AQM control system. 
Issue Date:  20120522 
URI:  http://hdl.handle.net/2142/30922 
Rights Information:  Copyright 2012 Huibing Yin 
Date Available in IDEALS:  20120522 
Date Deposited:  201205 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Mechanical Science and Engineering
Item Statistics
 Total Downloads: 281
 Downloads this Month: 0
 Downloads Today: 0
 Statistics Report