A Matrix Approach to the Analysis and Control of Networked Evolutionary Games with Bankruptcy Mechanism

This paper investigates the evolutionary dynamic and control problem for a kind of networked evolutionary games with bankruptcy mechanism by using semi‐tensor product of matrices, and presents a number of new results. First, this kind of games are expressed as logical dynamic networks and converted into their algebraic forms, based on which, the evolutionary dynamics of the given games can be discussed. Second, the control problem is considered, and a control sequence is designed to guarantee that none of players goes bankrupt as the control target requires. Finally, an illustrative example is given to show the effectiveness of our main results.     

Modelling and strategy consensus for a class of networked evolutionary games

Using the semi-tensor product method, this paper investigates the algebraic formulation and strategy consensus for a class of networked evolutionary games (NEGs) with ‘unconditional imitation updating rule’, and presents a number of new results. First, the given NEG is converted to an algebraic form via the semi-tensor product method, and an algorithm is established to obtain the algebraic expression of the considered game. Second, based on the algebraic form, the behaviours of the players in the given evolutionary games are analysed, and some meaningful results are presented. Finally, the strategy consensus problem is considered by adding a pseudo-player to the game, and a free-type control sequence is designed to make the given NEG reach strategy consensus. The study of an illustrative example shows that the new results obtained in this paper work very well.     

Algebraic formulation and strategy optimization for a class of evolutionary networked games via semi-tensor product method

Using the semi-tensor product method, this paper investigates the algebraic formulation and strategy optimization for a class of evolutionary networked games with “myopic best response adjustment” rule, and presents a number of new results. First, the dynamics of the evolutionary networked game is converted to an algebraic form via the semi-tensor product, and an algorithm is established to construct the algebraic formulation for the game. Second, based on the algebraic form, the dynamical behavior of evolutionary networked games is discussed, and some interesting results are presented. Finally, the strategy optimization problem is considered by adding a pseudo-player to the game, and a free-type control sequence is designed to maximize the average payoff of the pseudo-player. The study of an illustrative example shows that the new results obtained in this paper work very well.     

多值逻辑网络的输出跟踪牵制控制

本文利用代数状态空间方法,研究了多值逻辑控制网络的输出跟踪牵制控制.首先利用矩阵的半张量积给出了带牵制控制的多值逻辑控制网络的代数表示.其次基于该代数表示,定义了一组合适的能达集,并建立了多值逻辑控制网络输出跟踪牵制控制器的设计方法.再次,利用多值逻辑哑算子的性质,给出了多值逻辑控制网络分布式输出跟踪控制问题可解的充要条件.最后将所得的理论结果应用于网络演化博弈的演化行为分析.     

A Matrix Approach to the Modeling and Analysis of Networked Evolutionary Games With Time Delays

Using the semi-tensor product method, this paper investigates the modeling and analysis of networked evolutionary games (NEGs) with finite memories, and presents a number of new results. Firstly, a kind of algebraic expression is formulated for the networked evolutionary games with finite memories, based on which the behavior of the corresponding evolutionary game is analyzed. Secondly, under a proper assumption, the existence of Nash equilibrium of the given networked evolutionary games is proved and a free-type strategy sequence is designed for the convergence to the Nash equilibrium. Finally, an illustrative example is worked out to support the obtained new results.      

Suboptimal Strategies of Linear Quadratic Closed-loop Differential Games: An BMI Approach

The suboptimal control program via memoryless state feedback strategies for LQ differential games with multiple players is studied in this paper. Sufficient conditions for the existence of the suboptimal strategies for LQ differential games are presented. It is shown that the suboptimal strategies of LQ differential games are associated with a coupled algebraic Riccati inequality. Furthermore, the problem of designing suboptimal strategies is considered. A non-convex optimization problem with BMI constrains is formulated to design the suboptimal strategies which minimizes the performance indices of the closed-loop LQ differential games and can be solved by using LMI Toolbox of MATLAB, An example is given to illustrate the proposed results.     

