基于事件驱动控制的混杂动态博弈系统的纳什均衡分析

陈向勇 曹进德 赵 峰 姜晓伟

(1.临沂大学自动化与电气工程学院,山东临沂 276005;2.东南大学数学学院,江苏南京 211189;3.中国地质大学复杂系统先进控制与智能自动化湖北省重点实验室;自动化学院,湖北武汉 430074)

1 引言

20世纪60年代中期,诺贝尔奖获得者泽尔腾将纳什均衡概念引入动态分析,开创了动态博弈的研究.经过近六十年发展,一系列重要成果被提出,比如,属于连续动态博弈范畴的微分对策[1]已被成功应用于飞行器追逃控制、多目标协同作战等方面;源于棋牌游戏的事件动态博弈[2]在2007年被首次提出并实现了对逻辑层面有限阶段动态博弈的分析和求解[3].

近年来,混杂动态博弈已经成为新的研究热点.它源于作战行动和棋牌游戏,描述的是两个非合作智能主体之间事件动态博弈和微分对策相互作用的多阶段博弈过程.然而,逻辑状态演化的引入使得系统结构复杂度变高,导致传统的博弈模型无法准确地描述系统的内在结构和演化特征,对其进行建模和求解变得非常困难,如何建立更有效描述混杂动态博弈演化过程的数学模型成为首要解决的问题.其中,徐等首次通过一个空战实例介绍了基于事件触发的混杂动态博弈问题的内容与处理方法[4].此后,针对阶段数较少的混杂动态博弈,陈等建立了基于Lanches-ter方程的状态空间表述模型,分别对连续最优策略和事件变招策略的求解[5-6].针对逻辑层面的有限动态博弈,程代展教授给出了演化博弈的代数状态空间描述和博弈策略的矩阵表示[7-8].2019年,借鉴混杂动态系统的思想,文献[9]首次提出了博弈切换演化动力学框架(图1a所示),即不同博弈模式对应不同环境状态,个体行为和当前时间进行博弈共同决定下一时间进行的博弈,并研究了网络结构群体合作演化行为.以上研究结果都为混杂动态博弈系统的分析和控制提供了较好的基础模型.

当前,人工智能在围棋、星际争霸等博弈场景的应用[10-11],为动态博弈问题的求解带来便利并取得算法方面的进步,使得博弈系统的策略集和阶段数逐渐庞大,呈现出规模大和结构复杂度高的特点.特别在博弈演化过程中,预测结果千变万化,导致传统的博弈理论无法准确分析其演化规律.因此,众多研究者开始重新审视复杂动态博弈中纳什均衡的意义和作用,并对博弈从初始状态到均衡的动态演化过程及参与者的运动规律进行深入探索.其中,演化稳定策略[12-13]为复杂博弈均衡解的研究实现了突破.文献[14-15]对多阶段演化博弈中的有限理性问题进行了理论分析和应用验证,实现了对传统博弈问题参与者“理性”基础的修正.文献[16]给出多阶段有限博弈的均衡分析和一致性预测成立条件.文献[17]针对具有大策略集的多阶段博弈给出期望条件,实现了均衡的存在性分析和求解.文献[18-19]针对复杂动态博弈的演化特点,利用事件树给出了激励均衡、完美子博弈强均衡和开环反馈纳什均衡的概念和性质.这都为混杂动态博弈均衡问题的分析提供理论借鉴.

另一方面,复杂博弈均衡的求解在智能优化算法方面[20]取得了进步.针对非合作博弈系统,提出时变纳什均衡和广义纳什均衡等概念,设计了有效求解的分布式智能优化方法[21-23].由此,上述研究成果已经在大规模复杂博弈的均衡求解方面发挥了作用.然而,混杂动态博弈的均衡解需要在多阶段演化后通过动态调整才能达到,而且参与者对保证利益最大化行动的理解存在较大差异,而针对混杂动态博弈均衡的存在性分析、性质分类等研究成果较少.

