基于策略迭代算法的连续时间线性Markov跳变系统非零和微分反馈Nash控制

针对一类连续时间线性Markov跳变系统,本文提出了一种新的策略迭代算法用于求解系统的非零和微分反馈Nash控制问题.通过求解耦合的数值迭代解,以获得具有线性动力学特性和无限时域二次成本的双层非零和微分策略的Nash均衡解.在每一个策略层,采用策略迭代算法来计算与每一组给定的反馈控制策略相关联的最小无限时域值函数.然后,通过子系统分解将Markov跳变系统分解为N个并行的子系统,并将该算法应用于跳变系统.本文提出的策略迭代算法可以很容易求解非零和微分策略所对应的耦合代数Riccati方程,且对高维系统有效.最后通过仿真示例证明了本文设计方法的有效性和可行性.     

线性时变二次微分对策Nash策略的小波分析法(Ⅱ)——小波逼近解的收敛性

研究小波逼近分析方法的收敛性问题, 对线性时变二次微分对策Nash策略情形, 证明了Nash策略的小波逼近解收敛于精确解, 基于小波逼近的多尺度多分辨特性, 给出了误差估计的阶数.     

带Poisson跳的线性二次随机微分博弈及其在鲁棒控制中的应用

研究了一类带Poisson跳扩散过程的线性二次随机微分博弈,包括非零和博弈的Nash均衡策略与零和博弈的鞍点均衡策略问题．利用微分博弈的最大值原理,得到Nash均衡策略的存在条件等价于两个交叉耦合的矩阵Riccati方程存在解,鞍点均衡策略的存在条件等价于一个矩阵Riccati方程存在解的结论,并给出了均衡策略的显式表达及最优性能泛函值．最后,将所得结果应用于现代鲁棒控制中的随机H₂/H_∞控制与随机H_∞控制问题,得到了鲁棒控制策略的存在条件及显式表达,并验证所得结果在金融市场投资组合优化问题中的应用．     

多组对策系统非劣Nash策略的最优均衡解算法

多组对策系统中求解组与组之间的非劣Nash策略至关重要.如何针对一般问题解析求出非劣Nash策略还没有有效的方法.本文阐述了一种利用组与组之间的非劣反应集构造求解非劣Nash策略的迭代算法.为此首先引进多组对策系统组内部合作对策的最优均衡值和最优均衡解的概念,然后通过证明最优均衡解是组内部隐含某一权重向量的合作对策的非劣解,得到求解合作对策的单目标规划问题.进一步说明在组内部该问题的解不仅是非劣解而且对所有局中人都优于不合作时的Nash平衡策略.最后给出了验证该算法有效性的一个实际例子.     

线性时变二次微分对策Nash策略的小波分析法(Ⅰ)——小波逼近解

基于小波多尺度逼近特性,提出了一种求解线性时变系统中微分对策Nash策略的新方法.该法避免求解耦合Riccati微分方程,而只需求解代数方程,适合于计算机求解.     

多随从诱导策略

本文研究多随从诱导问题.当随从进行Nash不合作对策时,得到了连续诱导策略的一 个存在性充分条件与一种设计方法;当随从进行Nash协商对策时,得到了仿射型和连续型 诱导策略的存在性充分条件与设计方法.     

基于微分对策的供应链合作广告决策研究

针对供应链系统中制造商和零售商的合作广告计划问题，利用微分对策构建动态模型．分别研究制造商和零售商在合作和非合作条件下的广告策略．运用动态规划原理。分别得出静态反馈Nash均衡和反馈Stackelberg均衡，将两种均衡策略加以比较，结果显示合作广告计划是供应链系统中的一种协调和激励机制，可以提高两个渠道成员以及整个供应链系统的利润。     

关于定量与定性微分对策

本文将文献[2,3,4,5,7]中的方法加以发展,用来解决一类定量和定性微分对策问题. 对于定量对策,我们推出最优策略(u,v)所应满足的必要条件,即"双方极值原理".对于定 性对策,也得到最优策略(u,v)的必要条件、且不必如文献[1]中那样限于"小范围".并确定了 组成界栅(barrier)的轨线的方程. 还讨论了一些其他问题,如充分条件、目标集的更一般的形式、定性对策与能控性问题间 的关系等. 可见,这种方法是一种可用来解决多种类型的最优控制和微分对策问题的有力工具. 文中附有二例.     