线性二次闭环微分对策次优对策的双线性矩阵不等式方法

The suboptimal control program via memoryless state feedback strategies for LQ differential games with multiple players is studied in this paper. Sufficient conditions for the existence of the suboptimal strategies for LQ differential games are presented. It is shown that the suboptimal strategies of LQ differential games are associated with a coupled algebraic Riccati inequality. Furthermore, the problem of designing suboptimal strategies is considered. A non-convex optimization problem with BMI constrains is formulated to design the suboptimal strategies which minimizes the performance indices of the closed-loop LQ differential games and can be solved by using LMI Toolbox of MATLAB. An example is given to illustrate the proposed results.     

Modelling and strategy optimisation for a kind of networked evolutionary games with memories under the bankruptcy mechanism

This paper investigates the evolutionary dynamic and strategy optimisation for a kind of networked evolutionary games whose strategy updating rules incorporate ‘bankruptcy’ mechanism, and the situation that each player's bankruptcy is due to the previous continuous low profits gaining from the game is considered. First, by using semi-tensor product of matrices method, the evolutionary dynamic of this kind of games is expressed as a higher order logical dynamic system and then converted into its algebraic form, based on which, the evolutionary dynamic of the given games can be discussed. Second, the strategy optimisation problem is investigated, and some free-type control sequences are designed to maximise the total payoff of the whole game. Finally, an illustrative example is given to show that our new results are very effective.     

Algebraization and Optimization of Networked Evolutionary Boxed Pig Games with Passive Reward and Punishment

This paper investigates the evolutionary dynamics and optimization problem of the boxed pig games with the mechanism of passive reward and punishment by using the semi‐tensor product method. First, an algorithm is provided to construct the algebraic formulation for the dynamics of the networked evolutionary boxed pig games with the mechanism of passive reward and punishment. Then, the impact of reward and punishment parameters on the final cooperation level of the whole network is discussed. Finally, an example is provided to show the effectiveness of our results.     

Weighted Nash equilibrium of incomplete-profile networked evolutionary games with multiple payoffs

This paper investigates the existence and convergence of weighted Nash equilibrium for incomplete-profile networked evolutionary games with multiple payoffs. First, the incomplete-profile networked evolutionary game under probabilistic myopic best response adjustment rule is transformed into an algebraic form based on the semi-tensor product of matrices. Second, a method for calculating weighted Nash equilibrium is presented, and the relationship between weighted Nash equilibrium and positive-probability fixed point is derived. Furthermore, a criterion is provided to verify whether the profiles in the feasible profile set can converge to the set of weighted Nash equilibriums with probability one. Finally, an illustrative example is given to support the new results obtained in this paper.     

演化博弈的鲁棒稳定与镇定

本文研究了干扰影响下演化博弈的稳定与镇定问题. 首先, 文章给出了干扰博弈、控制–干扰博弈以及鲁棒 Nash均衡等概念, 并在此基础上提出了干扰演化博弈与控制–干扰演化博弈鲁棒稳定与镇定的定义. 其次, 利用矩 阵半张量积工具, 得到了干扰演化博弈与控制–干扰演化博弈的代数状态空间表示, 将鲁棒稳定与镇定问题转化为 一个辅助系统的集合稳定与集合镇定问题. 紧接着, 文章建立了干扰演化博弈与控制–干扰演化博弈鲁棒稳定与镇 定的充分必要条件, 并进一步设计了状态反馈控制器. 最后, 通过两个例子验证了所得结论的有效性.     

Semi-tensor product approach to networked evolutionary games