受上述分析的启发,本文研究了基于事件驱动控制的混杂动态博弈系统的纳什均衡分析问题.首先,分析了事件驱动机制对混杂动态博弈过程的影响,进而,在进行状态空间描述的基础上,给出了混杂动态博弈的纳什均衡的定义,并建立了对应博弈系统的策略型模型.其次,结合Lanchester方程,分别讨论了两类混杂动态博弈系统的均衡问题,包括事件驱动策略设计和固定的情况,获得了均衡解存在的必要条件.最后,数值模拟进行了应用分析,验证了所取得结果的合理性,并总结了混杂动态博弈研究的未来工作.

2 模型描述和基础知识

图1展示了非合作动态博弈双方的混杂动态演化过程,其中,X和Y为博弈双方的决策者,从图1不难看出,混杂动态博弈的演化过程包含两个层面,一是决策者的变招X和Y发生在离散时刻,每次变招都是根据博弈双方观察和探测的态势信息确立的,都会改变对阵的形势,引起连续系统的结构性变化,表现为事件驱动的逻辑状态变化.另一层面就是双方连续动态的博弈过程,具体是根据决策者的指令和系统的结构特征而不断调整连续控制输入,来改变各单元状态量,但是博弈双方的态势不会发生改变,属于系统结构不变情况下的连续控制过程,如此构成了混合动态博弈的演化过程.由此,依据文献[4-5]的建模原则,可得

图1 混杂动态博弈系统演化结构图Fig.1 Evolution structure of hybrid dynamic games system

其中:x和y是X和Y的状态向量;t ∈[0,T],T是终端时刻;Ex和Ey分别是双方引起系统结构变化的事件驱动控制策略;U和V是连续控制输入向量.进而,定义如下的性能指标函数:

其中:Φ(x(T),y(T))为与终端状态向量有关的连续函数;h(x,y,Ex,Ey,U,V)为连续函数.由此构成了混合动态博弈系统的状态空间描述的一般形式.

由此,设博弈双方在tk(1 ≤k<∞)时进行引起系统结构变化的事件驱动变招,其中tk ∈[t0,tf],t0≤t1≤···≤tk≤···≤tf,t0为初始时刻,tf为终端时刻,可确定策略集为U={U1,U2,··· ,Uk,},V={V1,V2,··· ,Vk},Ex={Ex1,Ex2,··· ,Exk},Ey={Ey1,Ey2,··· ,Eyk}.定义博弈双方在确定连续控制和事件变招策略集后的对阵态势集合为S={s0,s1,··· ,sk,sf},s0={sx0,sy0}为初始态势,演化稳定结局为sf={sxf,syf},对应的sq(q=1,2,··· ,k)为演化过程中双方确定策略后的态势,由此可以得到

由此,可以用一个七元数组建立混杂动态博弈系统的策略型模型

其中:P={X,Y}是博弈双方的决策者集合,决策双方对应的状态向量一般定义为x={x1,x2,··· ,xn}和y={y1,y2,··· ,ym};S={s0,s1,··· ,sk,sf}为态势集合,C={U,V}为连续控制策略集合;E={EX,EY}为双方根据态势制定的事件驱动策略;Σ:s×(E×C)→s为态势转移函数集合;R是由博弈双方制定的演化规则,包括行动集、信息集和预先制定的规则等;J为性能指标函数.

本文主要是针对所建立基于事件驱动控制的混杂动态博弈系统,对其纳什均衡进行分析.根据博弈论和微分对策理论,当混杂动态博弈的事件触发次数较少和策略集合较小时,可知博弈的纳什均衡需要满足

注1式(4)中给出的纳什均衡的定义是按照传统博弈论和微分对策的基础理论所提出的.由于本文研究的混杂动态博弈主要是由事件驱动控制和连续微分对策相互作用所组成的,而每一次变招的发生都和系统的结构特性、参数和性能指标等有着紧密的联系,因此在每一次事件驱动策略不变的连续博弈演化中,纳什均衡解都是存在的.

3 主要结果

本节重点考虑事件驱动控制策略和连续控制策略对混杂动态博弈演化的影响,将分别对事件驱动的混杂动态博弈的均衡问题和事件策略固定的混杂动态博弈系统的均衡问题进行分析.

3.1 事件驱动控制的混杂动态博弈的纳什均衡

针对系统(1)和性能指标(2),设博弈双方的连续控制输入量是固定量,则混杂动态博弈的纳什均衡问题转化为求解最佳事件驱动策略(E∗x,E∗y)使得