非线性零和微分对策的事件触发自适应动态规划算法

针对一类非线性零和微分对策问题,本文提出了一种事件触发自适应动态规划(event-triggered adaptive dynamic programming,ET--ADP)算法在线求解其鞍点.首先,提出一个新的自适应事件触发条件.然后,利用一个输入为采样数据的神经网络(评价网络)近似最优值函数,并设计了新型的神经网络权值更新律使得值函数、控制策略及扰动策略仅在事件触发时刻同步更新.进一步地,利用Lyapunov稳定性理论证明了所提出的算法能够在线获得非线性零和微分对策的鞍点且不会引起Zeno行为.所提出的ET--ADP算法仅在事件触发条件满足时才更新值函数、控制策略和扰动策略,因而可有效减少计算量和降低网络负荷.最后,两个仿真例子验证了所提出的ET--ADP算法的有效性.     

线性时变二次微分对策Nash策略的小波分析法(Ⅰ)——小波逼近解

基于小波多尺度逼近特性，提出了一种求解线性时变系统中微分对策Nash策略的新方法，该法避免求解耦合Riccati微分方程，而只需求解代解方程，适合于计算机求解。     

A note on proofs of existence of Nash equilibria in finite strategic games,of two players

Known general proofs of Nash’s Theorem (about the existence of Nash Equilibria (NEa) in finite strategic games) rely on the use of a fixed point theorem (e.g. Brouwer’s or Kakutani’s). While it seems that there is no general way of proving the existence of Nash equilibria without the use of a fixed point theorem, there do however exist some (not so common in the CS literature) proofs that seem to indicate alternative proof paths, for games of two players. This note discusses two such proofs.     

Feedback control on Nash equilibrium for discrete-time stochastic systems with Markovian jumps: Finite-horizon case

In this paper, we consider the feedback control on nonzero-sum linear quadratic (LQ) differential games in finite horizon for discrete-time stochastic systems with Markovian jump parameters and multiplicative noise. Four-coupled generalized difference Riccati equations (GDREs) are obtained, which are essential to find the optimal Nash equilibrium strategies and the optimal cost values of the LQ differential games. Furthermore, an iterative algorithm is given to solve the four-coupled GDREs. Finally, a suboptimal solution of the LQ differential games is proposed based on a convex optimization approach and a simplification of the suboptimal solution is given. Simulation examples are presented to illustrate the effectiveness of the iterative algorithm and the suboptimal solution.     

Sampled fictitious play for approximate dynamic programming

Sampled fictitious play (SFP) is a recently proposed iterative learning mechanism for computing Nash equilibria of non-cooperative games. For games of identical interests, every limit point of the sequence of mixed strategies induced by the empirical frequencies of best response actions that players in SFP play is a Nash equilibrium. Because discrete optimization problems can be viewed as games of identical interests wherein Nash equilibria define a type of local optimum, SFP has recently been employed as a heuristic optimization algorithm with promising empirical performance. However, there have been no guarantees of convergence to a globally optimal Nash equilibrium established for any of the problem classes considered to date. In this paper, we introduce a variant of SFP and show that it converges almost surely to optimal policies in model-free, finite-horizon stochastic dynamic programs. The key idea is to view the dynamic programming states as players, whose common interest is to maximize the total multi-period expected reward starting in a fixed initial state. We also offer empirical results suggesting that our SFP variant is effective in practice for small to moderate sized model-free problems.     

Infinite horizon linear quadratic differential games for discrete-time stochastic systems

This paper deals with the infinite horizon linear quadratic(LQ)differential games for discrete-time stochastic systems with both state and control dependent noise.The Popov-Belevitch-Hautus(PBH)criteria for exact observability and exact detectability of discrete-time stochastic systems are presented.By means of them,we give the optimal strategies (Nash equilibrium strategies)and the optimal cost values for infinite horizon stochastic differential games.It indicates that the infinite horizon LQ stochastic differential games are associated with four coupled matrix-valued equations.Furthermore, an iterative algorithm is proposed to solve the four coupled equations.Finally,an example is given to demonstrate our results.     

Comparing the notions of optimality in CP-nets,strategic games and soft constraints