In this paper a comprehensive introduction for modeling and control of networked evolutionary games （NEGs） via semi-tensor product （STP） approach is presented. First, we review the mathematical model of an NEG, which consists of three ingredients： network graph, fundamental network game, and strategy updating rule. Three kinds of network graphs are considered, which are i） undirected graph for symmetric games; ii） directed graph for asymmetric games, and iii） d-directed graph for symmetric games with partial neighborhood information. Three kinds of fundamental evolutionary games （FEGs） are discussed, which are i） two strategies and symmetric （S-2）; ii） two strategies and asymmetric （A-2）; and iii） three strategies and symmetric （S-3）. Three strategy updating rules （SUR） are introduced, which are i） Unconditional Imitation （UI）; ii） Fermi Rule（FR）; iii） Myopic Best Response Adjustment Rule （MBRA）. First, we review the fundamental evolutionary equation （FEE） and use it to construct network profile dynamics （NPD）of NEGs.
To show how the dynamics of an NEG can be modeled as a discrete time dynamics within an algebraic state space, the fundamental evolutionary equation （FEE） of each player is discussed. Using FEEs, the network strategy profile dynamics （NSPD） is built by providing efficient algorithms. Finally, we consider three more complicated NEGs： i） NEG with different length historical information, ii） NEG with multi-species, and iii） NEG with time-varying payoffs. In all the cases, formulas are provided to construct the corresponding NSPDs. Using these NSPDs, certain properties are explored. Examples are presented to demonstrate the model constructing method, analysis and control design technique, and to reveal certain dynamic behaviors of NEGs.     

局部信息约束下网络演化博弈的动力学与优化

网络演化博弈的优化问题是混合值逻辑网络的一个自然推广.本文研究了一类网络演化博弈的优化控制问题,其中每个控制个体在极大化自己的收益时只能获取到邻域信息.首先,利用矩阵的半张量积,将局部信息约束下控制网络演化博弈的动力学转化为相应的代数形式.然后得到了局部信息约束下确定型网络演化博弈的最优控制序列.最后,基于动态规划的解,研究了局部信息约束下概率型网络演化博弈的优化控制问题,得到了最优控制序列的简单计算公式.两个数值例子验证了本文的理论结果.     

Stable degree analysis for strategy profiles of evolutionary networked games网络演化博弈中策略组合的稳定度分析

In this paper, we investigate the stable degree of strategy profile for evolutionary networked games by using the semi-tensor product method, and present a number of new results. First, we propose the concept of k-degree stability for strategy profiles based on a normal evolutionary networked game model. Second, using the semi-tensor product of matrices, we convert the game dynamics with “best imitate” strategy updating rule into an algebraic form. Third, based on the algebraic form of the game, we analyzed the stable degree of strategy profile, and proposed two necessary and sufficient conditions for the k-degree stability of strategy profile. Furthermore, we discuss the computation problem of the transient time within which a disturbed strategy profile can be restored, and also establish an algorithm for the verification of the stable degree of strategy profile. The study of an illustrative example shows that the new results obtained in this paper are very effective.     

On Dynamics and Nash Equilibriums of Networked Games

Networked noncooperative games are investigated, where each player (or agent) plays with all other players in its neighborhood. Assume the evolution is based on the fact that each player uses its neighbors' current information to decide its next strategy. By using sub-neighborhood, the dynamics of the evolution is obtained. Then a method for calculating Nash equilibriums from mixed strategies of multi-players is proposed. The relationship between local Nash equilibriums based on individual neighborhoods and global Nash equilibriums of overall network is revealed. Then a technique is proposed to construct Nash equilibriums of an evolutionary game from its one step static Nash equilibriums. The basic tool of this approach is the semi-tensor product of matrices, which converts strategies into logical matrices and payoffs into pseudo-Boolean functions, then networked evolutionary games become discrete time dynamic systems.      

The interpretation of discontinuous state feedback control laws as nonanticipative control strategies in differential games