其中:αji>0为Y方第j个单元对X方第i个单元的损耗系数;βij>0为X方第i个单元对Y方第j个单元的损耗系数;ηi和θj分别为终端状态所对应的重要性加权因子;ψji ∈{0,1}和φij ∈{0,1}是事件驱动变量.特别是,当在tq时刻发生变招时会引起对应值的选取,则对应的事件驱动策略的表达式为

其中:ψjqi为事件驱动策略确定后Y方第jq个单元会对阵X方的第i个单元;同样,φiq′j表示X方第iq′个单元会对阵Y方第j个单元;{1q,··· ,nq}∈{1,··· ,n}表示Y方在tq时刻变招发生后的选择的对阵方式;同样{1q′,··· ,mq′}∈{1,··· ,m}表示X方在tq时刻变招发生后的选择的对阵方式.

注2以上讨论的模型(6)属于系统(1)的范畴,可以改写成其中α和β为对应αji>0和βij>0的系数矩阵.同样,对应的性能指标(7)属于指标(2)的范畴.

注3因为ψjqi和φiq′j都是0-1型事件驱动变量.根据Lanchester方程的基础理论,当上述的矩阵中列和条件被满足时,表示博弈双方在选择对阵单元的时候必须集中全部力量攻击对方.

由此,根据动态博弈求解均衡的极大极小值原理,可以得到上述博弈系统均衡存在的必要条件.

定理1 设上述混杂动态博弈系统的伴随函数为λ={λ1,··· ,λm},µ={µ1,··· ,µn},对应系统的Hamilton函数为

注4此定理的具体证明过程可参考文献[6]给出的定理证明.

3.2 事件策略固定的混杂动态博弈的纳什均衡

针对系统(1)和性能指标(2),设博弈双方事件驱动策略是固定不变的,则混杂动态博弈的均衡问题转化为求解最优控制策略(U∗,V ∗)使得

注6根据Lanchester方程的基础理论,当上述的矩阵中列和和行和条件被满足时,所表示的物理含义是指博弈双方在对阵选择中己方的一个单元只能选择对阵对方的一个单元.

由此,针对博弈双方的连续控制输入ui(t)∈[u∗,

其中:u∗,u∗,v∗,v∗,M0和N0为非负实数,q=1,··· ,k.

证 根据式(15)可知

注9本部分讨论的事件驱动策略是不变的,但是变招时刻是需要计算出来,根据文献[5]提供的计算步骤,可以从终端时刻开始往前逐级求取每一时间区间[tq−1,tq]内的最优连续控制策略,在此基础上,利用静态优化方法可以求得变招时刻以及最终整个混杂博弈系统的纳什均衡.

注10如果变招时刻也是固定,这样整个混杂动态博弈系统就被划分为k+1个微分对策子系统,只需要按照微分对策原理,求出每一时间段内的子博弈系统的纳什均衡并将其整合,所对应的结果就是整个混杂博弈系统的纳什均衡结果.

3.3 应用例子

近年来,Lanchester方程已被成功应用于市场竞争、公共交通投资、人口预测模型等[24-25].文献[5-6]也给出了两类基于Lanchester方程的混杂动态博弈系统模型.由此,本文针对与系统模型(6)和模型(16)有关的应用例子进行均衡分析.

例1 设系统的连续控制输入量全为0,考虑如下混杂动态博弈模型

设系统状态的初始值为x10=100,y10=30,y20=30,终端时间为T=0.489.首先根据定理1可以求出纳什均衡解满足的条件为

进而,根据文献[6]的理论结果,可知,对于Ex在tq=0.384时刻会发生一次变招,对应的事件驱动策略为

则基于系统(21)和性能指标(22)的事件驱动的混杂动态博弈系统的纳什均衡满足

例2 在例1的基础上,保持系统模型不变,但性能指标为

由此,按照已取得的理论分析结果,可以求出在博弈演化时间段内没有新的变招发生,则对应博弈系统的纳什均衡满足

注11从例1和例2可以看出,上述事件驱动的混杂动态博弈系统纳什均衡的存在性与模型的系数和性能指标的重要性因子有关系.

则按照本文的理论分析结果和文献[5]的基本理论,可以得到变招时刻为t1=2.5,对应博弈系统的纳什均衡解(U∗,V ∗)需要满足

注12从例3可以看出,在事件驱动策略固定的前提下,混杂博弈系统的纳什均衡的存在性与变招发生的时刻以及最优连续控制输入有关系.

4 结论和展望

本文对基于事件驱动的混杂动态博弈系统的均衡问题进行了研究.在建立系统的状态空间模型和策略型表达式的基础上,分析了事件驱动控制在混杂动态博弈演化中的作用和意义,给出了传统意义上的纳什均衡的定义.进而,针对事件驱动变化的混杂动态博弈系统和事件策略固定的混杂动态博弈系统,分别对纳什均衡的存在性进行了分析,展示出混杂动态博弈系统在一定条件下纳什均衡的特点.最后通过应用分析展示了分析结果的可行性.

然而,混杂动态博弈的研究尚处于起步阶段.本文的主要研究也主要是结合Lanchester方程,在一定假设条件的基础上对两类特殊的混杂动态博弈系统的均衡问题进行研究.仅仅考虑了理性的博弈决策方遵守一致预测的情况,没有给出一般性的结论.基于此,针对于混杂动态博弈系统的建模、分析、控制和应用问题,未来的研究工作具体包括:

1) 如何较好地描述内在演化规律和结构特征并建立模型是混杂动态博弈首要解决的问题.近年来,网络科学的发展及不对称博弈方向的深入研究,为探讨具有大策略集和多阶段数的混杂动态博弈的演化特征提供了启发和借鉴.一方面,针对连续动态博弈,文献[26]建立了基于Lanchester方程的两阶段攻防对抗博弈系统的网络化模型.针对逻辑层面的动态博弈,文献[27]给出了考虑每个节点的演化方程,建立了表述其演化特征的逻辑动态模型,给出了切换拓扑的网络演化博弈的代数空间描述.2020 年,梅森·波特指出多层时序网络已成为未来网络科学的研究热点之一[28].由此,网络科学的发展为探讨更复杂的混杂动态博弈系统的内在规律和演化特征并建立更准确的模型提供了启发和借鉴.

