Noncooperative static and dynamic games: addressing shared constraints and phase transitions

Yin, Huibing

Permalink

https://hdl.handle.net/2142/30922 Copy

Description

Title

Noncooperative static and dynamic games: addressing shared constraints and phase transitions

Author(s)

Yin, Huibing

Issue Date

2012-05-22T00:15:25Z

Director of Research (if dissertation) or Advisor (if thesis)

• Mehta, Prashant G.
• Shanbhag, Vinayak V.

Doctoral Committee Chair(s)

Mehta, Prashant G.

Committee Member(s)

• Shanbhag, Vinayak V.
• Basar, Tamer
• Cox, Charles L.
• Meyn, Sean P.
• Vakakis, Alexander F.

Department of Study

Mechanical Sci & Engineering

Discipline

Mechanical Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• mean-field game
• oscillators
• synchronization of oscillators
• static and dynamic game
• phase transition
• flow control
• mean-field approximation
• optimal control
• Nonlinear system
• Hamilton-Jacobi-Bellman (HJB) equation
• Fokker-Planck-Kolmogorov (FPK) equation
• Approximate Dynamic Programming (ADP)
• Nash equilibrium
• active queue management

Abstract

Compared to linear systems, nonlinear generalizations may exhibit both non-equilibrium 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 multi-agent 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 N-dimensional stochastic differential equation model, coupled only through a cost function. The states are interpreted as phase angles for a collection of non-homogeneous 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 mean-field 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 Lyapunov-Schmidt 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 mean-field 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 non-monotone. 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 primal-dual space. The existence statements can be generalized to accommodate a piecewise-smooth 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 single-timescale 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 two-timescale 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 Lyapunov-Schmidt perturbation method. The results of the analysis are numerically verified and provide valuable insights into dynamics of the AQM control system.

Graduation Semester

2012-05

Permalink

http://hdl.handle.net/2142/30922

Copyright and License Information

Copyright 2012 Huibing Yin

Owning Collections