The notion of optimality naturally arises in many areas of applied mathematics and computer science concerned with decision making. Here we consider this notion in the context of three formalisms used for different purposes in reasoning about multi-agent systems: strategic games, CP-nets, and soft constraints. To relate the notions of optimality in these formalisms we introduce a natural qualitative modification of the notion of a strategic game. We show then that the optimal outcomes of a CP-net are exactly the Nash equilibria of such games. This allows us to use the techniques of game theory to search for optimal outcomes of CP-nets and vice-versa, to use techniques developed for CP-nets to search for Nash equilibria of the considered games. Then, we relate the notion of optimality used in the area of soft constraints to that used in a generalization of strategic games, called graphical games. In particular we prove that for a natural class of soft constraints that includes weighted constraints every optimal solution is both a Nash equilibrium and Pareto efficient joint strategy. For a natural mapping in the other direction we show that Pareto efficient joint strategies coincide with the optimal solutions of soft constraints.      

Nash equilibria: Complexity,symmetries, and approximation

We survey recent joint work with Christos Papadimitriou and Paul Goldberg on the computational complexity of Nash equilibria. We show that finding a Nash equilibrium in normal form games is computationally intractable, but in an unusual way. It does belong to the class NP; but Nash’s theorem, showing that a Nash equilibrium always exists, makes the possibility that it is also NP-complete rather unlikely. We show instead that the problem is as hard computationally as finding Brouwer fixed points, in a precise technical sense, giving rise to a new complexity class called PPAD. The existence of the Nash equilibrium was established via Brouwer’s fixed-point theorem; hence, we provide a computational converse to Nash’s theorem.To alleviate the negative implications of this result for the predictive power of the Nash equilibrium, it seems natural to study the complexity of approximate equilibria: an efficient approximation scheme would imply that players could in principle come arbitrarily close to a Nash equilibrium given enough time. We review recent work on computing approximate equilibria and conclude by studying how symmetries may affect the structure and approximation of Nash equilibria. Nash showed that every symmetric game has a symmetric equilibrium. We complement this theorem with a rich set of structural results for a broader, and more interesting class of games with symmetries, called anonymous games.     

Existence results for the three-point impulsive boundary value problem involving fractional differential equations

In this paper, we consider the existence of solutions for a class of three-point boundary value problems involving nonlinear impulsive fractional differential equations. By use of Banach’s fixed point theorem and Schauder’s fixed point theorem, some existence results are obtained.     

The Nash Equilibrium Point of Dynamic Games Using Evolutionary Algorithms in Linear Dynamics and Quadratic System

In this paper, examining some games, we show that classical techniques are not always effective for games with not many stages and players and it can’t be claimed that these techniques of solution always obtain the optimal and actual Nash equilibrium point. For solving these problems, two evolutionary algorithms are then presented based on the population to solve general dynamic games. The first algorithm is based on the genetic algorithm and we use genetic algorithms to model the players' learning process in several models and evaluate them in terms of their convergence to the Nash Equilibrium. in the second algorithm, a Particle Swarm Intelligence Optimization (PSO) technique is presented to accelerate solutions’ convergence. It is claimed that both techniques can find the actual Nash equilibrium point of the game keeping the problem’s generality and without imposing any limitation on it and without being caught by the local Nash equilibrium point. The results clearly show the benefits of the proposed approach in terms of both the quality of solutions and efficiency.     

Equilibria,fixed points,and complexity classes

Many models from a variety of areas involve the computation of an equilibrium or fixed point of some kind. Examples include Nash equilibria in games; market equilibria; computing optimal strategies and the values of competitive games (stochastic and other games); stable configurations of neural networks; analysing basic stochastic models for evolution like branching processes and for language like stochastic context-free grammars; and models that incorporate the basic primitives of probability and recursion like recursive Markov chains. It is not known whether these problems can be solved in polynomial time. There are certain common computational principles underlying different types of equilibria, which are captured by the complexity classes PLS, PPAD, and FIXP. Representative complete problems for these classes are, respectively, pure Nash equilibria in games where they are guaranteed to exist, (mixed) Nash equilibria in two-player normal form games, and (mixed) Nash equilibria in normal form games with three (or more) players. This paper reviews the underlying computational principles and the corresponding classes.