2) 博弈分析的目的是预测博弈的结果.由于大策略集和多阶段数的影响,混杂动态博弈对阵局势更为重要,纳什均衡的达到应当是在多次博弈后通过动态调整才能达到的,具有“相对性”和“动态性”.同时,在多阶段演化中,博弈决策双方产生不理性决策,使得传统的一致预测条件不再成立,这就需要给出“理性”决策主体一致性预测成立条件,这样才能混杂动态博弈研究目的与任务,这是实现混杂博弈控制的基本条件,也是设计最优策略求解的关键前提.

3) 混杂动态博弈典型特点就是具有较大的策略集和阶段数,这必然会给最优策略的设计和求解带来极大的困难,因此需要通过网络节点评估和拓扑结构分析,研究给出网络演化莫模型中重要节点的判别条件,设计消除失效策略的剪枝搜索方法并对大策略集空间简化,是混杂动态博弈理论研究的另一关键突破.同时,需要注意的时,在混杂动态博弈的网络演化中,网络中多个个体之间需要互相通信和信息交互,这样才能够实现博弈态势的监测和获取.当出现不完全的不对称信息时,博弈双方的决策状态会受到影响,从理论角度,就需要对衡量博弈双方获得信息的能力进行量化并在模型中体现,而从算法角度,就需要对演化稳定策略的求解进行算法设计,当前,分布式优化[31-32]和强化学习技术[33]为复杂博弈问题的研究提供了算法方面的借鉴,但这也对本文研究的混杂动态博弈在理论和算法学方面的研究提出了新挑战.

4) 混杂动态博弈的理论体系的完善离不开应用验证.现代物流系统[29-30]规模大且结构度复杂,是以离散事件为主的复杂的连续-离散事件相统一的混杂动态系统.特别是,物流供需博弈演化具有混杂动态特性,考虑供应量、需求量、供需速度、物流供需信息因素的影响,构建以需求方和供给方为决策主体、以利益最大化为供需目的的网络化混杂动态博弈模型;实现物流供需博弈系统的分析和求解,进而,通过建立网络演化仿真平台,实现对物流供需博弈的求解和应用验证,不断丰富和更新混杂动态博弈系统分析和控制的理论和方法体系.