In differential games, one player chooses a feedback strategy to maximize a payoff. The other player counters by applying a minimizing open loop control. Classical notions of feedback strategies, based on state feedback control laws for which the corresponding closed loop dynamics uniquely define a state trajectory, are too restrictive for many problems, owing to the absence of minimizing classical feedback strategies or because consideration of classical feedback strategies fails to define, in a useful way, the value of the game. A number of feedback strategy concepts have been proposed to overcome this difficulty. That of Elliot and Kalton, according to which a feedback strategy is a nonanticipative mapping between control functions for the two players, has been widely taken up because it provides a value of the game which connects, via the Hamilton-Jacobi-Isaacs equation, with other fields of systems science. Heuristic analysis of specific games problems often points to discontinuous optimal feedback strategies. These cannot be regarded as classical feedback control strategies because the associated state trajectories are not in general unique. We give general conditions under which they can be interpreted as generalized feedback strategies in the sense of Elliot and Kalton.     

三方多策略式博弈系统的长期演化稳定均衡特性研究

演化博弈论(EGT)基于有限理性假设且更加贴近现实,近年来已在众多领域得到了初步应用.基于此,本文关注一类较为常见的三方多策略式演化博弈系统,尝试通过理论分析总结其长期演化稳定均衡(ESE)特性,并进行仿真验证研究.首先,研究了一般情形下的三方两策略对称与非对称演化博弈系统;然后,将其扩展到更复杂的三方三策略非对称演化博弈类型,并对其长期ESE特性进行了理论分析与动态仿真验证;进一步,对通用三方n-策略(n 1)非对称演化博弈的建模思路进行了阐述与总结,给出其收敛迭代的计算方法.研究过程中详细定义了各类演化博弈模型的相对净支付(RNP)参数.实验结果表明可通过一些外部因素适当调整RNP参数使各类系统朝着期望的长期ESE状态自发收敛.最后,进行了实例验证.本文研究模型、方法和所得结论具有一定普适性,旨在丰富EGT研究,尤其是三方多策略演化博弈问题研究,并为相关领域非完全理性人参与的行为决策问题研究提供一些思路和理论参考.     

Disturbance attenuation analysis of state feedback Nash strategy for two-player Linear Quadratic Sequential Games

There is limited formal mathematical analysis of one type of games — dynamic sequential games with large, or even infinitely large, planning horizons, from the point view of system controls. In this paper, we use a zero-sum game theoretical approach to address the disturbance attenuation analysis of state feedback Nash strategies for Dynamic Linear Quadratic Sequential Games (LQSGs) with uncertainties or disturbances. Based on the assumption that the disturbance will do the worst to the normal game players, we provide a simultaneous zero-sum game formulation between nature and each player, and a non-zero sum formulation among the players. For finite-horizon LQSGs, we first provide state feedback Nash strategies with optimal attenuation levels. Then we extend the approach to infinite-horizon LQSGs. We prove that the feedback system is Bounded Input Bounded Output (BIBO) stable with respect to the disturbances.     

An equivalence result in linear-quadratic theory

We consider the zero-endpoint infinite-horizon LQ problem. We show that the existence of an optimal policy in the class of feedback controls is a sufficient condition for the existence of a stabilizing solution to the algebraic Riccati equation. This result is shown without assuming positive definiteness of the state weighting matrix. The feedback formulation of the optimization problem is natural in the context of differential games and we provide a characterization of feedback Nash equilibria both in a deterministic and stochastic context.     

Improving player experience in Computer Games by using players' behavior analysis and linguistic descriptions

Understanding player behavior has an interest to computer games researchers and developers since it allows them to improve the design and implementation of computer games and also to ensure that players have the expected experiences. Currently this knowledge is not usually reported to players as feedback, although sometimes it is already used as an analysis tool. This paper presents a novel technology for automatically generating linguistic reports and immediate feedback from actions performed by players during play sessions. These reports allow developers to provide players with a more complete and personalized feedback about their behaviors, abilities, attitudes, skills or movements. In order to show and explore the possibilities of this new technology, we have incorporated it in the core of a computer game. We have evaluated positively that the incorporation of this kind of feedback into the core of YADY computer game allows us to improve the overall player experience.